Watch 10 video solutions for Maximum Width Ramp, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by NeetCodeIO has 23,142 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 104Problem 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 | 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. |