We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Width Ramp

Difficulty: Medium

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.

Key Insights

  • A ramp is defined by two indices i and j where i < j and nums[i] <= nums[j].
  • The goal is to maximize the width j - i.
  • To efficiently find pairs that satisfy the ramp condition, we can utilize a stack to track potential starting points (indices) of ramps.
  • By iterating through the array while maintaining a sorted order of indices, we can quickly find valid pairs.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a monotonic stack to hold indices of the array. We will first traverse the array to identify the indices in increasing order of their corresponding values. Then, we will iterate through the array again to find the maximum width of the ramps by checking the conditions using the stack.

  1. Create a stack to store indices of the array.
  2. Traverse the array from left to right and populate the stack with indices of elements in increasing order.
  3. Traverse the array from right to left and check against the indices in the stack to find valid ramps, updating the maximum width accordingly.

This approach ensures that we efficiently find the maximum width without needing to compare every possible pair.

Code Solutions

def maxWidthRamp(nums):
    # Create a stack to hold indices of nums
    stack = []
    n = len(nums)
    
    # Fill the stack with indices of nums in increasing order of their values
    for i in range(n):
        if not stack or nums[stack[-1]] > nums[i]:
            stack.append(i)
    
    max_width = 0
    
    # Reverse traverse the nums array to find maximum width
    for j in range(n-1, -1, -1):
        while stack and nums[stack[-1]] <= nums[j]:
            max_width = max(max_width, j - stack.pop())
    
    return max_width
← Back to All Questions