LeetCode 962 - Maximum Width Ramp

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Stack, Monotonic Stack

Solution

Problem Understanding

The problem asks us to find the maximum width ramp in an array of integers. A ramp is defined as a pair of indices (i, j) such that:

i < j
nums[i] <= nums[j]

The width of the ramp is simply the distance between the two indices:

$$\text{width} = j - i$$

Our goal is to compute the largest possible width among all valid ramps in the array.

The input is an integer array nums, and the output is a single integer representing the maximum width ramp. If no valid ramp exists, we return 0.

The constraints are important:

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

An array size of up to 50,000 elements immediately tells us that quadratic solutions will likely be too slow. An O(n^2) algorithm would require up to 2.5 billion comparisons in the worst case, which is not feasible within standard LeetCode time limits. This strongly suggests that we need an O(n log n) or O(n) solution.

Several edge cases are worth identifying early:

Strictly decreasing arrays, such as [5,4,3,2,1], contain no valid ramp except trivial invalid cases, so the answer is 0.
Strictly increasing arrays, such as [1,2,3,4,5], produce the maximum possible width, which is n - 1.
Arrays with duplicate values are important because equality is allowed, meaning nums[i] <= nums[j] includes equal values.
Very small arrays of length 2 should still behave correctly.
Large plateaus of identical numbers can create wide ramps that naive implementations might miss if they only search for strictly increasing values.

Approaches

Brute Force Approach

The most direct solution is to check every possible pair (i, j) where i < j.

For every index i, we iterate through every later index j. If nums[i] <= nums[j], we compute the width j - i and update the maximum answer.

This works because it explicitly examines every possible ramp and therefore cannot miss the optimal one.

However, the time complexity is extremely poor. There are approximately:

$$\frac{n(n-1)}{2}$$

pairs to check, which gives an O(n^2) time complexity.

With n = 50,000, this approach becomes far too slow.

Optimal Monotonic Stack Approach

The key insight is that not every index is useful as a left endpoint.

Suppose we have two indices:

i1 < i2
nums[i1] <= nums[i2]

Then i2 is never better than i1 as the left side of a ramp, because:

i1 is farther left
i1 has an equal or smaller value

Any valid ramp using i2 could produce an equal or larger width using i1.

This means we only care about indices that form new minimum values as we scan from left to right.

We can store these candidate indices in a monotonic decreasing stack. The stack contains indices whose values strictly decrease as we move through the array.

Then we scan from right to left. For each position j, we try to match it with the earliest possible valid left endpoint from the stack.

Whenever:

$$nums[\text{stack[-1]}] \le nums[j]$$

we have found a valid ramp, and because we are scanning from right to left, this gives the widest possible ramp for that left index.

This produces an O(n) solution because each index is pushed and popped at most once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair of indices
Optimal	O(n)	O(n)	Uses a monotonic decreasing stack

Algorithm Walkthrough

Optimal Algorithm

Create an empty stack that will store candidate left indices.

The stack will maintain indices whose values are strictly decreasing. These are the only indices worth considering as ramp starting points. 2. Scan t