Maximum Distance Problem Statement

Given an integer array 'A' of size N, your task is to find the maximum value of j - i, with the restriction that A[i]

Question

Maximum Distance Problem Statement

Given an integer array 'A' of size N, your task is to find the maximum value of j - i, with the restriction that A[i] <= A[j], where 'i' and 'j' are indices of the array.

Input:

The input begins with an integer 'T', indicating the number of test cases. Each test case consists of two lines:
The first line contains an integer 'N' representing the size of the array.
The second line contains 'N' space-separated integers denoting the elements of the array.

Output:

For each test case, output a single integer on a new line, representing the maximum possible value of j - i meeting the condition A[i] <= A[j].

Example:

Input:

A = [3, 5, 4, 1]

Output:

Explanation:

The maximum distance occurs for the pair (3, 4), giving a distance of 2.

Constraints:

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

Time limit: 1 second per test case.

Note:

There is no need to print anything explicitly. Implement the required function to generate the output.

Follow-Up:

Consider solving this problem with O(N) time complexity.

Accepted Answer

Find the maximum distance between two elements in an array where the element at the first index is less than or equal to the element at the second index.

Iterate through the array and keep track of the minimum element encountered so far along with its index.
Calculate the maximum distance by subtracting the current index from the index of the minimum element.
Update the maximum distance if a greater distance is found while iterating.
Return the maximum distance calculated.