Maximum Width Ramp — Two-Pass Monotonic Stack for Maximum Index Distance

Problem Statement#

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

Constraints:

• 2 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 5 * 10^4

Input:  nums = [6,0,8,2,1,5]
Output: 4
Explanation: Ramp (i=1, j=5): nums[1]=0 <= nums[5]=5, width=4.

Input:  nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: Ramp (i=2, j=9): nums[2]=1 <= nums[9]=1, width=7.

Why This Problem Matters#

Maximum Width Ramp is a medium problem that is genuinely tricky. The brute force is O(n²), but the constraint (n up to 50,000) requires an O(n) or O(n log n) solution. The monotonic stack approach is elegant and reusable: this same two-pass "build candidate stack then scan from the other end" pattern appears in other maximum-width problems.

Amazon asks this type of problem to test whether you can recognize that a two-pass approach can achieve O(n) when the direct one-pass approach fails. The insight — that the best left endpoints form a decreasing subsequence, and the best right endpoints should be matched from the right — is the kind of non-obvious reasoning that separates candidates who have studied patterns from those who have not.

The Core Insight#

We want to maximize j - i such that nums[i] <= nums[j] and i < j.

Key observation about candidate left endpoints: Only indices with strictly decreasing values are interesting as left endpoints. If nums[a] >= nums[b] for a < b, then a is always at least as good a left endpoint as b for any j >= b — it gives a wider ramp whenever it's valid. So discard b from the candidate set.

This means: the candidate left endpoints form a strictly decreasing subsequence of values. Build these with a stack where we only push index i if nums[i] < nums[stack[-1]].

Scanning for right endpoints: Once we have our decreasing candidate stack, scan from RIGHT to LEFT. For each j, while nums[stack_top] <= nums[j], update ans = max(ans, j - stack_top) and POP. The pop is safe because any future j' < j would give a smaller width using the same left endpoint — we already have the best answer for it.

Visual Dry Run#

Input: nums = [6, 0, 8, 2, 1, 5]

Phase 1 — Build decreasing candidate stack:

Candidate stack: [0, 1] with values [6, 0].

Phase 2 — Scan right to left:

Result: 4.

Solution (Optimal)#

class Solution:
    def maxWidthRamp(self, nums: list[int]) -> int:
        n = len(nums)
        stack = []
 
        # Phase 1: Build decreasing candidate left endpoints
        for i in range(n):
            if not stack or nums[i] < nums[stack[-1]]:
                stack.append(i)
 
        ans = 0
 
        # Phase 2: Scan right to left, match candidates greedily
        for j in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[j]:
                ans = max(ans, j - stack.pop())
 
        return ans

var maxWidthRamp = function(nums) {
    const n = nums.length;
    const stack = [];
 
    for (let i = 0; i < n; i++) {
        if (stack.length === 0 || nums[i] < nums[stack[stack.length - 1]]) {
            stack.push(i);
        }
    }
 
    let ans = 0;
 
    for (let j = n - 1; j >= 0; j--) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[j]) {
            ans = Math.max(ans, j - stack.pop());
        }
    }
 
    return ans;
};

Time: O(n) — two linear passes; total push/pop operations bounded by n Space: O(n) — stack holds at most n indices

Common Mistakes#

• Trying a single-pass approach — there is no obvious single-pass O(n) algorithm; recognizing that two passes are needed is part of the insight
• Not popping in Phase 2 — this produces correct answers but wastes work; the pop is safe because smaller j values can only give smaller widths for the same left endpoint
• Scanning left-to-right in Phase 2 instead of right-to-left — left-to-right finds the smallest valid j (minimum width), not the maximum; right-to-left maximizes the width
• Wrong Phase 1 condition — only push if strictly less than the current stack top; using <= is harmless but unnecessary since equal values produce equal-width ramps from the same right endpoint

Interview Tips#

• Frame the problem as: "I need the leftmost valid left endpoint paired with the rightmost valid right endpoint for the widest pair." This motivates the two-pass approach.
• Explain Phase 1: "I build a decreasing stack of candidate left endpoints — these are the only interesting left endpoints. If nums[a] > nums[b] for a < b, then a gives a wider ramp than b whenever a is valid, so b is never better."
• Explain Phase 2: "I scan from the right. For the rightmost j, I match as many left endpoints as I can, recording each width. Once matched, I pop the left endpoint — no smaller j can give a better width using the same left."

Follow-up Questions#

• What if the condition is strict: nums[i] < nums[j]? Change Phase 2 condition to nums[stack[-1]] < nums[j]. Phase 1 is unchanged.
• Can you solve this in O(n log n) using binary search? Yes: build the decreasing candidate stack (O(n)), then for each j from n-1 to 0, binary search the stack for the smallest valid left endpoint. Each search is O(log n).
• What if you want the minimum width ramp? Simpler: scan left to right with the monotonic stack, and for each position check if it can pair with the most recent candidate (nearest left endpoint).

Key Takeaways#

• For maximum index distance satisfying a condition, use a two-pass approach: build decreasing candidate left endpoints, then scan right-to-left matching them.
• The pop in Phase 2 is safe because the current j gives the best width for that left endpoint, and smaller j values will only give smaller widths.
• Only strictly decreasing-value indices are interesting left endpoints — any index with a value >= a later index can never give a wider ramp than the later index.
• Phase 1 builds the candidate stack in O(n); Phase 2 matches in O(n) amortized since each element is popped at most once.
• This two-pass "candidate stack then reverse scan" pattern generalizes to other "maximum index gap satisfying a monotone condition" problems.
• The O(n log n) alternative using binary search on the candidate stack is also valid and easier to implement in an interview if the O(n) insight is not immediately obvious.
• Right-to-left scanning in Phase 2 is essential for maximizing width — left-to-right scanning would minimize it instead.