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], then i=7 and j=11 is the solution.
Solution: A naive solution is O(n2) 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].
Read full article from Two sorted elements with maximum distance in an unsorted array - PrismoSkills
