Max Distance

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

If there is no solution possible, return -1.

Example : A : [3 5 4 2]

Output : 2 for the pair (3, 4)

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Solution:

1. To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j.

2. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i].

3. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index.

4. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j].

5. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right.

6. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

int Solution::maximumGap(const vector<int> &A) {
    int maxGap;
    int i, j;

    vector<int> LMin(A.size(), 0);
    vector<int> RMax(A.size(), 0);

   /* Construct LMin such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = A[0];
    for (i = 1; i < A.size(); ++i)
        LMin[i] = min(A[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[A.size()-1] = A[A.size()-1];
    for (j = A.size()-2; j >= 0; --j)
        RMax[j] = max(A[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxGap = 0;
    while (j < A.size() && i < A.size()) {
        if (LMin[i] <= RMax[j]) {
            maxGap = max(maxGap, j-i);
            j = j + 1;
        } else {
            i = i+1;
        }
    }

    return maxGap;
}