#962

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Maximum Width Ramp

Find the maximum width of a ramp where nums[i] <= nums[j] for i < j using a two-pointer approach.

array two pointers stack monotonic stack

Problem Statement

Given an integer array nums, a ramp is defined as a pair of indices (i, j) such that i < j and nums[i] <= nums[j]. The width of the ramp is calculated as j - i. Your task is to return the maximum width of such a ramp from the array.

If no ramp exists in the array, return 0. For example, in the array nums = [6,0,8,2,1,5], the maximum width ramp is achieved between indices 1 and 5, giving a width of 4.

Examples

Example 1

Input: nums = [6,0,8,2,1,5]

Output: 4

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

The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

Constraints

2 <= nums.length <= 5 * 104
0 <= nums[i] <= 5 * 104

Solution Approach

Two-pointer Scanning

A two-pointer technique is used to find the maximum width ramp efficiently. First, scan the array with the second pointer starting at the end, and use the stack to store indices of elements that could form valid ramps.

Monotonic Stack for Tracking Indices

Use a monotonic stack to maintain a list of indices where elements are in non-decreasing order. This allows for efficient checking of possible ramp widths between the stack and the second pointer as you scan the array.

Maximizing the Ramp Width

For each valid pair (i, j) where nums[i] <= nums[j], calculate the width j - i. Continuously update the maximum width found while iterating through the array.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) due to a single scan of the array using the two-pointer technique, and the space complexity is O(n) for storing indices in the stack. This ensures the algorithm scales efficiently with large inputs.

What Interviewers Usually Probe

Candidate understands the two-pointer technique for optimizing problems like this one.
Look for clarity in the candidate's explanation of the monotonic stack's role in solving the problem.
Assess how well the candidate relates the problem to patterns like invariant tracking and ramp-width maximization.

Common Pitfalls or Variants

Common pitfalls

Failing to use the monotonic stack efficiently, leading to incorrect ramp width calculations.
Not recognizing that the two-pointer technique must be combined with a stack for optimal performance.
Overcomplicating the problem by using a brute-force approach that results in O(n^2) time complexity.

Follow-up variants

Consider variations where the ramp definition might change, such as requiring nums[i] > nums[j] or other constraints on the array.
Explore edge cases with minimum and maximum array sizes to ensure the algorithm handles these scenarios effectively.
Consider extending the problem to allow ramps in multidimensional arrays or with additional constraints.

FAQ

What is the time complexity of the Maximum Width Ramp problem?

The time complexity is O(n) due to a single pass through the array using the two-pointer technique, with a stack operation for each element.

How does the two-pointer technique work in the Maximum Width Ramp problem?

The two-pointer technique allows you to efficiently track potential ramps by iterating through the array, using a stack to track indices and calculate the maximum width.

What is a monotonic stack, and how does it help solve the Maximum Width Ramp problem?

A monotonic stack maintains a sequence of indices in non-decreasing order, helping efficiently track potential ramp widths and ensuring the correct pair of indices is selected for maximizing the width.

How does GhostInterview assist with solving the Maximum Width Ramp problem?

GhostInterview guides you step-by-step through the problem, offering clear explanations of the two-pointer and stack techniques, helping you avoid common mistakes.

Can the solution for the Maximum Width Ramp problem be optimized further?

The current solution is already optimal with O(n) time complexity, but variations of the problem with different constraints may require alternative strategies.

terminal

Solution

Solution 1: Monotonic Stack

According to the problem, we can find that the subsequence formed by all possible $\textit{nums}[i]$ must be monotonically decreasing. Why is that? Let's prove it by contradiction.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stk = []
        for i, v in enumerate(nums):
            if not stk or nums[stk[-1]] > v:
                stk.append(i)
        ans = 0
        for i in range(len(nums) - 1, -1, -1):
            while stk and nums[stk[-1]] <= nums[i]:
                ans = max(ans, i - stk.pop())
            if not stk:
                break
        return ans

Continue Practicing

#581 shortest unsorted continuous subarray #1574 shortest subarray to be removed to make array sorted #321 create maximum number