Maximum Width Ramp
Medium · Stack & Strings · Array · Two Pointers · Stack · Monotonic Stack
Problem
In an integer array nums, a ramp is a pair of indices (i, j) with i < j and nums[i] <= nums[j]. Its width is j - i.
Return the largest width of any ramp in nums, or 0 if there is none.
Examples
Input: nums = [7,2,5,3,1,6] Output: 4
Index 1 (value 2) and index 5 (value 6) form a ramp of width 4.
Input: nums = [5,4,3] Output: 0
Every later value is smaller, so no ramp exists.
Input: nums = [4,9,1,4,0] Output: 3
nums[0] = nums[3] = 4 is a ramp of width 3; equal values count.
Constraints
- 2 <= len(nums) <= 5 · 10^4
- 0 <= nums[i] <= 5 · 10^4
Approaches
- For each start, search from the far right — time O(n²), space O(1)
Follow-up
Another O(n log n) way: sort the indices by value (ties by index) and walk them in that order, keeping the smallest index seen so far. Every later index in the walk has a value at least as big, so index - smallest index so far is a ramp, and the largest one is the answer.
Related problems
Start free on Cariara · Coding problems · System design studio
