Maximum Width Ramp

Problem#

A ramp is a pair (i, j) with i < j and nums[i] <= nums[j]. Return the maximum width j - i over all ramps, or 0 if none exists.

Examples#

nums = [6,0,8,2,1,5] → 4 (i=1, j=5)
nums = [9,8,1,0,1,9,4,0,4,1] → 7 (i=2, j=9)

Constraints#

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

Approach#

Forward pass: push indices i where nums[i] is strictly less than every previously pushed value — i.e., maintain a stack of “potential left endpoints” with strictly decreasing values. Backward pass: for each j from right to left, pop the top while nums[top] <= nums[j] and update the answer with j - top. Because the stack is decreasing, popping in this way greedily finds the widest legal left for each j.

Solution#

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            if (st.empty() || nums[st.top()] > nums[i]) st.push(i);
        }
        int ans = 0;
        for (int j = n - 1; j >= 0; --j) {
            while (!st.empty() && nums[st.top()] <= nums[j]) {
                ans = max(ans, j - st.top());
                st.pop();
            }
        }
        return ans;
    }
};

func maxWidthRamp(nums []int) int {
    n := len(nums)
    st := []int{}
    for i := 0; i < n; i++ {
        if len(st) == 0 || nums[st[len(st)-1]] > nums[i] {
            st = append(st, i)
        }
    }
    ans := 0
    for j := n - 1; j >= 0; j-- {
        for len(st) > 0 && nums[st[len(st)-1]] <= nums[j] {
            if j-st[len(st)-1] > ans {
                ans = j - st[len(st)-1]
            }
            st = st[:len(st)-1]
        }
    }
    return ans
}

from typing import List

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        st: List[int] = []
        for i in range(n):
            if not st or nums[st[-1]] > nums[i]:
                st.append(i)
        ans = 0
        for j in range(n - 1, -1, -1):
            while st and nums[st[-1]] <= nums[j]:
                ans = max(ans, j - st[-1])
                st.pop()
        return ans

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

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

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

Editorial#

Any optimal left endpoint must be a “decreasing-stack candidate”: if there’s a smaller-or-equal element with a smaller index, that one is strictly better. Sweeping j from the right and popping the stack is then a single linear pass — each index is pushed and popped at most once.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#