Maximum Distance

Moderate

0/80

Average time to solve is 15m

Contributed by

104 upvotes

Asked in companies

Problem statement

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)

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

1
9
34 8 10 3 2 80 30 33 1

Sample Output 1:

Explanation:

Maximum value occurs for the pair (8, 33)

Sample Input 2:

1
10
9 2 3 4 5 6 7 8 18 0

Sample Output 2:

Explanation:

Maximum value occurs for the pair (9, 18)

Hint 1

Can you think of solving the problem in O(N) time complexity by using extra space?

Approaches (1)

Approach 1

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.

Time Complexity

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

Space Complexity

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

(100% EXP penalty)

Maximum Distance

Console