Maximum Width Ramp

medium array stack monotonic stack

Problem

A ramp is a pair (i, j) with i < j and nums[i] ≤ nums[j]. Return the largest j − i over all ramps.

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

Output4

Decreasing stack of left-candidates, scan from the right popping when allowed.

nums (comma-separated)

def maxWidthRamp(nums):
    st = []
    for i, x in enumerate(nums):
        if not st or nums[st[-1]] > x:
            st.append(i)
    best = 0
    for j in range(len(nums) - 1, -1, -1):
        while st and nums[st[-1]] <= nums[j]:
            best = max(best, j - st.pop())
    return best

function maxWidthRamp(nums) {
  const st = [];
  for (let i = 0; i < nums.length; i++) {
    if (st.length === 0 || nums[st[st.length - 1]] > nums[i]) st.push(i);
  }
  let best = 0;
  for (let j = nums.length - 1; j >= 0; j--) {
    while (st.length && nums[st[st.length - 1]] <= nums[j]) best = Math.max(best, j - st.pop());
  }
  return best;
}

class Solution {
    public int maxWidthRamp(int[] nums) {
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++)
            if (st.isEmpty() || nums[st.peek()] > nums[i]) st.push(i);
        int best = 0;
        for (int j = nums.length - 1; j >= 0; j--)
            while (!st.isEmpty() && nums[st.peek()] <= nums[j]) best = Math.max(best, j - st.pop());
        return best;
    }
}

int maxWidthRamp(vector<int>& nums) {
    vector<int> st;
    for (int i = 0; i < (int)nums.size(); i++)
        if (st.empty() || nums[st.back()] > nums[i]) st.push_back(i);
    int best = 0;
    for (int j = (int)nums.size() - 1; j >= 0; j--)
        while (!st.empty() && nums[st.back()] <= nums[j]) { best = max(best, j - st.back()); st.pop_back(); }
    return best;
}

Explanation

A ramp is a pair (i, j) with i < j and nums[i] <= nums[j], and we want the widest one. The clever idea uses two passes and a decreasing stack of candidate left endpoints.

First pass, left-to-right: we push an index i onto the stack only when its value is strictly smaller than the value at the current stack top. This leaves a stack of indices whose values strictly decrease — the only sensible candidates for the left end i of a ramp, since any larger earlier value would be a worse left endpoint.

Second pass, right-to-left: for each j, while the value at the stack top is <= nums[j], that top index forms a valid ramp with j. We record the width j - st.pop() and pop it, because we are scanning j from the right so this is the widest ramp that top index can ever get.

Example: nums = [6, 0, 8, 2, 1, 5]. The candidate stack becomes indices [0, 1] (values 6 then 0). Scanning from the right, j = 5 (value 5) pops index 1 (value 0) giving width 5 - 1 = 4, which is the answer.

Because each candidate is pushed once and popped once, the whole solution runs in linear time.

Time: O(n) Space: O(n)