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

Question

Given an unsorted array, find the max j - i difference between indices such that j > i and a[j] > a[i] in O(n). I am able to find j and i using trivial methods in O(n^2) complexity but would like to know how to do this in O(n)?

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}

Output: 5 (j = 5, i = 0)

Answer 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