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.
- Difficulty: Medium
- Topics: Arrays, Two Pointers, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 400 <= nums[i] <= 50000
Hints for Maximum Width Ramp
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.
Hint 2
Build that stack of candidate left indices in one forward pass.
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
- Forward pass: push
iwhennums[i]is smaller than the current stack top's value. - Backward pass over
j: whilenums[top] <= nums[j], pop and updatebest = 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 bestJava
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