Maximum Distance
You have been given an array 'A' of N integers. You need to find the maximum value of j - i subjected to the constraint of A[i]

Question

Maximum Distance

You have been given an array 'A' of N integers. You need to find the maximum value of j - i subjected to the constraint of A[i] <= A[j], where ‘i’ and ‘j’ are the indices of the array.

For example :

If 'A' = {3, 5, 4, 1}

then the output will be 2.
Maximum value occurs for the pair (3, 4)

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ which denotes the size of the array.

The second line of each test case contains elements of the array. The line consists of values of elements of the array separated by a single space.

Output Format:

For each test case, print a single line containing a single integer denoting the maximum value of j - i subjected to the condition A[i] <= A[j].

The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10 ^ 4
-10 ^ 5 <= A[i] <= 10 ^ 5

Time limit: 1 sec.

Follow Up:

Can you solve it using O(N) time complexity?

Accepted Answer

Efficient approach

The idea behind this approach is to create a monotonously decreasing array and comparing its values with the given array to find the maximum distance.

Create an auxiliary array ‘RMax’ such that ‘RMax’ holds the greatest element on the right side of the given array.
Declare a variable ‘diff’ initialized to -1 to find the maximum distance.
Now traverse both the arrays simultaneously from left to right and check for the condition.
If A[i] is greater than RMax[j], then we must move ahead in A[] (or do i++) because all elements on left of A[i] are greater than or equal to A[i].
Otherwise, we must move ahead in RMax[j] to look for a greater j – i value.
We keep on updating the value of ‘diff’ at each comparison.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

An auxiliary array of size N is used for the comparisons. So space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

We are iterating through the array only once. So overall time complexity will be O(N).

Python (3.5)

'''

    Time complexity: O(N)

	Space complexity: O(N)



	where 'N' is the size of the array.

'''



def maxDiff(a, n):

    

    rmax = [0] * n

    rmax[-1] = a[-1]

    

    # Store largest element to the right.

    for i in range (n - 2, -1, -1):

        rmax[i] = max(rmax[i + 1], a[i])

        

    res = -1

    i = 0

    j = 0

    

    # Compare both arrays.

    while i < n and j < n:

        if a[i] <= rmax[j]:

            res = max(res, j - i)

            j += 1

        else:

            i += 1

            

    return res

Java (SE 1.8)

/*



	Time complexity: O(N)

	Space complexity: O(N)



	where 'N' is the size of the array.



*/



import java.util.ArrayList;



public class Solution {

	public static int maxDiff(ArrayList a, int n) {



		// Create an auxiliary ArrayList.

		ArrayList RMax = new ArrayList(n);



		for (int i = 0; i < n; i++) {

			RMax.add(0);

		}



		RMax.set(n - 1, a.get(n - 1));



		// Store greatest element from right.

		for (int j = n - 2; j >= 0; j--) {

			RMax.set(j, Math.max(a.get(j), RMax.get(j + 1)));

		}



		int i = 0, j = 0;

		int diff = -1;



		// Start comparing both ArrayLists.

		while (j < n && i < n) {



			if (a.get(i).intValue() <= RMax.get(j).intValue()) {

				diff = Math.max(diff, j - i);

				j = j + 1;

			} else {

				// Move a step ahead in given array.

				i = i + 1;

			}



		}



		return diff;

	}



}

C++ (g++ 5.4)

/*



	Time complexity: O(N)

	Space complexity: O(N)



	where 'N' is the size of the array.



*/



int maxDiff(vector a, int n)

{

    // Create auxiliary vector.

    vector  RMax (n, 0);



    RMax[n - 1] = a[n -1] ;



    // Store greatest element from right.

    for(int j = n - 2; j >= 0; j--)

    {

        RMax[j] = max(a[j], RMax[j+1]);

    }



    int i = 0, j = 0;

    int diff = -1;



    // Start comparing both vectors.

    while (j < n && i < n)

    {

        // If greater element is found on right side as per the given condition.

        if (a[i] <= RMax[j])

        {

            // Update diff.

            diff = max(diff, j - i);

            j = j + 1;

        }

        else

        {

            // Move a step ahead in given array.

            i = i + 1;

        }

    }



    return diff;

}