Introduction

The problem is to find indices i and j such that V[j] is greater than V[i] and the distance j - i is as large as possible. A quadratic scan works, but there is a standard linear-time solution that is much better for large arrays.

Why the Naive Solution Is Too Slow

The direct approach checks every pair:

• choose i
• try every j to the right
• keep the best valid distance

That costs O(n^2), which is fine for tiny inputs but quickly becomes expensive.

1def max_gap_bruteforce(values):
2    best = (-1, -1, -1)
3
4    for i in range(len(values)):
5        for j in range(i + 1, len(values)):
6            if values[j] > values[i] and j - i > best[0]:
7                best = (j - i, i, j)
8
9    return best

We want something closer to one pass through the data.

The Linear-Time Idea

The efficient solution separates the comparison into two helper arrays:

• 'left_min[i] is the smallest value seen from the left up to index i'
• 'right_max[j] is the largest value seen from index j to the end'

Once those arrays exist, use two pointers:

• start i at the left
• start j at the left
• if left_min[i] is less than right_max[j], the condition can be satisfied, so update the answer and move j
• otherwise move i

This works because left_min summarizes the best candidate on the left and right_max summarizes the best candidate on the right.

Building the Helper Arrays

1def build_left_min(values):
2    left_min = [0] * len(values)
3    left_min[0] = values[0]
4
5    for i in range(1, len(values)):
6        left_min[i] = min(left_min[i - 1], values[i])
7
8    return left_min
9
10
11def build_right_max(values):
12    right_max = [0] * len(values)
13    right_max[-1] = values[-1]
14
15    for j in range(len(values) - 2, -1, -1):
16        right_max[j] = max(right_max[j + 1], values[j])
17
18    return right_max

These arrays cost O(n) time and O(n) extra memory. After that, the final scan is also linear.

Full Working Solution

The version below returns both the maximum distance and one valid pair of indices.

1def max_index_gap(values):
2    if len(values) < 2:
3        return -1, -1, -1
4
5    n = len(values)
6    left_min_index = [0] * n
7    right_max_index = [0] * n
8
9    min_idx = 0
10    for i in range(n):
11        if values[i] < values[min_idx]:
12            min_idx = i
13        left_min_index[i] = min_idx
14
15    max_idx = n - 1
16    for j in range(n - 1, -1, -1):
17        if values[j] > values[max_idx]:
18            max_idx = j
19        right_max_index[j] = max_idx
20
21    i = 0
22    j = 0
23    best_gap = -1
24    best_pair = (-1, -1)
25
26    while i < n and j < n:
27        left_idx = left_min_index[i]
28        right_idx = right_max_index[j]
29
30        if values[right_idx] > values[left_idx]:
31            if right_idx - left_idx > best_gap:
32                best_gap = right_idx - left_idx
33                best_pair = (left_idx, right_idx)
34            j += 1
35        else:
36            i += 1
37
38    return best_gap, best_pair[0], best_pair[1]
39
40
41data = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]
42print(max_index_gap(data))

For this input, the best answer uses the smallest useful value on the left and the farthest larger value on the right.

Why It Works

The two-pointer scan is efficient because left_min_index[i] never hides a better left candidate. If the smallest value seen so far on the left cannot form a valid pair with the best possible right-side value at j, then no later left index summarized by that prefix will help, so moving i is safe.

Likewise, when the condition succeeds, moving j is safe because a farther right position might increase the gap.

That monotonic movement is what keeps the scan linear.

Alternative View: Prefix Minima and Suffix Maxima

Many explanations write the solution using value arrays only, then reconstruct indices later. That is fine if you only need the maximum gap. If you also need the actual indices, storing the best prefix-minimum index and suffix-maximum index directly is cleaner.

If duplicates matter, be explicit about the comparison. The title says V[j] must be greater than V[i], not greater than or equal to it, so the test should remain strict.

Common Pitfalls

Using >= instead of > changes the problem and can return a different pair than the one requested.

Building left_min and right_max with values but forgetting how to recover the original indices leads to an incomplete answer.

Trying to move both pointers on every iteration usually breaks the invariant and misses valid long-distance pairs.

Falling back to sorting destroys the original index positions unless you do extra bookkeeping, and it is unnecessary here anyway.

Summary

• The brute-force solution is O(n^2), but the standard optimized solution is O(n).
• Build prefix-minimum information from the left and suffix-maximum information from the right.
• Use two pointers to scan for the farthest valid pair.
• Keep the comparison strict because the condition is "greater than," not "greater than or equal to."
• Store indices, not just values, if you need the actual pair as output.