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

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