Problem

Given an array arr[], find the maximum j – i such that arr[j] > arr[i].

Examples

Example 1:

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6  (j = 7, i = 1)

Example 2:

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Example 3:

Input:  {6, 5, 4, 3, 2, 1}
Output: -1

Solution

Note that as j-i is maximum, it means j > i.

Method 1 - Brute force

This is simple but inefficient solution. Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j - i so far.

Code

Java
public int maxIndexDiff(int arr[]) {
	int maxDiff = -1, n = arr.length;
	
	for (int i = 0; i < n; ++i) {
		for (int j = n - 1; j > i; --j) {
			if (arr[j] > arr[i] && maxDiff < (j - i)) {
				maxDiff = j - i;
			}
		}
	}

	return maxDiff;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using 2 Aux Arrays

Algorithm

  1. Initialize two arrays lMin and rMax of the same size as arr[].
    • lMin will store the index of the minimum element encountered so far to the left (including itself) for each index i in arr[].
    • rMax will store the index of the maximum element encountered so far to the right (including itself) for each index i in arr[].
  2. Fill lMin Array (Forward Pass)
    • For each index i:
    • Compare arrA[i] with arrA[lMin[i-1]] (the minimum element encountered so far).
    • If arrA[i] < arrA[lMin[i-1]], update lMin[i] to i (current element becomes the new minimum).
    • Otherwise, keep lMin[i] as lMin[i-1] (previous minimum remains).
  3. Fill rMax Array (Backward Pass).
    • For each index i:
    • Compare arrA[i] with arrA[rMax[i+1]] (the maximum element encountered so far).
    • If arrA[i] > arrA[rMax[i+1]], update rMax[i] to i (current element becomes the new maximum).
    • Otherwise, keep rMax[i] as rMax[i+1] (previous maximum remains).
  4. Calculate max index difference, by comparing the pairs {lMin[i], rMax[i]}.

Code

Java
public static int findMaxDistance(int[] arr) {
	int n = arr.length;

	int[] lMin = new int[n];
	int[] rMax = new int[n];

	lMin[0] = 0;
	for (int i = 1; i < n; i++) {
		lMin[i] = arr[i] < arr[lMin[i - 1]] ? i : lMin[i - 1];
	}

	rMax[n - 1] = n - 1;
	for (int i = n - 2; i >= 0; i--) {
		rMax[i] = arr[i] > arr[rMax[i + 1]] ? i : rMax[i + 1];
	}

	int maxDiff = -1;
	for (int i = 0; i < n; i++) {
		if (lMin[i] < rMax[i]) {
			maxDiff = Math.max(maxDiff, rMax[i] - lMin[i]);
		}
	}

	return maxDiff;
}

Dry Run

Initiate

Lets consider the array [7, 3, 9, 2, 1, 11, 0], with n = 7.

Forward pass to fill lMin

When we run the forward pass, and initiate lMin. lMin[0] is 0. i = 1

arr[i] = 3, arr[lMin[i - 1]] = 7

Math.min(3, 7) = 3, hence lMin[1] = i = 1. 

lMin becomes [0, 1, 0, 0, 0, 0, 0]

i = 2

arr[i] = 9, arr[lMin[i - 1]] = 3

Math.min(9, 3) = 3, hence `lMin[2] = lMin[i-1] = 1`.

lMin becomes [0, 1, 1, 0, 0, 0, 0]

i = 3

arr[i] = 2, arr[lMin[i - 1]] = 3

Math.min(2, 3) = 3, hence `lMin[3] = i = 3`.

lMin becomes [0, 1, 1, 3, 0, 0, 0]

Likewise, we continue for i = 4 to 6, and lMin becomes [0, 1, 1, 3, 4, 4, 6].

Backward pass to fill rMax

When we run the forward pass, and initiate rMax. rMax[6] is 6. i = 5

arr[i] = 11, arr[rMax[i + 1]] = 0

Math.max(11, 0) = 11, hence rMax[5] = i = 5. 

rMax becomes [0, 0, 0, 0, 0, 5, 6]

i = 4

arr[i] = 1, arr[rMax[i + 1]] = 11

Math.max(1, 11) = 11, hence `rMax[4] = rMax[i+1] = 5`.

rMax becomes [0, 0, 0, 0, 5, 5, 6]

i = 3

arr[i] = 2, arr[rMax[i + 1]] = 11

Math.max(2, 11) = 11, hence `rMax[3] = rMax[i+1] = 5`.

rMax becomes [0, 0, 0, 5, 5, 5, 6]

Likewise, we continue for i = 2 to 0, and rMax becomes [5, 5, 5, 5, 5, 5, 6].

Calculate maxDiff
arr =    [7, 3, 9, 2, 1, 11, 0]
lMin =   [0, 1, 1, 3, 4, 4, 6]
rMax =   [5, 5, 5, 5, 5, 5, 6]
indices = 0  1  2  3  4  5  6
maxDiff = -1;

i = 0

lMin[i] = 0, rMax[i] = 5
is lMin[i] < rMax[i]? Yes
maxDiff = max(-1, rMax[i] - lMax[i]) = max(-1, 5) = 5

i = 1

lMin[i] = 1, rMax[i] = 5
is lMin[i] < rMax[i]? Yes
maxDiff = max(5, rMax[i] - lMax[i]) = max(5, 4) = 5

Similarly, we continue. And for us i = 0, j = 5 is the solution, where we have maxDiff being maximum.