Two sorted elements with maximum distance in an unsorted array - PrismoSkills

Two sorted elements with maximum distance in an unsorted array - PrismoSkills

Problem: Given an unsorted array, find two indexes in the array such that arr[i] < arr[j] and j-i is maximum.

Example: If the array is [7, 3, 9, 2, 1, 11, 0], 7 and 11 are the solution.


Solution: A naive solution is O(n²) where we loop over entire array and at each loop-position, check the elements towards its right for greater elements max distance far.

For a more efficient solution, we will need to analyze some properties of the problem.

Note that for any solution i and j, the value (j-i) has to be maximum which means that no element towards right of j can be greater than arr[j].
Because if there were such an element, then that element would have been part of the solution and not arr[j].
Similarly, if i and j are a solution, then no element to left of arr[i] is smaller than arr[i].

Thus, if we create two arrays IndexOfLeftMinimum and IndexOfRightMaximum for every element in the array, then the solution is just the maximum value of IndexOfRightMaximum[k] - IndexOfLeftMinimum[k].

Does this really work?

Note that the for i,j to be a solution, a[i] is the minimum from 0 to i and a[j] is the maximum from j to a.length One could get confused here in thinking that there could be an index k to the right of j such that a[k] < a[j] but a[k] > a[i] (i.e. an element lesser than a[j] existing in the right-side of j but greater than a[i]) If such an element were to exist, then wouldn't (i,k) form the solution instead of (i,j)? Answer to this question is yes, but our original observation holds here again that if (i,k) were the solution, then there would be no element bigger than a[k] towards the right of k. Then do we have two solutions here: (i,j) and (i,k)? Answer to that is also yes but since we need to choose the maximum, we will choose (i,k) And that is what happens in the last loop of the below code.

Read full article from Two sorted elements with maximum distance in an unsorted array - PrismoSkills