Stacks & Monotonic Stack

A stack remembers "what's still open". Reach for one whenever the most recent unfinished thing is the one you must deal with first: brackets, nested structures, undo, and — the interview favorite — monotonic stacks for next-greater/smaller queries.

Recognize it

• Brackets/nesting/"valid sequence".
• Decode/parse with nested scopes (3[a2[c]]).
• "Next greater/smaller element", "how many days until warmer", histogram areas.
• Simulation where things collide with or cancel the latest survivor.

Templates

# Matching
def valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for c in s:
        if c in "([{":
            st.append(c)
        elif not st or st.pop() != pairs[c]:
            return False
    return not st

# Monotonic stack — next greater element to the right
def next_greater(nums):
    res = [-1] * len(nums)
    st = []                          # indices, values strictly decreasing
    for i, x in enumerate(nums):
        while st and nums[st[-1]] < x:
            res[st.pop()] = x        # x is the answer for everything smaller
        st.append(i)
    return res

Each index is pushed and popped at most once → O(n) despite the nested loop.

Key variations

• Store indices, not values — distances (Daily Temperatures) and widths (Largest Rectangle) need them.
• Circular array: iterate 2n times with i % n — Next Greater Element II.
• Increasing vs decreasing: next greater → keep the stack decreasing; next smaller → increasing. Strict vs non-strict handles duplicates — decide before coding.
• Histogram: when a bar pops, its rectangle's height is the popped bar, width spans to the new stack top — Largest Rectangle in Histogram; append a sentinel 0 to flush.
• Build-a-smaller-number greedily: pop while the top is bigger than the incoming digit and removals remain — Remove K Digits.
• Two stacks / stack with metadata: Min Stack stores (value, min-so-far) pairs; Implement Queue Using Stacks amortizes transfers.

Classic problems

• Valid Parentheses — matching
• Min Stack — auxiliary min
• Evaluate Reverse Polish Notation — operand stack
• Decode String — nested scopes
• Simplify Path — .. pops
• Asteroid Collision — collision simulation
• Daily Temperatures — monotonic, distances
• Largest Rectangle in Histogram — the hard classic
• Valid Parenthesis String — range of open counts (stack-free twist)

Pitfalls

• Popping an empty stack — guard every pop.
• Forgetting the flush at the end: leftover stack items are the "no answer" cases (or need a sentinel to force them out).
• Duplicates and strict/non-strict comparison change answers — test [2,2,2].
• RPN in Python: integer division toward zero is int(a / b), not a // b.