Get started

Maximum Index — Medium Problem & Solution

Given an array arr, find the maximum value of j - i over all pairs of indices with i <= j and arr[i] <= arr[j]. Return that maximum difference.

  • Difficulty: Medium
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Adobe, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array arr, find the maximum value of j - i over all pairs of indices with i <= j and arr[i] <= arr[j].

Return that maximum difference. It is always at least 0, since i == j always qualifies.

Example 1

Input: arr = [34,8,10,3,2,80,30,33,1]
Output: 6
Explanation: arr[1] = 8 and arr[7] = 33 give j - i = 6.

Example 2

Input: arr = [1,2,3,4,5,6]
Output: 5
Explanation: The first and last elements already satisfy the condition.

Example 3

Input: arr = [9,2,3,4,5,6,7,8,18,0]
Output: 8
Explanation: arr[0] = 9 and arr[8] = 18.

Constraints

  • 1 <= arr.length <= 100000
  • 0 <= arr[i] <= 1000000000

How to solve Maximum Index

Replace each index by the best value it can offer: on the left, the running minimum (a smaller left value can only help); on the right, the running maximum. Both sequences are monotone, so a single two-pointer sweep finds the widest valid gap.

Approach

  1. Build leftMin, where leftMin[i] = min(arr[0..i]) — non-increasing.
  2. Build rightMax, where rightMax[j] = max(arr[j..n-1]) — non-increasing.
  3. Walk i and j from 0. While leftMin[i] <= rightMax[j], the pair is feasible: record j - i and advance j.
  4. Otherwise advance i, since no larger j will help this i.

Why it works

If leftMin[i] <= rightMax[j] then some i' <= i and j' >= j satisfy the original condition with an even wider gap, so recording j - i never overestimates. When the test fails, leftMin[i] is too large for every rightMax at or beyond j (that sequence only shrinks), so i is exhausted.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Advancing j when the test fails — it is i that must move on.
  • Answering -1 when no pair works; i == j always works, so the floor is 0.

Reference solution

Python

from typing import List

def maxIndexDiff(arr: List[int]) -> int:
    n = len(arr)
    left_min = [0] * n
    right_max = [0] * n
    left_min[0] = arr[0]
    for i in range(1, n):
        left_min[i] = min(left_min[i - 1], arr[i])
    right_max[n - 1] = arr[n - 1]
    for j in range(n - 2, -1, -1):
        right_max[j] = max(right_max[j + 1], arr[j])
    i = j = 0
    best = 0
    while i < n and j < n:
        if left_min[i] <= right_max[j]:
            best = max(best, j - i)
            j += 1
        else:
            i += 1
    return best

JavaScript

var maxIndexDiff = function(arr) {
    var n = arr.length;
    var leftMin = [], rightMax = [];
    for (var t = 0; t < n; t++) { leftMin.push(0); rightMax.push(0); }
    leftMin[0] = arr[0];
    for (var i = 1; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1], arr[i]);
    rightMax[n - 1] = arr[n - 1];
    for (var j = n - 2; j >= 0; j--) rightMax[j] = Math.max(rightMax[j + 1], arr[j]);
    var p = 0, q = 0, best = 0;
    while (p < n && q < n) {
        if (leftMin[p] <= rightMax[q]) {
            if (q - p > best) best = q - p;
            q++;
        } else p++;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue