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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
JavaScript
| 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 | — |
| 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. |
Maximum Width Ramp - Leetcode 962 - Python • NeetCodeIO • 23,142 views views
Watch 9 more video solutions →Practice Maximum Width Ramp with our built-in code editor and test cases.
Practice on FleetCode