Two sorted elements with maximum distance in an unsorted array

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:

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

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

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

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));

}