Maximum Width Ramp
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible pair of indices (i, j) where i < j. For each pair, it verifies if it forms a ramp (nums[i] <= nums[j]) and, if so, calculates its width j - i. The maximum width found across all pairs is the result.
Algorithm
- Initialize a variable
maxWidthto 0. - Use a nested loop. The outer loop iterates through each possible starting index
ifrom0ton-2. - The inner loop iterates through each possible ending index
jfromi + 1ton-1. - Inside the inner loop, check the ramp condition:
nums[i] <= nums[j]. - If the condition is true, it means we've found a valid ramp. We calculate its width
j - iand updatemaxWidthto be the maximum of its current value and the new width. - After checking all pairs,
maxWidthwill hold the maximum width of any ramp in the array.
Walkthrough
The brute-force solution is the most straightforward way to solve the problem. We simply follow the definition of a ramp and its width. We iterate through all possible pairs of indices (i, j) such that i comes before j. For every such pair, we check if nums[i] is less than or equal to nums[j]. If this condition holds, we have found a valid ramp. We then calculate its width, which is j - i, and compare it with the maximum width found so far, updating it if the new width is larger. This process is repeated until all possible pairs have been considered.
class Solution { public int maxWidthRamp(int[] nums) { int n = nums.length; int maxWidth = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] <= nums[j]) { maxWidth = Math.max(maxWidth, j - i); } } } return maxWidth; }}Complexity
Time
O(N^2), where N is the length of `nums`. The nested loops lead to a quadratic number of comparisons.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
This approach improves upon the brute-force method by sorting. The key idea is to not sort the array values directly, but to sort their original indices based on the values they point to. After sorting, we can efficiently find the maximum ramp width in a single pass.
Algorithm
- Create an array or list of indices from
0ton-1. - Sort this index array based on the corresponding values in
nums. If values are equal, the relative order of indices doesn't matter for correctness. - Initialize
maxWidth = 0andminIndexto a large value (e.g.,n). - Iterate through the sorted indices array. For each
index:- Calculate a potential width:
width = index - minIndex. - Update
maxWidth = max(maxWidth, width). - Update
minIndex = min(minIndex, index)to keep track of the smallest original index seen so far.
- Calculate a potential width:
- Return
maxWidth.
Walkthrough
To maximize j - i for a ramp, for any given j, we need to find an i < j with nums[i] <= nums[j] such that i is as small as possible. We can reframe the problem by processing the numbers in increasing order of their values. By doing so, for any number nums[j], any number nums[i] processed before it will satisfy nums[i] <= nums[j].
We can implement this by creating pairs of (value, index) and sorting them by value. Then, we iterate through the sorted list. To maximize j - i, we need to pair the current index_j with the smallest index_i seen so far. We can maintain a variable min_index that tracks the minimum index encountered as we iterate. For each element, we calculate the potential width using its index and min_index, update our maxWidth, and then update min_index with the current element's index if it's smaller.
import java.util.Arrays; class Solution { public int maxWidthRamp(int[] nums) { int n = nums.length; Integer[] indices = new Integer[n]; for (int i = 0; i < n; i++) { indices[i] = i; } // Sort indices based on the values in nums Arrays.sort(indices, (a, b) -> Integer.compare(nums[a], nums[b])); int maxWidth = 0; int minIndex = n; for (int index : indices) { maxWidth = Math.max(maxWidth, index - minIndex); minIndex = Math.min(minIndex, index); } return maxWidth; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent scan is O(N).
Space
O(N) to store the array of indices for sorting.
Trade-offs
Pros
Significantly more efficient than brute force, with O(N log N) time complexity.
Passes the time limits for the given constraints.
Cons
Requires extra space proportional to the input size.
Not the most optimal solution in terms of time complexity.
This is the most optimal approach with linear time complexity. It uses a monotonic stack to identify potential starting points of a ramp in one pass, and then finds the maximum width by scanning from the end of the array in a second pass.
Algorithm
- Initialize an empty stack.
- First Pass (Build Candidates): Iterate
ifrom0ton-1. If the stack is empty ornums[i]is less thannumsat the index on top of the stack, pushionto the stack. This creates a stack of indices corresponding to a monotonically decreasing sequence of values. - Initialize
maxWidth = 0. - Second Pass (Find Ramps): Iterate
jfromn-1down to0.- While the stack is not empty and
numsat the index on top of the stack (i) is less than or equal tonums[j]:- We have a valid ramp
(i, j). UpdatemaxWidth = max(maxWidth, j - i). - Pop the index
ifrom the stack, as it has been matched with its best possiblej.
- We have a valid ramp
- While the stack is not empty and
- Return
maxWidth.
Walkthrough
The core idea is to efficiently find the best candidates for the start of a ramp, i. A good candidate i should have a small value nums[i]. If we have two indices i1 < i2 with nums[i1] <= nums[i2], i1 is always a better or equal candidate than i2 for starting a ramp. This implies that the best candidates for i will have values that form a strictly decreasing sequence.
Pass 1: Build a monotonic stack. We iterate through the array and build a stack of indices. We only push an index i onto the stack if nums[i] is smaller than the value at the index on top of the stack. This results in a stack where indices are increasing and their corresponding values in nums are strictly decreasing. These are our optimal candidates for the start of a ramp.
Pass 2: Find the maximum width. We iterate backwards from the end of the array (j from n-1 to 0). For each j, we check if nums[j] can form a ramp with the index i at the top of the stack (nums[i] <= nums[j]). If it can, we've found a valid ramp (i, j). We calculate the width j - i, update our maxWidth, and pop i from the stack. We pop because we've found the best possible j for this i (since we're iterating j backwards). We continue this process with the new top of the stack until the condition is no longer met or the stack is empty.
import java.util.Stack; class Solution { public int maxWidthRamp(int[] nums) { Stack<Integer> stack = new Stack<>(); int n = nums.length; // Pass 1: Build a stack of candidate indices for the start of the ramp. for (int i = 0; i < n; i++) { if (stack.isEmpty() || nums[stack.peek()] > nums[i]) { stack.push(i); } } int maxWidth = 0; // Pass 2: Iterate from the end to find the maximum width. for (int j = n - 1; j >= 0; j--) { while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) { int i = stack.pop(); maxWidth = Math.max(maxWidth, j - i); } } return maxWidth; }}Complexity
Time
O(N). Each index is pushed and popped from the stack at most once. Both passes are linear scans of the array.
Space
O(N) in the worst case for the stack (e.g., when the input array is strictly decreasing).
Trade-offs
Pros
Most efficient solution with linear time complexity.
Guaranteed to pass within time limits for large inputs.
Cons
Can be less intuitive to understand compared to sorting or brute-force approaches.
Requires extra space for the stack.
Solutions
Solution
class Solution {public int maxWidthRamp(int[] nums) { int n = nums.length; Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { if (stk.isEmpty() || nums[stk.peek()] > nums[i]) { stk.push(i); } } int ans = 0; for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) { ans = Math.max(ans, i - stk.pop()); } if (stk.isEmpty()) { break; } } return ans; }}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 ; }class Solution {public: int maxWidthRamp(vector<int> &nums) { int n = nums.size(); stack<int> stk; for (int i = 0; i < n; ++i) { if (stk.empty() || nums[stk.top()] > nums[i]) stk.push(i); } int ans = 0; for (int i = n - 1; i; --i) { while (!stk.empty() && nums[stk.top()] <= nums[i]) { ans = max(ans, i - stk.top()); stk.pop(); } if (stk.empty()) break; } return ans; }};class Solution: def maxWidthRamp(self, nums: List[int]) -> int: stk = [] for i, v in enumerate(nums): if not stk or nums[stk[- 1]] > v: stk . append(i) ans = 0 for i in range(len(nums) - 1, - 1, - 1): while stk and nums[stk[- 1]] <= nums[i]: ans = max(ans, i - stk . pop()) if not stk: break return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.