find the max difference between j and i indices such that j > i and a[j] > a[i] in O(n)

Solution 1:

For brevity's sake I am going to assume all the elements are unique. The algorithm can be extended to handle non-unique element case.

First, observe that if x and y are your desired max and min locations respectively, then there can not be any a[i] > a[x] and i > x, and similarly, no a[j] < a[y] and j < y.

So we scan along the array a and build an array S such that S[i] holds the index of the minimum element in a[0:i]. Similarly an array T which holds the index of the maximum element in a[n-1:i] (i.e., backwards).

Now we can see that a[S[i]] and a[T[i]] are necessarily decreasing sequences, since they were the minimum till i and maximum from n till i respectively.

So now we try to do a merge-sort like procedure. At each step, if a[S[head]] < a[T[head]], we pop off an element from T, otherwise we pop off an element from S. At each such step, we record the difference in the head of S and T if a[S[head]] < a[T[head]]. The maximum such difference gives you your answer.

EDIT: Here is a simple code in Python implementing the algorithm.

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist

Solution 2:

Let's make this simple observation: If we have 2 elements a[i], a[j] with i < j and a[i] < a[j] then we can be sure that j won't be part of the solution as the first element (he can be the second but that's a second story) because i would be a better alternative.

What this tells us is that if we build greedily a decreasing sequence from the elements of a the left part of the answer will surely come from there.

For example for : 12 3 61 23 51 2 the greedily decreasing sequence is built like this:

12 -> 12 3 -> we ignore 61 because it's worse than 3 -> we ignore 23 because it's worse than 3 -> we ignore 51 because it's worse than 3 -> 12 3 2.

So the answer would contain on the left side 12 3 or 2.

Now on a random case this has O(log N) length so you can binary search on it for each element as the right part of the answer and you would get O(N log log N) which is good, and if you apply the same logic on the right part of the string on a random case you could get O(log^2 N + N(from the reading)) which is O(N). But we can do O(N) on a non-random case too.

Suppose we have this decreasing sequence. We start from the right of the string and do the following while we can pair the last of the decreasing sequence with the current number

1) If we found a better solution by taking the last of the decreasing sequence and the current number than we update the answer

2) Even if we updated the answer or not we pop the last element of the decreasing sequence because we are it's perfect match (any other match would be to the left and would give an answer with smaller j - i)

3) Repeat while we can pair these 2

Example Code:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    // let's solve the problem
    vector<int> decreasing; 

    pair<int, int> answer;

    // build the decreasing sequence
    decreasing.push_back(1);
    for (int i = 1; i <= N; ++i)
        if (A[i] < A[decreasing.back()])
            decreasing.push_back(i); // we work with indexes because we might have equal values

    for (int i = N; i > 0; --i) {
        while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
            pair<int, int> current_pair(decreasing.back(), i);
            if (current_pair.second - current_pair.first > answer.second - answer.first)
                answer = current_pair;
            decreasing.pop_back();
        }
    }

    cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")\n";
}

Later Edit: I see you gave an example: I indexed from 1 to make it clearer and I print (i, j) instead of (j, i). You can alter it as you see fit.

Solution 3:

We can avoid checking the whole array by starting from the maximum difference of j-i and comparing arr[j]>arr[i] for all the possible combinations j and i for that particular maximum difference Whenever we get a combination of (j,i) with arr[j]>arr[i] we can exit the loop

Example : In an array of {2,3,4,5,8,1} first code will check for maximum difference 5(5-0) i.e (arr[0],arr[5]), if arr[5]>arr[0] function will exit else will take combinations of max diff 4 (5,1) and (4,0) i.e arr[5],arr[1] and arr[4],arr[0]

int maxIndexDiff(int arr[], int n)
{
    int maxDiff = n-1;
    int i, j;

    while (maxDiff>0)
    {
        j=n-1;
        while(j>=maxDiff)
        {
            i=j - maxDiff;
            if(arr[j]>arr[i])
            { 
                return maxDiff;  
            }
            j=j-1;
        }
        maxDiff=maxDiff-1;
    }
    return -1;  
}`

https://ide.geeksforgeeks.org/cjCW3wXjcj

Solution 4:

Here is a very simple O(n) Python implementation of the merged down-sequence idea. The implementation works even in the case of duplicate values:

downs = [0]
for i in range(N):
    if ar[i] < ar[downs[-1]]:
        downs.append(i)

best = 0
i, j = len(downs)-1, N-1
while i >= 0:
    if ar[downs[i]] <= ar[j]:
        best = max(best, j-downs[i])
        i -= 1
    else:
        j -= 1
print best