Edmondo's Vault

Monotonic Stack

May 18, 20263 min read

The monotonic stack is an approach that can be used to solve many algorithmic problem. :

  1. Maintains visibility dynamically:

    • By popping elements that are shorter than the current element, you’re effectively determining all the people visible to the current person in one go.
    • Any “hidden” elements are automatically removed during the popping process because:
      • They are shorter than the person currently being processed.
      • A taller person already obscures them for any further visibility checks.

  2. Ensures correctness “magically”:

    • When you pop an element from the stack, you increment the visibility count (sol[j]).
    • By maintaining a stack of indices of decreasing heights, the popping process simulates blocking and handles hidden elements for you.

Are Left-to-Right and Right-to-Left Traversals Equivalent?

No, they are not always equivalent. The choice depends on:

  1. The direction of dependencies between elements (e.g., “previous” or “next”).
  2. The type of information you need (e.g., “next greater” or “previous smaller”).

For example:

  • Right-to-left traversal is often needed when the solution depends on elements to the right of the current element.
  • Left-to-right traversal works well when the solution depends on elements to the left of the current element.

Why Does 132 Pattern Require Right-to-Left Traversal?

For the 132 Pattern, you need:

  1. A candidate for the “3” (largest element in the pattern).
  2. A candidate for the “2” (intermediate element smaller than the “3”).
  3. The current number being processed as the “1”.

How to Decide Between Left-to-Right and Right-to-Left?

Here are some guidelines:

1. Do You Need “Next” or “Previous” Information?

  • Next Information (e.g., “next greater element”):
    • Use left-to-right traversal.
    • Example: Next Greater Element I, Daily Temperatures.
  • Previous Information (e.g., “previous smaller element”):
    • Use right-to-left traversal.
    • Example: 132 Pattern.

2. Are You Building Dependencies on the Fly?

  • If you need to process future elements to determine the current state, use right-to-left.
  • If you can determine the current state solely based on the past, use left-to-right.

3. Are You Optimizing for Multiple Passes?

  • Some problems (e.g., Sum of Subarray Minimums) require both previous and next information. In such cases:
    • Perform one pass left-to-right for “previous”.
    • Perform another pass right-to-left for “next”.

Can the 132 Pattern Be Solved Left-to-Right?

It’s possible but significantly harder and less efficient. Here’s why:

  1. You’d need to track:
    • The global minimum (1) up to the current point.
    • Potential “2” and “3” candidates for every element dynamically.
  2. This would require:
    • Either multiple passes over the array or maintaining additional data structures.

The right-to-left solution with a monotonic stack is both cleaner and more efficient ((O(N))).

Key Takeaways

  1. Right-to-Left:

    • Works well when the solution depends on future elements.
    • Examples: 132 Pattern, Next Smaller Element (or reverse).

  2. Left-to-Right:

    • Works well when the solution depends on past elements.
    • Examples: Next Greater Element, Stock Span.

  3. Dual Pass:

    • Use when the problem involves both “next” and “previous” dependencies.
    • Example: Sum of Subarray Minimums.

Let me know if you’d like to go through another example to solidify this concept! 😊

Graph View

Backlinks