LeetCode 962: Maximum Width Ramp

Problem Restatement

We are given an integer array nums.

A ramp is a pair of indices (i, j) such that:

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

The width of the ramp is:

j - i

Return the maximum possible width of a ramp. If no valid ramp exists, return 0.

The official constraints are:

Source: LeetCode problem statement.

Input and Output

Example function shape:

def maxWidthRamp(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Output:

4

The best ramp is:

i = 1
j = 5
nums[i] = 0
nums[j] = 5

Since 0 <= 5, the width is:

5 - 1 = 4

Example 2:

nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]

Output:

7

The best ramp is:

i = 2
j = 9
nums[i] = 1
nums[j] = 1

Since 1 <= 1, the width is:

9 - 2 = 7

First Thought: Check Every Pair

The direct solution is to try every pair (i, j).

For each i, check every later j.

for i in range(n):
    for j in range(i + 1, n):
        if nums[i] <= nums[j]:
            answer = max(answer, j - i)

This is correct, but too slow.

With up to 5 * 10^4 numbers, O(n^2) pair checking is not acceptable.

Key Insight

For a ramp (i, j), we want i as far left as possible and j as far right as possible.

Not every index is useful as a starting index.

Suppose we have two indices a < b and:

nums[a] <= nums[b]

Then b is never better than a as a ramp start.

Why?

For any future j, if nums[b] <= nums[j], then nums[a] <= nums[j] is also true, and a gives a wider ramp because a < b.

So we only keep indices whose values form a strictly decreasing sequence from left to right.

These are the only useful start candidates.

Monotonic Stack

Build a stack of candidate starting indices.

Scan from left to right.

Push index i only if its value is smaller than the value at the current stack top:

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

This creates a stack of indices with strictly decreasing values.

Example:

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

The candidate stack becomes:

[0, 1]

because:

nums[0] = 6
nums[1] = 0

Index 2 has value 8, so it is not useful as a start because index 0 is earlier and smaller or equal for ramp purposes is not true here, but index 2 is too large and too far right to improve as a starting candidate. Index 3, 4, and 5 are also not smaller than 0.

Finding the Best End Index

After building the stack, scan from right to left.

For each ending index j, check whether it can pair with the smallest-value candidate on top of the stack:

while stack and nums[stack[-1]] <= nums[j]:
    answer = max(answer, j - stack[-1])
    stack.pop()

Why pop?

Once index i forms a valid ramp with the current j, this is the widest ramp it can ever get, because we are scanning j from right to left.

Any future j will be smaller, so it cannot produce a larger width for the same i.

Algorithm

1. Create an empty stack.
2. Scan nums from left to right.
3. Push index i only when it creates a new lower value than all previous stack candidates.
4. Initialize answer = 0.
5. Scan nums from right to left.
6. While the current right index j can form a ramp with the stack top:
   • update the answer
   • pop that start index
7. Return answer.

Correctness

We first show that every useful start index is kept in the stack.

If an index i is not pushed, then there is an earlier index k < i with nums[k] <= nums[i]. For any valid ramp starting at i and ending at j, we also have nums[k] <= nums[i] <= nums[j]. Therefore, (k, j) is also a valid ramp and has larger width. So index i can never be needed for an optimal answer.

Thus, the stack contains all possible start indices that could lead to a maximum-width ramp.

Next, the second pass scans ending indices from right to left. When a start index i on the stack can form a valid ramp with current index j, this j is the rightmost remaining endpoint for i. Therefore, j - i is the largest width that start index i can achieve.

After computing that width, popping i is safe because no later scan step can give it a larger width.

The algorithm checks every relevant start index against the farthest possible valid endpoint. Therefore, the maximum width found is exactly the maximum width ramp.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def maxWidthRamp(self, nums: list[int]) -> int:
        stack = []

        for i, value in enumerate(nums):
            if not stack or value < nums[stack[-1]]:
                stack.append(i)

        answer = 0

        for j in range(len(nums) - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[j]:
                i = stack.pop()
                answer = max(answer, j - i)

        return answer

Code Explanation

We create a stack of possible left endpoints:

stack = []

Then we scan from left to right:

for i, value in enumerate(nums):

We only push a new index if it has a smaller value than the current best candidates:

if not stack or value < nums[stack[-1]]:
    stack.append(i)

This keeps the stack values strictly decreasing.

Then we scan from right to left:

for j in range(len(nums) - 1, -1, -1):

For the current right endpoint j, we check candidate starts from the stack:

while stack and nums[stack[-1]] <= nums[j]:

If the condition holds, we found a valid ramp.

We pop the start index:

i = stack.pop()

and update the answer:

answer = max(answer, j - i)

Popping is safe because this is the widest possible ramp for that start index.

Finally:

return answer

Testing

def run_tests():
    s = Solution()

    assert s.maxWidthRamp([6, 0, 8, 2, 1, 5]) == 4
    assert s.maxWidthRamp([9, 8, 1, 0, 1, 9, 4, 0, 4, 1]) == 7

    assert s.maxWidthRamp([1, 2, 3, 4, 5]) == 4
    assert s.maxWidthRamp([5, 4, 3, 2, 1]) == 0
    assert s.maxWidthRamp([1, 1, 1, 1]) == 3
    assert s.maxWidthRamp([3, 1, 2]) == 1
    assert s.maxWidthRamp([2, 2, 1]) == 1

    print("all tests passed")

run_tests()

Test meaning: