Maximum Width Ramp

Medium
385.

Maximum Width Ramp

Maximum Width Ramp is a medium coding problem on arrays, two pointers and stack, asked in Amazon and Google interviews.

A ramp in an integer array nums is a pair (i, j) with i < j and nums[i] <= nums[j]; its width is j - i.

Return the maximum width of any ramp, or 0 if none exists.

Example 1

Input
nums = [6,0,8,2,1,5]
Output
4
Explanation
The ramp (1, 5) has nums[1] = 0 <= nums[5] = 5.

Example 2

Input
nums = [9,8,1,0,1,9,4,0,4,1]
Output
7

Example 3

Input
nums = [5,4,3]
Output
0

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 50000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxWidthRamp = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Width Ramp — Solution in Python, Java & C++

Maximum Width Ramp solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Width Ramp is a medium coding problem on arrays, two pointers and stack, asked in Amazon and Google interviews.

Problem statement

A ramp in an integer array nums is a pair (i, j) with i < j and nums[i] <= nums[j]; its width is j - i.

Return the maximum width of any ramp, or 0 if none exists.

Example 1

Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The ramp (1, 5) has nums[1] = 0 <= nums[5] = 5.

Example 2

Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7

Example 3

Input: nums = [5,4,3]
Output: 0

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 50000

Hints for Maximum Width Ramp

  1. Hint 1

    Only a strictly decreasing prefix can supply the left end of the widest ramp — any later, larger value would be a worse start.

  2. Hint 2

    Build that stack of candidate left indices in one forward pass.

  3. Hint 3

    Then scan from the right, popping every candidate the current value can reach; each pop gives a ramp, and later pops can only be narrower.

How to solve Maximum Width Ramp

Only a strictly decreasing prefix can supply the widest ramp's left end. Build that stack of candidate starts, then scan from the right popping every start the current value can reach.

Approach

  1. Forward pass: push i when nums[i] is smaller than the current stack top's value.
  2. Backward pass over j: while nums[top] <= nums[j], pop and update best = j - top.

Why it works

A later, larger start is dominated by an earlier, smaller one, so the decreasing prefix holds every useful left end; scanning j from the right guarantees the first j that reaches a start gives its maximal width.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Each start is popped once, so the two passes are linear despite the nested loop.

Reference solution

Python

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

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique