DSA problem
Maximum Width Ramp
A ramp in an integer array nums is a pair of indices (i, j) with i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Given nums, return the maximum width of any ramp in the array, or 0 if no ramp exists.
The brute force is the obvious double loop: for every i, find the largest j such that nums[i] <= nums[j]. That is O(n²) and quickly becomes too slow for n up to 5 * 10⁴.
A monotonic-stack solution runs in O(n) time. The key observation is that, for any candidate ramp ending at j, the best i is the leftmost index where nums[i] <= nums[j]. So we only need to consider indices i whose values form a strictly decreasing sequence from left to right — any index with a value not strictly smaller than something already to its left is dominated as a starting point.
So: in a first left-to-right pass, push every index whose value is strictly less than the value at the stack's top, producing a strictly decreasing stack of candidate i values. Then in a second right-to-left pass over j = n - 1, n - 2, …, while the value at the stack's top is at most nums[j], pop the top i and update the answer with j - i. Each index is pushed once and popped at most once, giving O(n) total time.
Examples
nums = [6,0,8,2,1,5]4nums = [9,8,1,0,1,9,4,0,4,1]7nums = [2,2,1]1Constraints
- 2 <= nums.length <= 5 * 10^4
- 0 <= nums[i] <= 5 * 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.