Maximum Width Ramp LeetCode 962 Guide

LeetCode 962 — Maximum Width Ramp — gives you an integer array nums. A ramp is a pair (i, j) where i < j and nums[i] <= nums[j]. The width of the ramp is j - i. Return the maximum width of a ramp in the array, or 0 if no ramp exists.

The brute force approach checks all O(n^2) pairs, which is too slow for n up to 50,000. We need to identify which pairs are worth checking. The key observation: the optimal left endpoint i must be a "prefix minimum" — no earlier index has a smaller value.

This leads to a two-phase algorithm: build a monotonic decreasing stack of candidate left indices, then scan from right to left, popping candidates that form valid ramps. The widest ramp found is the answer.

Scan nums from left to right. Push index 0 onto the stack. For each subsequent index i, push i only if nums[i] is strictly less than nums[stack.top()]. This builds a monotonically decreasing stack of values.

Why only push decreasing values? If nums[i] >= nums[j] where j is already on the stack and j < i, then j is a better left endpoint than i for any future right endpoint. It has both a smaller or equal value and an earlier position. So i is dominated and never useful.

After this phase, the stack contains all "prefix minimum" indices — positions where the value is smaller than all previous values. These are the only candidates that could be the left endpoint of a maximum-width ramp.

Scan nums from right to left (j = n-1 down to 0). For each j, while the stack is non-empty and nums[j] >= nums[stack.top()], pop the top index i and update the answer with j - i. Continue popping as long as the condition holds.

Why scan right to left? We want the widest possible ramp, so we try the largest j values first. When we find a valid (i, j) pair, index i is consumed (popped) because no later j (which is smaller) could produce a wider ramp with i.

Why is it safe to pop? Once we process index j with stack top i, any future j' < j would give a narrower ramp with i. So i's best partner is the current j (or an earlier one that already popped it). Popping is irreversible and correct.

Consider nums = [6, 0, 8, 2, 1, 5]. Phase 1: push 0 (val 6). i=1: 0 < 6, push 1. i=2: 8 > 0, skip. i=3: 2 > 0, skip. i=4: 1 > 0, skip. i=5: 5 > 0, skip. Stack: [0, 1] (indices with values [6, 0]).

Phase 2: j=5, val=5. Stack top is 1 (val 0). 5 >= 0, pop, ramp = 5-1 = 4. Stack top is 0 (val 6). 5 < 6, stop. j=4, val=1. Stack top 0 (val 6). 1 < 6, skip. j=3, val=2. 2 < 6, skip. j=2, val=8. 8 >= 6, pop, ramp = 2-0 = 2. Stack empty.

Maximum ramp = max(4, 2) = 4 (pair i=1, j=5: nums[1]=0 <= nums[5]=5, width=4). This matches the expected answer.

In Python, phase 1: stack = [0]. For i in range(1, n), if nums[i] < nums[stack[-1]], append i. Phase 2: result = 0. For j in range(n-1, -1, -1), while stack and nums[j] >= nums[stack[-1]], result = max(result, j - stack.pop()). Return result.

In Java, use an ArrayDeque<Integer> for the stack. The logic is identical. Phase 1 pushes decreasing indices. Phase 2 scans right-to-left and pops while nums[j] >= nums[stack.peek()]. Track the maximum width.

A common alternative approach sorts indices by value and scans for maximum j - minimum i seen so far. This also runs in O(n log n) due to sorting. The stack approach is O(n) and more elegant, making it the preferred interview solution.

Time complexity is O(n). Phase 1 scans left to right in O(n). Phase 2 scans right to left in O(n). Each index is pushed at most once and popped at most once. Total operations: at most 2n pushes/pops plus 2n comparisons.

Space complexity is O(n) for the stack. In the worst case (strictly decreasing array), all n indices are pushed. In practice, the stack is smaller because only prefix minimums are stored.

This is optimal — any algorithm must examine each element at least once to determine if it participates in a ramp. The monotonic stack achieves this lower bound with a clean two-phase structure.

Trapping Rain Water (LeetCode 42) and Largest Rectangle in Histogram (LeetCode 84) both use monotonic stacks with two-phase reasoning. Maximum Width Ramp adds the twist of scanning right-to-left in the second phase, which is unique among common stack problems.

Maximum Distance in Arrays (LeetCode 624) solves a similar "maximize j - i" problem but across multiple arrays. The approach differs (greedy tracking of min/max) but the goal is analogous — finding the widest valid pair.

Online Stock Span (LeetCode 901) and Sum of Subarray Minimums (LeetCode 907) are other monotonic stack problems that process elements based on their relationship to stack contents. Together with Maximum Width Ramp, they form a comprehensive stack practice set.