05/03 GfG POTD Solution - The Logic Tutorial

 Input:

n = 2

a[] = {1, 10}

Output:

1

Explanation:

a[0] < a[1] so (j-i) is 1-0 = 1.

Example 2:

Input:

n = 9

a[] = {34, 8, 10, 3, 2, 80, 30, 33, 1}

Output:

6

Explanation:

In the given array a[1] < a[7] satisfying the required condition(a[i] < a[j]) thus giving the maximum difference of j - i which is 6(7-1).

Your Task:

The task is to complete the function maxIndexDiff() which finds and returns maximum index difference. Printing the output will be handled by driver code

class Solution{
public:
    int maxIndexDiff(int arr[], int n) {
        vector<int> prefix(n), suffix(n);
        prefix[0] = arr[0];
        suffix[n - 1] = arr[n - 1];
        
        for(int i = 1; i < n; i++){
            prefix[i] = min(prefix[i - 1], arr[i]);
            suffix[n - i - 1] = max(suffix[n - i], arr[n - i - 1]);
        }
        
        int i, j, ans;
        i = j = ans = 0;
        
        while(j < n){
            if(prefix[i] <= suffix[j]){
                ans = max(ans, j - i);
                ++j;
            }
            else{
                ++i;
            }
        }
        
        return ans;
    }
};