Monotonic Stack

The monotonic stack is the pattern people find magical: a plain stack, kept in sorted order, that answers “what’s the next bigger thing?” for every element in O(n) total. It feels like it should be O(n²), and the reason it isn’t is the heart of the trick.

The idea

Keep a stack whose values are always in order (say, decreasing). Walk the array:

• While the stack’s top is smaller than the current element, pop it — and the current element is that popped element’s “next greater”. Record the answer at the moment of popping.
• Then push the current element (its index).

Each element is pushed once and popped at most once, so the total number of operations is O(n) — even though the inner “while pop” loop makes it look quadratic. The stack is acting as a memory of “elements still waiting for their next-greater.”

The template: daily temperatures

“For each day, how many days until a warmer temperature?” — store indices so you can compute the distance:

def daily_temperatures(T):
    res = [0] * len(T)
    stack = []                         # indices, temps decreasing
    for i, t in enumerate(T):
        while stack and T[stack[-1]] < t:
            j = stack.pop()            # day j finally gets a warmer day
            res[j] = i - j             # distance
        stack.append(i)
    return res
# daily_temperatures([73,74,75,71,69,72,76,73]) -> [1,1,4,2,1,1,0,0]

Decreasing stack → next greater. Flip the comparison for an increasing stack → next smaller.

Worked example: largest rectangle in histogram

The famous hard one. For each bar, you want the widest rectangle it can anchor — bounded by the first smaller bar on each side. A monotonic (increasing) stack finds those boundaries in O(n):

def largest_rectangle(heights):
    stack = []; best = 0
    heights = heights + [0]            # sentinel flushes the stack at the end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1 if stack else i   # span to the left boundary
            best = max(best, height * width)
        stack.append(i)
    return best
# largest_rectangle([2,1,5,6,2,3]) -> 10   (5 and 6 → 2 wide × 5 high)

The same machinery (find the span bounded by smaller elements on both sides) solves trapping rain water and maximal rectangle in a binary matrix.

Step-by-step walkthrough

Trace Daily Temperatures on [73, 74, 75, 71, 69, 72, 76, 73]. The stack holds indices of days still waiting for a warmer day, in decreasing temperature order. Each new day pops every colder day it beats — and those days get their answer.

Every index is pushed once and popped at most once, so it’s O(n). Final answer: [1, 1, 4, 2, 1, 1, 0, 0].

When to reach for it

Signals: “next greater / next smaller element”, “how many steps until a bigger value” (daily temperatures, stock span), histogram / rectangle area, trapping rain water. Whenever you need, for each element, the nearest bigger-or-smaller neighbour, reach for a monotonic stack.

Pitfalls

• Storing values instead of indices. Most of these problems need distances or widths, so store indices and look up values as needed.
• Wrong monotonic direction / comparison. Decreasing stack gives next-greater; increasing gives next-smaller. Pick based on what you’re answering, and be careful with > vs >= (ties).
• Forgetting the sentinel. A trailing 0 (or iterating one past the end) flushes any elements still on the stack at the end — otherwise their answers are never recorded.

Recap

A monotonic stack keeps elements in sorted order; when a new element breaks the order you pop and answer each out-of-order element (its next greater/smaller). Each element enters and leaves once → O(n). Store indices; decreasing stack = next-greater, increasing = next-smaller. Signal: next greater/smaller, days-until, histogram, rain water.

Practice: 11 solved problems on monotonic stack → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 10 — Binary Search, halving the search space.