Maximum Width Ramp: Stack-Based Optimal Pairs

LeetCode 962, Maximum Width Ramp, is a medium problem that asks you to find the widest pair of indices where the left value does not exceed the right value. It looks like it should be solvable with two pointers or sorting, but the cleanest O(n) solution uses a decreasing stack with a right-to-left sweep. Once you see why this works, the pattern clicks and you can apply it to a whole family of "find the optimal pair" problems.

The problem

Given an integer array nums, a ramp is a pair (i, j) where i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Return the maximum width of a ramp in the array, or 0 if no ramp exists.

Input:  [6, 0, 8, 2, 1, 5]
Output: 4

The best ramp is (i=1, j=5). We have nums[1]=0 <= nums[5]=5, and the width is 5 - 1 = 4. There are other valid ramps like (0, 2) with width 2, but none wider than 4.

Why this problem matters

The Maximum Width Ramp is a clean example of a two-phase stack algorithm. Unlike most monotonic stack problems where you build and consume the stack in a single pass, this one separates the two operations: first you build the stack going left to right, then you consume it going right to left. Understanding this separation gives you a tool for problems where scanning in one direction is not enough.

This pattern appears in optimization problems where you need to find the best pair (i, j) subject to some constraint. Stock trading problems, scheduling problems, and range-query problems all have variants where you need to match a "good left endpoint" with a "good right endpoint" that is as far away as possible. The decreasing stack gives you the set of all potentially useful left endpoints, and the right-to-left sweep finds the best match for each one.

The problem also teaches an important lesson about greedy elimination. When scanning from right to left, once you pop an index from the stack, you know that no future (smaller) value of j can do better with that index. This "pop and forget" property is what makes the algorithm O(n) instead of O(n^2).

The brute force approach

The most direct approach is to check every pair (i, j) where i < j:

def max_width_ramp_brute(nums):
    n = len(nums)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] <= nums[j]:
                best = max(best, j - i)
    return best

This works, but the nested loops give O(n^2) time. For an array of 50,000 elements, that is 1.25 billion comparisons in the worst case. The problem constraints allow up to 50,000 elements, so brute force will time out.

The problem with brute force is that it does not exploit any structure. For each i, it scans all possible j values without knowing which ones are worth checking. We need a way to narrow down the candidates.

The key insight

The trick is to split the problem into two phases. First, identify which indices are worth considering as the left endpoint i of a ramp. Second, find the best right endpoint j for each of those candidates.

Which indices make good left endpoints? Only those that form a strictly decreasing sequence of values from left to right. If nums[a] <= nums[b] and a < b, then a is always a better or equal left endpoint than b (it is further left and its value is no larger). So you never need b as a left endpoint if a exists.

Build a stack of these candidates by scanning left to right and only pushing when the value is strictly less than the current top. Then scan from right to left: for each j, pop from the stack as long as nums[stack[-1]] <= nums[j], recording j - stack[-1] as a candidate width.

Walking through it step by step

The solution

def max_width_ramp(nums):
    n = len(nums)
    stack = []

    for i in range(n):
        if not stack or nums[i] < nums[stack[-1]]:
            stack.append(i)

    best = 0
    for j in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] <= nums[j]:
            best = max(best, j - stack.pop())

    return best

Here is what each piece does:

1. Build the decreasing stack. Walk left to right. Push index i only if nums[i] is strictly less than the value at the current top of the stack (or the stack is empty). This gives you every index that could possibly be the left endpoint of an optimal ramp.
2. Sweep right to left. Starting from the last index, check if nums[j] is greater than or equal to the value at the top of the stack. If so, pop the top, compute the width j - popped_index, and update the best. Keep popping as long as the condition holds.
3. Return the best width. After the sweep, best holds the maximum width ramp found, or 0 if no ramp exists.

The reason the right-to-left sweep works is that once you pop an index i at position j, no smaller value of j can produce a wider ramp with i. Since we process j values from largest to smallest, the first time we pop i is guaranteed to give us the widest ramp for that particular i.

Complexity analysis

The first loop runs in O(n) and pushes at most n indices. The second loop also runs in O(n) for the outer iteration, and the inner while loop pops each index at most once. Since each index is pushed once and popped at most once, the total work across both phases is O(n).

The space is O(n) for the stack, which in the worst case (a strictly decreasing array) holds all n indices.

Building blocks

1. Decreasing candidate stack

The first phase builds a stack of candidate left endpoints:

stack = []
for i in range(n):
    if not stack or nums[i] < nums[stack[-1]]:
        stack.append(i)

This pattern filters out indices that are "dominated" by earlier ones. If a < b and nums[a] <= nums[b], then a is always at least as good as b for the left endpoint, so b is unnecessary. The resulting stack contains only the indices where the value is strictly decreasing, and these are the only candidates worth checking.

2. Right-to-left greedy matching

The second phase sweeps from right to left and greedily pops from the stack:

best = 0
for j in range(n - 1, -1, -1):
    while stack and nums[stack[-1]] <= nums[j]:
        best = max(best, j - stack.pop())

This is the "consume" phase. By scanning j from right to left, you guarantee that the first time you can match a stack entry, you get the widest possible ramp for it. Once popped, the entry is gone because no future j (which is smaller) could do better.

Edge cases

Before submitting, verify your solution handles:

• Strictly decreasing array like [5, 4, 3, 2, 1]: no valid ramp exists. Every pair has nums[i] > nums[j]. Return 0. The stack holds all indices but nothing gets popped.
• Strictly increasing array like [1, 2, 3, 4, 5]: the best ramp is (0, 4) with width 4. Only index 0 goes on the stack, and it gets popped immediately at j=4.
• All equal values like [3, 3, 3, 3]: any pair is valid. The best ramp is (0, 3) with width 3.
• Two elements [1, 2]: width 1. [2, 1]: width 0.
• Single element [5]: no pair exists, return 0.
• Ramp at the edges like [1, 9, 8, 7, 6, 2]: the best ramp is (0, 5) with width 5, since nums[0]=1 <= nums[5]=2.

Common mistakes

1. Using < instead of <= in the stack-building phase. You should push when the value is strictly less than the top. Using <= would include duplicate values that cannot improve the answer as left endpoints.

2. Scanning left to right in the second phase. The right-to-left sweep is essential. If you scan left to right, popping an entry does not guarantee you found the best j for it, because a larger j might exist later.

3. Forgetting to pop inside the while loop. Some people check the top of the stack but forget to pop it, leading to an infinite loop. The pop is what makes progress and ensures O(n) total work.

4. Using a max-heap or sorting instead of a stack. While sorting-based approaches can work, they typically run in O(n log n) and are harder to implement correctly. The stack approach is both simpler and faster.

5. Confusing this with a sliding window problem. The ramp condition nums[i] <= nums[j] is not a window constraint. Sliding window assumes you can shrink from the left when a condition breaks, but here the valid pairs are not contiguous.

From understanding to recall

You have seen the two-phase stack algorithm: build a decreasing stack of candidate left endpoints, then sweep right to left to find the widest match. The logic is clean and the code is short. But writing it from scratch under time pressure requires you to remember several details: the strict less-than check during the build phase, the right-to-left direction of the sweep, and the pop-and-compare loop.

These are exactly the kinds of details that fade after a week or two. Spaced repetition is the fix. By revisiting this pattern at increasing intervals, you turn "I vaguely remember a two-pass stack trick" into "I can write this in 60 seconds." The building blocks transfer to other problems too. Any time you need to find optimal pairs with index-distance constraints, the decreasing-candidate-stack pattern is your starting point.

Related posts

• Daily Temperatures - Classic monotonic stack problem
• Online Stock Span - Another stack-based streaming problem
• Largest Rectangle in Histogram - Stack pattern for finding optimal ranges

CodeBricks breaks the two-phase stack pattern into its reusable pieces and drills them separately. You practice building the decreasing candidate stack, then practice the right-to-left sweep, until each piece is automatic. When Maximum Width Ramp or a similar "find the widest valid pair" problem appears in an interview, the code flows without hesitation.