Problem Description

You are given an integer array nums. A ramp is defined as a pair of indices (i, j) where:

• i < j (i comes before j in the array)
• nums[i] <= nums[j] (the value at index i is less than or equal to the value at index j)

The width of a ramp is calculated as j - i (the distance between the two indices).

Your task is to find the maximum width among all possible ramps in the array. If no valid ramp exists in nums, return 0.

For example:

• If nums = [6, 0, 8, 2, 1, 5], a valid ramp would be (i=1, j=5) because nums[1] = 0 <= nums[5] = 5, giving a width of 5 - 1 = 4.
• Another valid ramp would be (i=0, j=2) because nums[0] = 6 <= nums[2] = 8, giving a width of 2 - 0 = 2.

The solution uses a monotonic stack approach:

1. First, build a decreasing monotonic stack by iterating through the array and only adding indices where the value is smaller than the previous stack top. This creates a list of potential starting points for ramps.
2. Then, iterate from right to left through the array. For each position, check if it can form a valid ramp with indices in the stack (where the stack value is less than or equal to current value). Pop elements from the stack when valid ramps are found and track the maximum width.
3. The key insight is that once an index from the stack is used as the start of a ramp, it can be removed since any future ramp using that starting point would have a smaller width.

Intuition

To find the maximum width ramp, we need to find indices i and j where i < j and nums[i] <= nums[j], maximizing j - i.

The key observation is that for any starting position i of a ramp, we want to find the rightmost j where nums[j] >= nums[i]. This naturally suggests we should process the array from right to left when looking for ending positions.

But which indices should we consider as potential starting positions? If we have two indices i1 < i2 where nums[i1] <= nums[i2], then i1 is always a better choice as a starting position because:

• Any j that forms a valid ramp with i2 will also form a valid ramp with i1 (since nums[i1] <= nums[i2] <= nums[j])
• The width j - i1 will always be greater than j - i2

This means we only need to consider indices as potential starting positions if they have values smaller than all previous indices. These indices form a decreasing sequence.

Why use a stack? As we traverse from right to left looking for ending positions:

• When we find a valid ramp with starting position i, we can remove i from consideration because any future j (to the left) would give a smaller width
• The stack structure allows us to efficiently check and remove these starting positions in order

The algorithm becomes:

1. Build a stack of indices with decreasing values (potential optimal starting points)
2. Traverse from right to left, and for each position, pop all valid starting positions from the stack while updating the maximum width
3. Once a starting position is used, it's removed since any other ending position would yield a smaller width

Learn more about Stack, Two Pointers and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic decreasing stack to efficiently find the maximum width ramp.

Step 1: Build the Monotonic Stack

stk = []
for i, v in enumerate(nums):
    if not stk or nums[stk[-1]] > v:
        stk.append(i)

We iterate through the array from left to right and build a stack that stores indices. An index i is added to the stack only if:

• The stack is empty (first element)
• nums[i] < nums[stk[-1]] (current value is smaller than the value at the top of the stack)

This creates a stack where the indices correspond to strictly decreasing values. For example, if nums = [6, 0, 8, 2, 1, 5], the stack would contain indices [0, 1, 4] corresponding to values [6, 0, 1].

Step 2: Find Maximum Width by Scanning Right to Left

ans = 0
for i in range(len(nums) - 1, -1, -1):
    while stk and nums[stk[-1]] <= nums[i]:
        ans = max(ans, i - stk.pop())
    if not stk:
        break

We traverse the array from right to left (from index n-1 to 0). For each position i:

• While the stack is not empty and nums[stk[-1]] <= nums[i], we have found a valid ramp
• We calculate the width as i - stk[-1] and update our answer
• We pop the index from the stack because any future ending position (to the left of current i) would give a smaller width for this starting position
• If the stack becomes empty, we can break early since we've found ramps for all potential starting positions

Why This Works:

1. The monotonic stack ensures we only consider the most promising starting positions (leftmost positions with each distinct "low" value)
2. Processing from right to left ensures we find the maximum width for each starting position
3. Popping used starting positions is optimal because once we've found the rightmost valid ending for a start position, any other ending would be suboptimal

Time Complexity: O(n) where n is the length of the array. Each element is pushed and popped from the stack at most once.

Space Complexity: O(n) in the worst case where the array is strictly decreasing, causing all indices to be stored in the stack.

Example Walkthrough

Let's walk through the algorithm with nums = [6, 0, 8, 2, 1, 5].

Step 1: Build the monotonic decreasing stack

We iterate through the array and add indices where values are strictly decreasing:

• i=0, v=6: Stack is empty, add 0. Stack: [0]
• i=1, v=0: 0 < 6, add 1. Stack: [0, 1]
• i=2, v=8: 8 > 0, skip. Stack: [0, 1]
• i=3, v=2: 2 > 0, skip. Stack: [0, 1]
• i=4, v=1: 1 > 0, skip. Stack: [0, 1]
• i=5, v=5: 5 > 0, skip. Stack: [0, 1]

Final stack: [0, 1] (indices with values [6, 0])

Step 2: Scan from right to left to find maximum width

Start with ans = 0.

• i=5, nums[5]=5:

  • Check stack top: nums[1]=0 ≤ 5 ✓
  • Width = 5 - 1 = 4, update ans = 4
  • Pop index 1. Stack: [0]
  • Check stack top: nums[0]=6 > 5 ✗
  • Continue

• i=4, nums[4]=1:

  • Check stack top: nums[0]=6 > 1 ✗
  • Continue

• i=3, nums[3]=2:

  • Check stack top: nums[0]=6 > 2 ✗
  • Continue

• i=2, nums[2]=8:

  • Check stack top: nums[0]=6 ≤ 8 ✓
  • Width = 2 - 0 = 2, ans remains 4 (4 > 2)
  • Pop index 0. Stack: []
  • Stack is empty, break early

Result: Maximum width = 4 (from indices 1 to 5)

The algorithm efficiently found that the widest ramp is from index 1 (value 0) to index 5 (value 5), giving a width of 4. By using the monotonic stack, we avoided checking unnecessary combinations and found the optimal solution in linear time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• The first loop iterates through all elements once to build the monotonic decreasing stack, taking O(n) time.
• The second loop iterates through the array from right to left once. While there's a nested while loop, each element in the stack is popped at most once throughout the entire execution, making the amortized time complexity O(n).
• Overall, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n) in the worst case.

• The stack stk stores indices of elements from the input array.
• In the worst case, when the array is strictly decreasing (e.g., [5, 4, 3, 2, 1]), all indices will be pushed onto the stack, requiring O(n) space.
• No other auxiliary data structures are used that scale with input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Building an Increasing Stack Instead of Decreasing

The Mistake: A common error is accidentally building an increasing monotonic stack by using the wrong comparison operator:

# WRONG: This builds an increasing stack
if not stack or nums[stack[-1]] < value:  # Should be >
    stack.append(index)

This fundamentally breaks the algorithm because:

• We need indices with smaller values as potential starting points for ramps
• An increasing stack would store indices with larger values, missing valid ramp starts

The Fix: Ensure you're using the correct comparison to build a decreasing stack:

# CORRECT: This builds a decreasing stack
if not stack or nums[stack[-1]] > value:
    stack.append(index)

Pitfall 2: Not Understanding Why We Traverse Right to Left

The Mistake: Some might attempt to traverse left to right in the second phase:

# WRONG: Traversing left to right
for i in range(len(nums)):
    while stack and nums[stack[-1]] <= nums[i]:
        ans = max(ans, i - stack.pop())

This fails because:

• We want the maximum width for each starting position
• Going left to right would find the leftmost valid ending, not the rightmost
• This gives suboptimal widths

The Fix: Always traverse from right to left to ensure maximum width:

# CORRECT: Right to left traversal
for i in range(len(nums) - 1, -1, -1):
    while stack and nums[stack[-1]] <= nums[i]:
        ans = max(ans, i - stack.pop())

Pitfall 3: Forgetting the Early Termination Optimization

The Mistake: Omitting the early break when the stack becomes empty:

# INEFFICIENT: Missing early termination
for i in range(len(nums) - 1, -1, -1):
    while stack and nums[stack[-1]] <= nums[i]:
        ans = max(ans, i - stack.pop())
    # Missing: if not stack: break

While this still produces correct results, it unnecessarily continues iterating even after all potential starting positions have been processed.

The Fix: Add the early termination check:

# OPTIMIZED: With early termination
for i in range(len(nums) - 1, -1, -1):
    while stack and nums[stack[-1]] <= nums[i]:
        ans = max(ans, i - stack.pop())
    if not stack:  # All starting positions processed
        break

Pitfall 4: Incorrectly Handling the Comparison in the Second Phase

The Mistake: Using strict inequality instead of less than or equal:

# WRONG: Using strict inequality
while stack and nums[stack[-1]] < nums[i]:  # Should be <=
    ans = max(ans, i - stack.pop())

This misses valid ramps where nums[i] == nums[j], which are allowed by the problem definition.

The Fix: Use the correct comparison operator:

# CORRECT: Using <=
while stack and nums[stack[-1]] <= nums[i]:
    ans = max(ans, i - stack.pop())