L16 · Stacks — LIFO & Matching

Series: LeetCode — From Basics to Interview-Ready · Session 16 / 65 · Phase 1 · Core patterns

Why this session exists

Nesting, matching, undo, and expression evaluation look like four different topics. They are one idea wearing four hats, and the idea is: the most recently opened thing is the first thing that must close.

That sentence is the definition of a stack, and it is also, word for word, the rule for balanced brackets, for undo history, for function call frames, and for operator precedence in postfix notation. When you learn to hear it in a problem statement, a category of problems collapses into a single template.

The reason this session sits here rather than earlier is that the next session — monotonic stacks — is one of the highest-leverage patterns in the whole interview canon, and it is unlearnable if the plain stack is not automatic. You cannot reason about "pop while the invariant is violated" if you are still thinking about whether pop returns the element or just removes it.

There is a second, quieter lesson here that generalises well beyond stacks: when a query is too slow, store the answer alongside the data instead of computing it on demand. Min Stack is the smallest possible illustration. Getting the minimum of a stack is O(n) if you scan; it is O(1) if you maintain a second stack whose top is always the current minimum. That trade — a bit of extra space and a bit of extra bookkeeping on every write, in exchange for a fast read — is the shape of a large fraction of all data structure design.

Blank-file warm-up

Five minutes, empty file, no notes. Write:

1. The pairs dictionary that maps each closing bracket to its opener.
2. The full is_valid loop using a list as a stack.

Write the dictionary in the closer-to-opener direction, not opener-to-closer. If you wrote it the other way, that is today's first finding — it makes the loop clumsier, and the reason is worth understanding before you read on.

Pattern anatomy

The shape that summons this pattern: a linear scan where the meaning of the current element depends on the most recent unresolved element before it.

For bracket matching the invariant is:

The stack holds, bottom to top, exactly the opening brackets that have been seen and not yet closed, in the order they were opened.

Every step must preserve that. An opener is unresolved by definition, so push it. A closer resolves exactly one opener — the most recent one — so pop and check it matches. At the end, an empty stack means everything got resolved.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}     # closer -> opener
    stack = []
    for ch in s:
        if ch in pairs:                        # it is a closer
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                                  # it is an opener
            stack.append(ch)
    return not stack

The dictionary is keyed by closer because the closer is where the decision happens. ch in pairs is then a clean test for "is this a closing bracket", and pairs[ch] immediately gives what must be on top. Keyed the other way you need a separate membership set and an inverted lookup.

Three things must all be checked and people usually check two: the stack is non-empty, the popped element matches, and the stack is empty at the end. Drop the first and ")" crashes. Drop the last and "(" returns True.

Min Stack is the auxiliary-state idea:

class MinStack:
    def __init__(self):
        self._data = []
        self._mins = []                 # _mins[i] = min of _data[0..i]
 
    def push(self, val):
        self._data.append(val)
        self._mins.append(val if not self._mins else min(val, self._mins[-1]))
 
    def pop(self):
        self._data.pop()
        self._mins.pop()
 
    def top(self):
        return self._data[-1]
 
    def get_min(self):
        return self._mins[-1]

Both stacks always have the same height, so pop is trivially consistent. The subtle correctness point is min(val, self._mins[-1]) rather than pushing only when val is a new minimum: pushing conditionally makes pop ambiguous, because you would have to decide whether the popped value was the one that set the current minimum. Equal heights removes the decision entirely, at the cost of O(n) extra space. That is the right trade under interview conditions — a correct O(n) beats a subtly broken O(k).

And RPN evaluation, where the stack holds operands rather than expectations:

def eval_rpn(tokens):
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),      # truncate toward zero, NOT floor
    }
    stack = []
    for t in tokens:
        if t in ops:
            b = stack.pop()                # second operand pops FIRST
            a = stack.pop()
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

b before a. The stack returns them in reverse order of arrival, and for subtraction and division that reversal is the difference between right and wrong.

The cue

How you recognise this from the problem statement:

1. Brackets, parentheses, tags, or any paired delimiters. Near-diagnostic. Valid Parentheses, Remove Invalid Parentheses, Longest Valid Parentheses, Basic Calculator — all stacks.
2. The word "nested". Nested lists, nested encodings ("3[a2[c]]"), nested directory paths. Nesting is a stack by definition, because you must finish the inner thing before the outer thing.
3. "Undo", "backtrack", "most recent", "last". Any language that points at recency rather than order-of-arrival.
4. Postfix / prefix / Reverse Polish notation, or any expression evaluation. The whole point of postfix is that it is evaluable with a single stack and no precedence rules.
5. An O(1) query on a structure that only changes at one end. Min Stack, max stack, stack with running sum. The one-end constraint is what makes the parallel-array trick work — you can undo the auxiliary state exactly because writes and deletes happen at the same place.

The anti-cue: if elements must be removed from the front while being added at the back, you want a queue, not a stack. And if you find yourself wanting to inspect elements deep in the stack rather than just the top, stop — you are probably reaching for the wrong structure, or you actually need the monotonic variant coming in the next session.

Guided solve

Valid Parentheses. Given a string containing only (, ), [, ], {, }, decide whether it is validly nested.

Before code, get precise about what "valid" means. Three conditions, all necessary:

• Every closing bracket matches the type of the most recent unmatched opening bracket.
• No closing bracket appears when there is nothing open.
• Nothing is left open at the end.

Most wrong answers to this problem drop one of the three. So write all three down before you start, and then make sure each has a corresponding line of code. That mapping — condition to line — is worth saying out loud in an interview; it shows you are working from a specification rather than from pattern memory.

Trace "{[()]}":

• { opener, push. Stack: ['{']
• [ opener, push. Stack: ['{', '[']
• ( opener, push. Stack: ['{', '[', '(']
• ) closer. Stack non-empty. Pop gives (. pairs[')'] is (. Match. Stack: ['{', '[']
• ] closer. Pop gives [. Match. Stack: ['{']
• } closer. Pop gives {. Match. Stack: []
• Loop ends, stack empty. True.

Now the three failure inputs, each isolating one condition:

"([)]" — at ), the top is [, not (. Type mismatch, False. This is the case that a naive counter-based solution gets wrong: counting opens and closes gives 2 and 2 and says valid. Counting cannot express nesting, which is exactly why you need a stack rather than three integers.

")(" — at ), the stack is empty. Without the not stack guard this raises IndexError rather than returning False. In an interview a crash reads much worse than a wrong answer.

"((" — the loop completes with the stack holding two openers. The final return not stack is what catches it.

Solo timed

15 minutes each, timer visible.

• Min Stack — keep two stacks of equal height; push min(val, current_min) unconditionally so pop never has to decide anything.
• Evaluate Reverse Polish Notation — pop the right operand before the left, and use int(a / b) for division because Python's // floors toward negative infinity while the problem specifies truncation toward zero.

If you finish early: implement Min Stack again using a single stack of tuples (value, running_min) and decide which version you would actually write in an interview.

Common failure modes

Popping from an empty stack. Every pop on a closer needs a preceding emptiness check. The input "]" should return False, not crash.

Forgetting the final emptiness check. "(((" consumes cleanly and returns True if you end with a bare return True. The last line must be return not stack.

Matching count instead of type. Tracking a counter, or even a per-type counter, cannot detect "([)]". Only the ordering information in the stack can.

Operand order in RPN. stack.pop() gives the right operand first. Writing a = pop(); b = pop() silently computes b - a and b / a. Addition and multiplication hide the bug; subtraction and division expose it.

Python's floor division in RPN. -7 // 2 is -4; the problem wants -3. Use int(a / b), or -(-a // b) if you want to avoid floats entirely on very large integers.

Conditional pushes to the min stack. Pushing to _mins only when a new minimum appears creates an asymmetry that pop cannot resolve without comparing values, and the comparison breaks on duplicate minimums. Keep the heights equal.

Complexity

Valid Parentheses — Time: O(n), Space: O(n). Each character is examined once and causes at most one push and at most one pop, so total stack operations are bounded by 2n. Space is worst case n when the input is all openers, such as "(((((".

Min Stack — Time: O(1) per operation, Space: O(n). Push does two appends, pop does two pops, top and get_min are single index reads. Amortised O(1) for append is the standard dynamic-array result; the occasional resize is O(n) but happens on a geometric schedule.

Evaluate RPN — Time: O(n), Space: O(n). One pass; each token pushes once, each operator pops twice and pushes once. Peak stack depth equals the maximum number of pending operands, which for valid RPN never exceeds the token count.

The space bound is genuinely O(n) in all three and not reducible — you cannot validate nesting depth n without recording n items, because you must be able to recall the type of every unclosed opener.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Valid Parentheses enters at whatever the blank-file attempt earned. Be strict: if you wrote the loop but forgot either the empty-stack guard or the final emptiness check, that is hint at best. Both omissions are wrong answers on real inputs.