Skip to content

962.maximum-width-ramp.md

Latest commit

 

History

History
215 lines (171 loc) · 9.42 KB

962.maximum-width-ramp.md

File metadata and controls

215 lines (171 loc) · 9.42 KB

962. Maximum Width Ramp

Two Pointers

To maximum the width j - i, we want two things:

  1. The smallest number before (Easy to find the larger number later)
  2. The largest number after (Easy to find the smaller number earlier)

We can pre-compute the two information for every single index:

  • Prefix minimum: The minimum value we've seen so far from the left side. This answers the question: "If I am forced to pick a starting number before/at index i, what is the smallest (best) choice?"
A = [6, 0, 8, 2, 1, 5]
--> min
     6  0  0  0  0  0
  • Suffix maximum: The maximum value we've seen so far from the right side. This answers the question: "If I am forced to pick a ending number after/at index j, what is the largest (best) choice?"
A = [6, 0, 8, 2, 1, 5]
              max <--
     8  8  8  5  5  5

Please note that both the prefix minimum and suffix maximum are decreasing order, it's a key observation for the following explanation in two pointers and monotonic stack approach.

Because both the prefix minimum and suffix maximum are sorted in descending order (when reading from left to right), then we can use two pointers to find the maximum ramp.

  • left: Scan the prefix minimum to look for starting candidate.
  • right: Scan the suffix maximum to look for ending candidate.

We iterate each index, and for each left pointer, we try to find the maximum right pointer such that prefix minimum <= suffix maximum:

  • If minBefore[left] > maxAfter[right], the starting candidate is too large to match the ending candidate.
    • We need smaller starting candidates, so we move left + 1 because the prefix minimum gets same or smaller as we move right.
    • Moving right + 1 will gets same or smaller suffix maximum as well, and minBefore[left] > maxAfter[right], smaller maxAfter[right] makes the situation worse.
  • If minBefore[left] <= maxAfter[right], it's a match.
    • Update the maximum width with right - left accordingly.
    • Move the right + 1 to get a wider ramp.
    • Why not moving the left? Because moving left gets the narrower ramp. We know moving right will make maxAfter[right] smaller, but it's the only direction that increase the width.
A = [6, 0, 8, 2, 1, 5]
     6  0  0  0  0  0   // prefix minimum
     8  8  8  5  5  5   // suffix maximum
     L
     |-----R            // The longest ramp starting from `6`
           
// Next iteration
        L
        |-----------R   // The longest ramp starting from `0`, the final answer

The monotonicity provides the predictability, we know exactly what happens when we move the pointers:

  1. Moving left + 1: The prefix minimum will stay the same or decrease, which makes it easier to find a matching ending candidate.
  2. Moving right + 1: The suffix maximum will stay the same or decrease, which makes it harder to find a matching starting candidate, but it makes a potential wider ramp.

We never need to move a pointer backwards.

  • If a ramp is valid, we expand the right pointer to find a wider ramp.
  • If a ramp is invalid, we fix by moving left to find a smaller starting candidate.
fun maxWidthRamp(nums: IntArray): Int {
    val n = nums.size
    val minBefore = IntArray(n)
    val maxAfter = IntArray(n)
    minBefore[0] = nums[0]
    for (i in 1 until n) {
        minBefore[i] = minOf(nums[i], minBefore[i - 1])
    }
    maxAfter[n - 1] = nums[n - 1]
    for (i in n - 2 downTo 0) {
        maxAfter[i] = maxOf(nums[i], maxAfter[i + 1])
    }

    var i = 0
    var j = 0
    var maxWidth = 0
    while (j < n) {
        if (minBefore[i] <= maxAfter[j]) {
            maxWidth = maxOf(maxWidth, j - i)
            j++
        } else {
            i++
        }
    }
    return maxWidth
}
  • Time Complexity: O(n) for pre-computing the prefix minimum and suffix maximum, and O(n) for two pointers scan, total O(n).
  • Space Complexity: O(n) for the prefix minimum and suffix maximum.

Sorting

There are two rules to form a valid ramp:

  1. Value Rule: nums[i] <= nums[j].
  2. Index Rule: i < j, and try to maximize the width j - i.

We can use sorting to solve the Value Rule first, so we only have to care about the Index Rule after that.

Step 1: Solve Value Rule by Sorting

We need to sort the value, but meanwhile we also need to keep track of the original index. So we can create an array of indices and sort the indices by its value.

nums  = [7, 6, 5, 8]
index = [0, 1, 2, 3]

// Sort the index by its value
     values = [5, 6, 7, 8]
sortedIndex = [2, 1, 0, 3]

Step 2: Solve Index Rule by Scanning

After sorting, all values after nums[i] are >= nums[i], that is, all later number will be a valid ending candidate.

To find the maximum width, we iterate the sorted index as the ending index j, and keep track of the minimum starting index i we've seen so far. The width is j - i, and we update the maximum width accordingly.

fun maxWidthRamp(nums: IntArray): Int {
    val n = nums.size
    val index = IntArray(n)
    for (i in nums.indices) {
        index[i] = i
    }
    val sortedIndex = index.sortedBy { nums[it] }
    var minIndex = sortedIndex.first()
    var maxWidth = 0
    for (i in 1 until n) {
        maxWidth = maxOf(maxWidth, sortedIndex[i] - minIndex)
        minIndex = minOf(minIndex, sortedIndex[i])
    }
    return maxWidth
}
  • Time Complexity: O(n log n) for sorting.
  • Space Complexity: O(n) for the sorted index.

Monotonic Stack

Key Insights

Think the key questions before diving deep into this approach:

Q1. Suppose we're looking for the starting index i, and we have 6 at index 0, then next we have 8 at index 1, could index 1 ever be a better starting index than index 0 for the maximum width ramp?

No, because 6 is smaller than 8 and the index 0 is smaller than index 1, it's easier to match a larger number later and get a wider ramp. So if we have a smaller number before, then we can ignore the larger number at the later index. We keep track of the valid starting candidates in a decreasing order, and we only care about the smaller numbers.

6, _, _, 8, _, _, 9, _, _
O        X        X

6, 5, 3, _, 0, ....
O  O  O     O

Notice the pattern from two pointers approach above? Both the prefix minimum and suffix maximum are monotonically decreasing. This is key observation for monotonic stack approach.

Q2. After gathering all the valid starting indices i, and our goal is to maximize the width j - i, how do we find the maximum width ramp?

To find the maximum j - i, we aim to have larger j and smaller i. So we should scane the array from right to left to find the valid ending index j.

Based on the above key insights, we can break the problem into two phases:

Phase 1: Building the Starting Indices i

Since the larger number at the later index can never be a better starting candidate than the smaller number at the earlier index, we can maintain a monotonic decreasing stack to store the valid starting indices.

Let's take the example A = [6, 0, 8, 2, 1, 5] to illustrate how we build the stack:

  • nums[0] = 6, the stack is empty, it's a candidate.
  • nums[1] = 0, it's smaller than 6, so it's also a candidate, we pop 6 and push 0.
  • nums[2] = 8, it's larger than 0, so we ignore it. Why? Because 0 is smaller and smaller index. Any valid j for 8 would also be valid for 0, but 0 can potentially get a wider ramp than 8.
  • Later numbers are larger than 0, so we ignore them, the stack is [0, 1] after phase 1.

Phase 2: Finding Valid Ending Indices j

Now we find the ending index j, to maximum the width j - i, we scan from right to left and keep track of the maximum width.

  • nums[j] = 5: It's larger than stack.last() = 0, it's valid ramp.

    • The magic step: Once we find a valid ramp, we pop the starting index from stack forever. Why? Because as we iterating from right to left, j becomes smaller. Even if we find another valid ramp with the same starting index, the width will be smaller than the current ramp.
    6, 0, _, _, 1, 5
   i-----------j    // valid, final answer
            <--
   i--------j       // valid, but narrower
   ...
    • We should keep checking the same j agaist the stack until j is no longer valid. (The stack becomes empty or meets the larger number than nums[j])

  • nums[j] = 1: It's larger than stack.last() = 0, it's valid ramp. We do the same thing as above.

  • Keep moving j to the left until the stack becomes empty or the end of the array.

fun monotonicStack(nums: IntArray): Int {
    // Index, decreasing stack, store the valid starting element.
    val stack = ArrayDeque<Int>()

    // Find the valid starting `i`
    for (i in nums.indices) {
        if (stack.isEmpty() || 
            (stack.isNotEmpty() && nums[stack.last()] > nums[i])) stack.addLast(i)
    }

    var maxWidth = 0
    // Iterate from right to left backward to find the valid ending `j`
    for (j in nums.size - 1 downTo 0) {
        // No any valid starting index.
        if (stack.isEmpty()) break
        while (stack.isNotEmpty() && nums[stack.last()] <= nums[j]) {
            val i = stack.removeLast()
            maxWidth = maxOf(maxWidth, j - i)
        }
    }
    return maxWidth
}
  • Time Complexity: O(n). Each index is pushed and popped at most once.
  • Space Complexity: O(n) for the stack.