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 * 104This 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.
C++
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.
C#
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices.
| 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. |
Maximum Width Ramp - Leetcode 962 - Python • NeetCodeIO • 20,039 views views
Watch 9 more video solutions →Practice Maximum Width Ramp with our built-in code editor and test cases.
Practice on FleetCode