Daily Challenge 10/10/2024: Maximum Ramp Width

Find the largest difference between two indices with increasing value in their corresponding array values.

The full problem statement may be found on leetcode.

Analysis

The phrasing of the problem is obfuscatory - the objective is to look for a pair of indices \(i, j\) for an array \(a: S\subset \mathbb{N} \to \mathbb{N}\) such that \(i \lt j\) and \(\phi(i) \leq \phi(j)\) and \(j - i\) is maximal.

This is actually a rather tricky problem - I had never encountered the monotonic stack approach until today.

Monotonic Stacks

A monotonic stack is a stack where elements are ordered monotonically. wow! What a shock that is. To make this happen, when an element that does not obey the ordering is pushed, elements are removed from the top until the new element can be pushed and maintain monotonicity.

Initial stack:             1 -> 2 -> 5
Stack when 3 is pushed:    1 -> 2 -> 3
Stack when 7 is pushed:    1 -> 2 -> 3 -> 7
Stack when 4 is pushed:    1 -> 2 -> 3 -> 4

The following example will push elements onto a stack with monotonic rules:

def push(stack: list[int], value: int, *, _top: int | None = None) -> int:

    top = _top or (len(stack) - 1)
    while stack and stack[top] > value:
        stack.pop()
        top -= 1

    stack.append(value)

    return top

and we can reproduce the above by running the following code:

stack = [] 

for item in [1, 2, 5, 3, 7, 4]:
  push(stack, item)
  print(f"After push {item}:", stack)

After push 1: [1]
After push 2: [1, 2]
After push 5: [1, 2, 5]
After push 3: [1, 2, 3]
After push 7: [1, 2, 3, 7]
After push 4: [1, 2, 3, 4]

Algorithm

stack = [0, 1]
nums = 6  0  8  2  1  5


6  0  8  2  1  5
               ^  index = 5, max_width = max(0, 5 - 1)

6  0  8  2  1  5
               ^  index = 5, max_width = max(4, 5 - 0)


stack is empty, stop.

Solution

class Solution:
    def maxWidthRamp(self, nums: list[int]) -> int:

        n = len(nums)
        stack: list[int] = []

        for index in range(n):
            num = nums[index]
            if not stack or nums[stack[-1]] > num:
                stack.append(index)

        max_width = 0
        for k in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[k]:
                max_width = max(max_width, k - stack.pop())

        return max_width