Make delicious recipes!

Two sorted elements with maximum distance in an unsorted array



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(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].

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.
Example:


Example 1:
Input Array         :  [7, 3, 9, 2, 1, 11, 0]

IndexOfLeftMinimum  :  [0, 1, 1, 3, 4,  4, 6]
IndexOfRightMaximum :  [5, 5, 5, 5, 5,  5, 6]
Distance Array      :  [5, 4, 4, 3, 1,  1, 0]

Maximum value in distance array = 5
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 5
Solution: i=0, j=5

Example 2:

Input Array         :  [0, 1, 2, 3, 4]

IndexOfLeftMinimum  :  [0, 0, 0, 0, 0]
IndexOfRightMaximum :  [4, 4, 4, 4, 4]

Maximum value in distance array = 4
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 4
Solution: i=0, j=4

Example 3:
Input Array         :  [4, 3, 2, 1, 0]

IndexOfLeftMinimum  :  [0, 1, 2, 3, 4]
IndexOfRightMaximum :  [0, 1, 2, 3, 4]

Maximum value in distance array = 0
Corresponding i (from IndexOfLeftMinimum array)  = None
Corresponding j (from IndexOfRightMaximum array) = None
Solution: No such pair


Code:

void findMaxDistanceApart (int arr[])
{
    if (arr.length<=1)
        return;

    int indexOfLeftMin [] = new int [arr.length];
    int indexOfRightMax[] = new int [arr.length];

    // below loop fills first array such that value at every index
    // tells the position of the minimum element present in the left of that index
    indexOfLeftMin[0] = 0;
    for (int i=1; i< arr.length; i++)
    {
        int currMin = arr[indexOfLeftMin[i-1]];
        if (arr[i] < currMin)
        {
            indexOfLeftMin[i] = i;
        } else {
            indexOfLeftMin[i] = indexOfLeftMin[i-1];
        }
    }


    // below loop fills second array such that value at every index
    // tells the position of the maximum element present in the right of that index
    indexOfRightMax[arr.length-1] = arr.length-1;
    for (int i=arr.length-2; i >= 0; i--)
    {
        int currMax = arr[indexOfRightMax[i+1]];
        if (arr[i] > currMax)
        {
            indexOfRightMax[i] = i;
        } else {
            indexOfRightMax[i] = indexOfRightMax[i+1];
        }
    }

    // find k such that difference between indexOfRightMax[k] and indexOfLeftMin[k] is maximum
    
    int maxDiff = -1;
    int i = -1;
    int j = -1;
    for (int k=0; k < arr.length; k++)
    {
        int distance = indexOfRightMax[k] - indexOfLeftMin[k];
        if (distance > maxDiff)
        {
            i = indexOfLeftMin[k];
            j = indexOfRightMax[k];
        }
    }
    
    if (i==j)
    {
        print ("No such pair exists");
        return;
    }

    print ("Two sorted elements maximum distance apart are " + arr[i] + " and " + arr[j]);
    print ("And maximum distance is " + (j-i));

}







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal