# 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:

```python
i < j
nums[i] <= nums[j]
```

The width of the ramp is:

```python
j - i
```

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

The official constraints are:

| Constraint | Value |
|---|---|
| `nums.length` | `2 <= nums.length <= 5 * 10^4` |
| `nums[i]` | `0 <= nums[i] <= 5 * 10^4` |

Source: LeetCode problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum width `j - i` among valid ramps |
| Ramp condition | `i < j` and `nums[i] <= nums[j]` |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
4
```

The best ramp is:

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

Since `0 <= 5`, the width is:

```python
5 - 1 = 4
```

Example 2:

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

Output:

```python
7
```

The best ramp is:

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

Since `1 <= 1`, the width is:

```python
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`.

```python
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:

```python
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:

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

This creates a stack of indices with strictly decreasing values.

Example:

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

The candidate stack becomes:

```python
[0, 1]
```

because:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is pushed at most once and popped at most once |
| Space | `O(n)` | The stack may store many candidate start indices |

## Implementation

```python
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:

```python
stack = []
```

Then we scan from left to right:

```python
for i, value in enumerate(nums):
```

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

```python
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:

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

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

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

If the condition holds, we found a valid ramp.

We pop the start index:

```python
i = stack.pop()
```

and update the answer:

```python
answer = max(answer, j - i)
```

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

Finally:

```python
return answer
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[6,0,8,2,1,5]` | Official example with width `4` |
| `[9,8,1,0,1,9,4,0,4,1]` | Official example with equal endpoint values |
| Increasing array | Maximum width is full range |
| Decreasing array | No valid ramp |
| All equal values | Equality is allowed |
| `[3,1,2]` | Best ramp starts in the middle |
| `[2,2,1]` | Equal adjacent values form a ramp |