Stacks & Monotonic Stacks cheatsheet

📚 Stacks & Monotonic Stacks

Push what's still unresolved; the newest item is resolved first. Keep the stack monotonic to answer 'next greater/smaller' in O(n).

Study the unit Practice this pattern

Recognize the pattern

Brackets / tags / nesting must be valid or matched → push openers, pop on closers
Undo, backspace, 'remove adjacent pairs', simplify a path → stack of what's kept so far
Evaluate postfix / an expression → stack of operands (and operators)
Need min/max of 'everything so far' after pops → push (value, running min) pairs
For each element, the next/previous greater or smaller → monotonic stack of indices
'How many days until warmer', spans, cars catching up → next greater in disguise
Largest rectangle / widest window bounded by the smallest bar → increasing stack

List as a stack

Only touch the end of the list. Guard peeks and pops with if stack.

Python template

stack: list[int] = []
stack.append(1)        # push
top = stack[-1]        # peek (IndexError if empty)
x = stack.pop()        # pop
if not stack:          # empty?
    pass

Matching brackets

Python template

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack   # unclosed openers?

Stack with extra state (min stack)

Each entry remembers a fact about itself and everything below it. The snapshot stays valid until it's popped.

Python template

stack: list[tuple[int, int]] = []  # (val, min so far)

def push(x: int) -> None:
    low = min(x, stack[-1][1]) if stack else x
    stack.append((x, low))

def get_min() -> int:
    return stack[-1][1]

Postfix evaluation

Pop the right operand first. Truncate division toward zero with int(a / b) (not //).

Python template

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    for t in tokens:
        if t in {"+", "-", "*", "/"}:
            b, a = stack.pop(), stack.pop()
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[-1]

Monotonic stack: next greater

Store indices. For next smaller, flip the comparison to >. For previous greater/smaller, read stack[-1] after popping, before pushing. Circular: loop over range(2 * n) with i % n.

Python template

def next_greater(nums: list[int]) -> list[int]:
    res = [-1] * len(nums)
    stack: list[int] = []  # values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            res[j] = x       # or i - j (distance)
        stack.append(i)
    return res

Sentinel flush (histogram)

Append a 0 so every bar gets popped. When a bar pops, the new top is its left boundary and i its right one.

Python template

def largest_rectangle(h: list[int]) -> int:
    stack, best = [], 0  # indices, heights increasing
    for i, x in enumerate(h + [0]):
        while stack and h[stack[-1]] >= x:
            top = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, h[top] * (i - left - 1))
        stack.append(i)
    return best

Operation costs

Operation	Time	Space
push / pop / peek at the end	O(1)	O(1)
pop(0) / insert(0, x)	O(n)	—
x in stack / min(stack)	O(n)	—
Bracket matching, postfix evaluation	O(n)	O(n)
Monotonic stack pass (each index in/out once)	O(n) total	O(n)

Watch for

Peeking or popping an empty stack raises IndexError: check if stack first (e.g. a closer arriving first).
Forgetting the final check: leftover openers mean the string is NOT valid.
Operand order: b = pop() then a = pop(); a - b and a / b, not the reverse.
-7 // 2 == -4 in Python; truncation toward zero wants -3 (int(a / b)).
Storing values instead of indices in a monotonic stack: you lose distances and widths.
< vs <= in the pop condition changes how equal values are treated; match the problem.