Given an unsorted array, find the max j – i difference between indices such that j > i and a[j] > a[i] in O(n).
Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)Solution
For an element a[i], we do not need to consider a[i] for left index if there is an element smaller than a[i] on left side of a[i]. Similarly, if there is a greater element on right side of a[j] then we do not need to consider this j for right index.
So we scan along the array a and build an array S such that S[i] holds the minimum element in a[0:i]. Similarly an array T which holds the maximum element in a[n-1:i] (i.e., backwards). S and T are necessarily decreasing sequences, since they were the minimum till i and maximum from n till i respectively. For example
If a = [2,5,3,4,1] S would look like [2,2,2,2,1] Similarly, T would look like [5,5,4,4,1]
We traverse arrays S and T from left to right. While traversing S[] and T[] if we see that S[i] is greater than T[j], then we must move ahead in S[] because all elements on left of S[i] are greater than or equal to S[i]. Otherwise we must move ahead in T[j] to look for a greater j – i value.