Monotonic Stack

What you'll learn

• What Is It?

  A monotonic stack is a stack that maintains its elements in either strictly increasing or strictly decreasing order. Elements that violate the order are popped before pushing a new element. This enables efficient solutions for "next grea…

• The Four Variants

  | Problem | Traverse Direction | Stack Maintains | Pop Condition | |---------|-------------------|-----------------|---------------| | Next Greater to Right | Right to Left | Decreasing (top = smallest) | stack[-1] = curr | | Next Smalle…

• Pattern 1: Next Greater Element to the Right

  Problem: For each element, find the first element to its right that is greater. Trace: Why O(n)? Each element is pushed once and popped at most once → 2n operations total. ---

• Pattern 2: Stock Span Problem

  Problem: For each day, find how many consecutive days (including today) the price was less than or equal to today's price. This is the "nearest greater to left" variant using indices. Example: ---

• Pattern 3: Largest Rectangle in Histogram

  Problem: Given bar heights, find the largest rectangle area. Key insight: For each bar, the maximum rectangle using that bar's height extends from the nearest shorter bar on the left to the nearest shorter bar on the right. Trace: Single…

• Pattern 4: Maximal Rectangle in Binary Matrix

  Problem: Find the largest rectangle containing only 1s in a binary matrix. Approach: Convert each row into a histogram (height = consecutive 1s above including current row), then apply largest rectangle in histogram for each row. Visual:…

• Pattern 5: Trapping Rain Water

  Problem: Given elevation bars, calculate how much water can be trapped. Insight: Water at each position = min(maxleft, maxright) - height. Use prefix max arrays (or two pointers for O(1) space). O(1) space with two pointers: ---

• Pattern 6: Min Stack (O(1) getMin)

  With extra space: Use a second stack tracking minimum at each state. Without extra space: Store encoded values when a new minimum arrives. Why 2val - min works: If val < min, then 2val - min < val < min. This encoded value acts as a flag…

• Problem Recognition

  | Signal | Pattern | |--------|---------| | "Next greater/smaller element" | Monotonic stack | | "Stock span" / "days until warmer" | NGE with indices | | "Largest rectangle in histogram" | Next smaller left + right | | "Maximal rectangl…

• Complexity

  All monotonic stack problems: - Time: O(n) — each element pushed and popped at most once - Space: O(n) — stack size