Leetcode Daily Question 10/10/2024 - 962. Maximum Width Ramp

Problem Description:

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.

from typing import List
class Solution:
  def maxWidthRamp(self, nums: List[int]) -> int:
    max_width = 0
    n = len(nums)
    stack = []
    
    for i, num in enumerate(nums):
      if not stack or num < nums[stack[-1]]:
        stack.append(i)
    
    for j in range(n - 1, -1 ,-1):
      while stack and nums[j] >= nums[stack[-1]]:
        i = stack.pop()
        max_width = max(max_width, j - i)
    
    return max_width

Explanation:

A clever approach to this is using a stack to keep track of the smallest element we have seen so far. This creates a strictly decreasing array of start points for us to compare.

Then we iterate in reverse, comparing the current element to the top of the stack. If the start point is valid, i.e. nums[stack[-1]] is less than nums[j]. Then we pop this from the stack and update the max width if necessary.

def maxWidthRamp(nums):
  max_width = 0
  stack = []
  n = len(nums)
  
  for i, num in enumerate(nums):
    if not stack or num < nums[stack[-1]]:
      stack.append(i)
  
  for j in range(n - 1, -1, -1):
    while stack and nums[j] >= nums[stack[-1]]:
      i = stack.pop()
      max_width = max(max_width, j - i)
  
  return max_width

The time complexity is O(n) as we traverse the array to fill the stack, and traverse the nums array in reverse to update max width.

The space complexity is O(n) as the stack may contain all of nums.

The full solution can be found near the top of the page.