Maximum Distance

Posted: 16 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given an array 'A' of 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 <= DATA <= 10 ^ 5


Where ‘T’ is the number of test cases, ‘N’ is the size of the array, “DATA” is the value of the element of the array.

Time limit: 1 sec.
Approach 1

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.
Try Problem