# Maximum Index

Tue Feb 08 2022 05:04:45 GMT+0000 (Coordinated Universal Time)

```class Solution{
// Function to find the maximum index difference.
static int maxIndexDiff(int arr[], int n) {
if(n==1){
return 0;
}
int RMax[] = new int[n];
int LMin[] = new int[n];

//Constructing LMin[] such that LMin[i] stores the minimum value
//from (arr[0], arr[1], ... arr[i]).
LMin[0] = arr[0];
for (int i = 1; i < n; ++i)
LMin[i] = Integer.min(arr[i], LMin[i - 1]);

//Constructing RMax[] such that RMax[j] stores the maximum value
//from (arr[j], arr[j+1], ..arr[n-1]).
RMax[n - 1] = arr[n - 1];
for (int j = n - 2; j >= 0; --j)
RMax[j] = Integer.max(arr[j], RMax[j + 1]);

int i = 0, j = 0, maxDiff = -1;
//Traversing both arrays from left to right to find optimum j-i.
//This process is similar to merge() of MergeSort.
while (j < n && i < n) {
if (LMin[i] <= RMax[j]) {
//Updating the maximum difference.
maxDiff = Integer.max(maxDiff, j - i);
j++;
} else
i++;
}
//returning the maximum difference.
return maxDiff;
}
}```
content_copyCOPY

Maximum Index Given an array A[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of A[i] < A[j] and i < j. Example 1: Input: N = 2 A[] = {1, 10} Output: 1 Explanation: A[0]<A[1] so (j-i) is 1-0 = 1. Example 2: Input: N = 9 A[] = {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 Explanation: In the given array A[1] < A[7] satisfying the required condition(A[i] < A[j]) thus giving the maximum difference of j - i which is 6(7-1). Your Task: The task is to complete the function maxIndexDiff() which finds and returns maximum index difference. Printing the output will be handled by driver code. Return -1 in case no such index is found. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 1 ≤ N ≤ 10^7 0 ≤ A[i] ≤ 10^9

https://practice.geeksforgeeks.org/problems/maximum-index-1587115620/1/?track=DSASP-Arrays&batchId=190