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 * 104The goal of #962 Maximum Width Ramp is to find the largest distance j - i such that i < j and nums[i] <= nums[j]. A brute-force approach checks all pairs, but it leads to O(n^2) time, which is inefficient for large arrays.
An optimized method uses a monotonic decreasing stack. First, traverse the array from left to right and push indices onto a stack only when they create a new smaller value. This stack keeps potential starting points for ramps in decreasing order of values. Then traverse the array from right to left, and whenever the current value satisfies the ramp condition with the top of the stack, calculate the width and update the maximum. Continue popping while valid ramps exist.
This strategy works because the stack stores only the most promising starting indices. The two-pass process ensures each element is processed efficiently, resulting in linear time complexity with minimal additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Pair Checking | O(n^2) | O(1) |
| Monotonic Decreasing Stack | O(n) | O(n) |
NeetCodeIO
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.
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.
1def maxWidthRamp(nums):
2 stack = []
3 max_width = 0
4
5 # Build initial decreasing stack of indices
6 for i, num in enumerate(nums):
7 if not stack or nums[stack[-1]] > num:
8 stack.append(i)
9
10 # Traverse from the end for maximum width
11 for j in range(len(nums) - 1, -1, -1):
12 while stack and nums[stack[-1]] <= nums[j]:
13 max_width = max(max_width, j - stack.pop())
14
15 return max_widthThis 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.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices.
1import java.util.ArrayList;
2import java.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of array and monotonic stack problems like Maximum Width Ramp can appear in FAANG-style interviews. They test understanding of stack patterns, greedy reasoning, and array traversal optimizations.
A monotonic stack ensures that only useful candidate indices are stored. This reduces unnecessary comparisons and allows the algorithm to find the maximum ramp width in linear time.
A monotonic stack is the most effective data structure for this problem. It helps track indices with decreasing values, allowing efficient comparison with elements scanned from the right side.
The optimal approach uses a monotonic decreasing stack. First, store candidate starting indices while maintaining decreasing values, then scan from right to left to compute the maximum ramp width efficiently.
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.