Maximum Width Ramp — Monotonic Stack + Two Pass
Sanjeev SharmaAdvertisement
Problem
Find maximum j - i such that i < j and nums[i] <= nums[j].
Approach — Decreasing Stack + Right Scan
- Build decreasing stack of indices (potential left endpoints)
- Scan from right: for each j, pop stack while stack top <= nums[j], track max width
Time: O(n) | Space: O(n)
Solutions
Python
class Solution:
def maxWidthRamp(self, nums: list[int]) -> int:
n=len(nums); stack=[]
for i in range(n):
if not stack or nums[i]<nums[stack[-1]]: stack.append(i)
ans=0
for j in range(n-1,-1,-1):
while stack and nums[stack[-1]]<=nums[j]:
ans=max(ans,j-stack.pop())
return ans
Complexity
- Time: O(n) | Space: O(n)
Advertisement
