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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Width Ramp

Number: 1002

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Accenture, TikTok, Microsoft

Problem Description

Given an integer array nums, a ramp is defined as a pair (i, j) such that i < j and nums[i] <= nums[j]. The width of the ramp is j - i. The problem asks for the maximum width ramp in the array. If no ramp exists, return 0.

Key Insights

  • We need to identify pairs (i, j) where i < j and nums[i] <= nums[j].
  • A monotonic decreasing stack can be constructed to maintain candidate starting indices.
  • By iterating from left to right, we push indices onto the stack only when they have a smaller value than the last.
  • Then, a backward pass from the end of the array allows us to efficiently match each element with the smallest possible candidate index from the stack.

Space and Time Complexity

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

Solution

The solution is built in two phases:

  1. Build a decreasing stack of indices by iterating through the array (only push an index if its value is less than the value at the current top of the stack).
  2. Iterate through the array backwards. For each index j, check and pop elements from the stack while nums[j] is greater than or equal to the nums value at the popped index. For each valid ramp found, compute the width (j - popped index) and update the maximum width accordingly. This approach guarantees we examine each element a constant number of times ensuring an efficient solution.

Code Solutions

# Python solution for Maximum Width Ramp

def maxWidthRamp(nums):
    n = len(nums)
    stack = []
    # Build a stack of indices where array values are in decreasing order
    for i in range(n):
        if not stack or nums[i] < nums[stack[-1]]:
            stack.append(i)
    max_width = 0
    # Iterate backwards to find the maximum width ramp
    for j in range(n - 1, -1, -1):
        while stack and nums[j] >= nums[stack[-1]]:
            max_width = max(max_width, j - stack.pop())
    return max_width

# Example usage:
nums = [6, 0, 8, 2, 1, 5]
print(maxWidthRamp(nums))  # Output: 4
← Back to All Questions