Maximum Width Ramp solution and explanation
Google
9 more videos on this problem
Maximum Width Ramp - Leetcode 962 - PythonNeetCodeIO · 14:47 · 23K views
Maximum Width Ramp | How to identify Monotonic Stack | Dry Runs | Leetcode 962 | codestorywithMIKcodestorywithMIK · 30:09 · 7K views
962. Maximum Width Ramp | stacks | Leetcode Daily Challenge | DSA | Java | shashcodeShashCode · 15:36 · 4K views
Maximum Width Ramp | Leetcode 962Techdose · 32:34 · 2K views
962. Maximum Width Ramp (Leetcode Medium)Programming Live with Larry · 11:28 · 1K views
Maximum Width Ramp - Leetcode 962Algorithms Casts · 14:51 · 1K views
solving leetcode in assembly 962. Maximum Width Rampakami · 2:12 · 1K views
Leetcode 962. Maximum Width Ramp (monotonic stack)LetsCode · 11:23 · 1K views
Maximum Width Ramp | Leetcode 962 | Amazon | Microsoft | Brute-Better-Optimal Solution + Live CodingTech With Anubhav · 38:40 · 827 views
Leetcode 962. Maximum Width RampJeevan Kumar - Cracckify · 7:20 · 618 views
The problem
A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.
Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.
Example 1:
Input: nums = [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.
Example 2:
Input: nums = [9,8,1,0,1,9,4,0,4,1] Output: 7 Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.
Constraints:
2 <= nums.length <= 5 * 1040 <= nums[i] <= 5 * 104
Approach overview
Problem Overview: You are given an integer array nums. A ramp is a pair of indices (i, j) such that i < j and nums[i] <= nums[j]. The width of the ramp is j - i. The goal is to find the maximum possible width among all valid ramps.
Approach 1: Monotonic Stack (O(n) time, O(n) space)
This approach builds a decreasing monotonic stack of indices while scanning the array from left to right. Push an index onto the stack only if its value is smaller than the value at the index currently on top of the stack. This ensures the stack contains candidate starting positions for ramps where each new index represents a smaller value than all previous candidates.
Next, iterate from the rightmost index toward the left. For each position j, check whether nums[j] can form a ramp with the index at the top of the stack. While the stack is not empty and nums[j] >= nums[stack.top], compute the width j - stack.top and update the maximum. Pop the index because any later j will produce a smaller width. Each index is pushed and popped at most once, giving O(n) time complexity with O(n) extra space for the stack. This technique is a classic pattern when solving problems with stack structures and monotonic constraints.
Approach 2: Two Pointers with Suffix Maximums (O(n) time, O(n) space)
This approach uses a preprocessing step instead of a stack. First build a suffix array where maxRight[j] stores the maximum value from index j to the end of the array. This tells you the largest possible value that could serve as the right side of a ramp starting at or after j.
Then use two pointers i and j. If nums[i] <= maxRight[j], a valid ramp can exist ending somewhere at or after j. Update the answer with j - i and move j forward to try increasing the width. If the condition fails, increment i because the left value is too large and cannot form a ramp with any future element. Both pointers move forward at most n times, giving linear O(n) time and O(n) extra space for the suffix array. This technique works well for problems involving comparisons across ranges in an array.
Recommended for interviews: The monotonic stack solution is the most common interview answer because it directly models the search for the smallest left candidates and efficiently checks them from the right side. Showing the brute-force idea (O(n^2)) demonstrates baseline reasoning, but implementing the O(n) monotonic stack approach signals strong understanding of stack-based optimization patterns.
Approach 1: Monotonic Stack Approach
This approach utilizes a stack to keep track of indices in a monotonically decreasing order, which helps to quickly find the maximum possible ramp width.
def maxWidthRamp(nums):
stack = []
max_width = 0
# Build initial decreasing stack of indices
for i, num in enumerate(nums):
if not stack or nums[stack[-1]] > num:
stack.append(i)
# Traverse from the end for maximum width
for j in range(len(nums) - 1, -1, -1):
while stack and nums[stack[-1]] <= nums[j]:
max_width = max(max_width, j - stack.pop())
return max_width#include <vector>
#include <stack>
#include <algorithm>
int maxWidthRamp(std::vector<int>& nums) {
std::stack<int> s;
int max_width = 0;
for (int i = 0; i < nums.size(); ++i) {
if (s.empty() || nums[s.top()] > nums[i]) {
s.push(i);
}
}
for (int j = nums.size() - 1; j >= 0; --j) {
while (!s.empty() && nums[s.top()] <= nums[j]) {
max_width = std::max(max_width, j - s.top());
s.pop();
}
}
return max_width;
}This solution first creates a stack that holds indices of nums in a decreasing manner. It then traverses the array from right to left, popping elements from the stack to calculate potential maximum widths.
Time Complexity: O(n), where n is the number of elements in the array - because each element is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack of indices.
Approach 2: Two Pointer Approach
This approach uses two pointers to find the maximum width ramp by initially sorting potential endpoints and then finding the earliest start point that forms a valid ramp.
import java.util.ArrayList;
import java.util.List;
class Solution {
public int maxWidthRamp(int[] nums) {
List<Integer> indices = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
indices.add(i);
}
indices.sort((a, b) -> Integer.compare(nums[a], nums[b]));
int maxRamp = 0;
int minIndex = nums.length;
for (int index : indices) {
maxRamp = Math.max(maxRamp, index - minIndex);
minIndex = Math.min(minIndex, index);
}
return maxRamp;
}
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxWidthRamp(int[] nums) {
List<int> indices = new List<int>();
for (int i = 0; i < nums.Length; i++) {
indices.Add(i);
}
indices.Sort((a, b) => nums[a] - nums[b]);
int maxRamp = 0;
int minIndex = nums.Length;
foreach (int index in indices) {
maxRamp = Math.Max(maxRamp, index - minIndex);
minIndex = Math.Min(minIndex, index);
}
return maxRamp;
}
}This solution sorts the indices based on their values and then iteratively updates the maximum width by finding the smallest index encountered so far, to ensure the widest ramp.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices.
Approach 3: Monotonic Stack
According to the problem, we can find that the subsequence formed by all possible nums[i] must be monotonically decreasing. Why is that? Let's prove it by contradiction.
Suppose there exist i_1<i_2 and nums[i_1]leqnums[i_2], then actually nums[i_2] cannot be a candidate value, because nums[i_1] is more to the left and would be a better value. Therefore, the subsequence formed by nums[i] must be monotonically decreasing, and i must start from 0.
We use a monotonically decreasing stack stk (from bottom to top) to store all possible nums[i]. Then we traverse j starting from the right boundary. If we encounter nums[stk.top()]leqnums[j], it means a ramp is formed at this point. We cyclically pop the top elements from the stack and update ans.
The time complexity is O(n) and the space complexity is O(n), where n represents the length of nums.
function maxWidthRamp(nums) {
let [ans, n] = [0, nums.length];
const stk = [];
for (let i = 0; i < n - 1; i++) {
if (stk.length === 0 || nums[stk.at(-1)] > nums[i]) {
stk.push(i);
}
}
for (let i = n - 1; i >= 0; i--) {
while (stk.length && nums[stk.at(-1)] <= nums[i]) {
ans = Math.max(ans, i - stk.pop());
}
if (stk.length === 0) break;
}
return ans;
}function maxWidthRamp(nums: number[]): number {
let [ans, n] = [0, nums.length];
const stk: number[] = [];
for (let i = 0; i < n - 1; i++) {
if (stk.length === 0 || nums[stk.at(-1)!] > nums[i]) {
stk.push(i);
}
}
for (let i = n - 1; i >= 0; i--) {
while (stk.length && nums[stk.at(-1)!] <= nums[i]) {
ans = Math.max(ans, i - stk.pop()!);
}
if (stk.length === 0) break;
}
return ans;
}func maxWidthRamp(nums []int) int {
n := len(nums)
stk := []int{}
for i, v := range nums {
if len(stk) == 0 || nums[stk[len(stk)-1]] > v {
stk = append(stk, i)
}
}
ans := 0
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= nums[i] {
ans = max(ans, i-stk[len(stk)-1])
stk = stk[:len(stk)-1]
}
if len(stk) == 0 {
break
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n), where n is the number of elements in the array - because each element is pushed and popped from the stack at most once. |
| Two Pointer Approach | Time Complexity: O(n log n) due to sorting. |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check All Pairs | O(n^2) | O(1) | Useful only for understanding the definition of a ramp or when n is very small. |
| Monotonic Stack | O(n) | O(n) | Best general solution. Common interview approach using a decreasing stack of candidate indices. |
| Two Pointers with Suffix Maximum | O(n) | O(n) | Good alternative when you prefer pointer scanning and preprocessing instead of a stack. |
Frequently asked questions
Is Maximum Width Ramp easy or hard?
Maximum Width Ramp is classified as a Medium difficulty problem. The challenge comes from recognizing that brute force is too slow and that a monotonic stack can track optimal left candidates efficiently. Once the pattern is recognized, the implementation is straightforward.
How to solve Maximum Width Ramp in O(n)?
Build a decreasing monotonic stack of indices while iterating left to right. Then traverse the array from right to left and check whether the current value can form a ramp with the stack's top index. When nums[j] >= nums[i], update the width and pop the index. Each element is processed at most twice, giving O(n) time.
Maximum Width Ramp Python or Java solution?
Python solutions typically implement the monotonic stack using a list and perform a reverse scan to compute widths. Java implementations often follow the same algorithm with a Stack or ArrayDeque. Both achieve O(n) time complexity and O(n) auxiliary space.
What is the best approach for Maximum Width Ramp?
The most efficient approach uses a monotonic decreasing stack. First store candidate starting indices whose values keep decreasing. Then scan the array from right to left and pop indices while nums[j] >= nums[stack.top], updating the ramp width. This method runs in O(n) time and O(n) space and is the solution most interviewers expect.
What data structure is used in Maximum Width Ramp?
The primary data structure is a monotonic stack that stores indices in decreasing order of their values. This structure ensures the left side of potential ramps always contains the smallest candidates, allowing efficient width checks while scanning from the right.
What is the time complexity of Maximum Width Ramp?
The optimal algorithms run in O(n) time. The monotonic stack solution pushes each index once and pops it at most once while scanning from the right. Alternative linear solutions using two pointers with a suffix maximum array also achieve O(n) time with O(n) additional space.
Is Maximum Width Ramp asked at Google, Amazon, or Meta?
Maximum Width Ramp appears in interview preparation lists for companies like Amazon, Google, and Meta because it tests monotonic stack patterns and array scanning techniques. Variations of the problem are also common in competitive programming and coding interviews that focus on stack-based optimizations.