> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/max-distance.md).

# Max Distance

Given an array **A** of integers, find the maximum of **j - i** subjected to the constraint of **A\[i] <= A\[j]**.\
\
**Input Format**<br>

First and only argument is an integer array A.\
\
**Output Format**<br>

Return an integer denoting the maximum value of j - i;\
\
**Example Input**<br>

Input 1:

```
 A = [3, 5, 4, 2]
```

\
**Example Output**<br>

Output 1:

```
 2
```

\
**Example Explanation**<br>

Explanation 1:

```
 Maximum value occurs for pair (3, 4).
```

```java
public class Solution {
    public int maximumGap(final int[] A) {
        if (A.length == 1)
            return 0;
        int maxDiff;
        int i, j;
        int RMax[] = new int[A.length];
        int LMin[] = new int[A.length];
        /*
         * Construct LMin[] such that LMin[i] stores the minimum value from (arr[0],
         * arr[1], ... arr[i])
         */
        LMin[0] = A[0];
        for (i = 1; i < A.length; ++i)
            LMin[i] = Math.min(A[i], LMin[i - 1]);
        /*
         * Construct RMax[] such that RMax[j] stores the maximum value from (arr[j],
         * arr[j+1], ..arr[n-1])
         */
        RMax[A.length - 1] = A[A.length - 1];
        for (j = A.length - 2; j >= 0; --j)
            RMax[j] = Math.max(A[j], RMax[j + 1]);
        /* Traverse both arrays from left to right to find optimum j - i */
        i = 0;
        j = 0;
        maxDiff = -1;
        while (j < A.length && i < A.length) {
            if (LMin[i] <= RMax[j]) {
                maxDiff = Math.max(maxDiff, j - i);
                j = j + 1;
            } else
                i = i + 1;
        }
        return maxDiff;
    }
}
```