Stacks — LIFO & Matching

Review boundary and corrected contracts

RPN division must truncate toward zero without converting large integers to float. Compute the quotient of absolute values and restore its sign. Division by zero remains an error; tokens must encode a valid expression. MinStack supports queries only when nonempty.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for stacks & queues is in the 6-month plan: S026 — theory.

Learning objective: Own the LIFO primitive: bracket matching via push-expect-pop, O(1) minimum via a parallel auxiliary stack, and postfix evaluation as the same idea applied to operands.

Series: LeetCode — From Basics to Production-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 consuming completed subexpressions in postfix notation (which needs no precedence table). 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 design review 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.

The bracket function below accepts only the six bracket characters; it is not a tokenizer for arbitrary source code, strings, comments or HTML. 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. Equal heights remove the need to decide whether a popped value set a new minimum, at the cost of O(n) extra space. A conditional min stack is also correct if it records every value less than or equal to the current minimum, then removes one minimum whenever the outgoing value equals it. For pushes 3, 1, 1, that auxiliary stack is [3, 1, 1]; after one pop its top must still be 1. A strictly-less push rule without counts loses that duplicate. Both approaches have O(n) worst-case storage; the equal-height version has fewer conditions.

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: (-(abs(a) // abs(b)) if (a < 0) != (b < 0) else abs(a) // abs(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 under a tight review; 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. Under a tight review 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.

The counter-based solution is the single most common wrong answer here, and it is seductive because it works for the single-bracket-type version of the problem. If a problem only ever uses ( and ), a counter genuinely suffices — increment, decrement, fail if it ever goes negative, fail if it is non-zero at the end. The moment a second bracket type appears, a counter cannot represent which type is open where, and you need the stack. Knowing exactly where the counter stops working is more useful than knowing that the stack always works.

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 (-(abs(a) // abs(b)) if (a < 0) != (b < 0) else abs(a) // abs(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 under a tight review.

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 (-(abs(a) // abs(b)) if (a < 0) != (b < 0) else abs(a) // abs(b)). Do not replace this with -(-a // b): that computes a ceiling, so for a=7, b=2 it gives 4 rather than 3. Converting through int(a / b) can round or overflow before truncation for large integers. The absolute-value quotient plus sign works for either sign of a nonzero divisor.

Conditional pushes to the min stack. Strictly-smaller pushes without duplicate counts fail after pushing the minimum twice and popping it once. Either keep heights equal as above, or push on <= and pop one auxiliary entry when the outgoing value equals its top. Equality handling, not conditional storage itself, decides correctness.

Myth: Valid Parentheses can be solved with counters — one counter per bracket type — since a stack is just tracking how many of each are open.

Why: A counter records how many brackets of a type are open but discards the order in which they opened, and order is precisely what nesting means. The string '([)]' has one of each type open and closed, so all counters balance, yet it is invalid because the square bracket opened after the round one and must therefore close before it. The stack is not a counting device; it is an ordering device. Counters are sufficient only in the degenerate single-bracket-type case.

Steps 1: Because nesting means an inner construct must be fully closed before its enclosing construct can close, the resolution order of open items is exactly the reverse of their creation order.

Steps 2: Because reverse-of-creation order is the definition of LIFO, the set of unresolved openers is precisely a stack — no other structure encodes that constraint natively.

Steps 3: Because each closer resolves exactly one opener, and it is always the most recent unresolved one, a single pop-and-compare fully validates that closer in O(1).

Steps 4: Because every character is pushed at most once and popped at most once, the total work is bounded by 2n, giving O(n) time.

Steps 5: Because a stack only mutates at one end, a summary with a constant-time update from the previous summary — such as minimum, maximum or a fixed-width running sum — can be maintained in a parallel stack of equal height, making that query O(1) and its undo exact. This does not make arbitrary derived queries, such as a median, constant-time.

Steps 6: Testable prediction: '([)]' must return False while '()[]' returns True. Any solution using only counters will return True for both, which is how you can tell the two approaches apart with a single input.

Picture: A spike file on a desk — the old spindle receipts get impaled on. You can only add to the top and only take from the top. Whatever you jammed on last is the only thing you can reach, and that is a feature, not a limitation.

Trigger: Fires on paired delimiters, the word 'nested', anything described as 'undo' or 'most recent', and on postfix expression evaluation.

Name: Two parallel stacks (data + mins)

Gain: Both stacks always the same height, so pop needs no comparison and no special case; straightforward to keep consistent; reads are O(1), and Python list end-updates are amortised O(1).

Cost: O(n) extra space even when the minimum rarely changes — a strictly increasing input stores the same value n times.

Name: Single stack of (value, running_min) tuples

Gain: One structure to keep consistent instead of two, so it is impossible for the heights to desynchronise; the same O(1) reads and amortised O(1) list end-updates.

Cost: Tuple allocation per push has a real constant-factor cost in Python, and top() needs an index into the tuple, which reads slightly worse.

Name: Conditional min stack (record smaller or equal minima)

Gain: Stores only record minima and their equal repetitions, potentially fewer than n entries; worst-case space is still O(n). A value/count variant can compress repetitions.

Cost: Pop must compare the outgoing value against the min-stack top to decide whether to pop it too, and the comparison is wrong on duplicate minima unless you handle equality explicitly. More states to get right under time pressure.

Pick: Use equal-height stacks for the simplest invariant. Conditional minima are also valid with the explicit equality policy above; neither approach improves the O(n) worst-case bound.

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) reads, amortised O(1) push/pop, 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.

These implementations use O(n) worst-case stack entries, not a universal lower bound for every problem variant or computational model. With multiple bracket types an exact one-pass validator must retain nesting-order information; a single type needs only a balance counter. RPN storage depends on the maximum pending-operand depth. Arithmetic costs and integer storage also grow with operand bit length, so O(n) RPN time here counts arithmetic operations rather than arbitrary-precision bit operations.

Self-check (answer follows each question).

Q: Why is the pairs dictionary keyed by closing bracket rather than opening bracket?

A: The decision point is the closer: ch in pairs becomes a clean test for 'is this a closer', and pairs[ch] directly gives the opener that must be on top. Keyed the other way you need a separate membership set for closers plus an inverted lookup.

Q: Name the three separate conditions Valid Parentheses must check, and which line catches each.

A: Stack non-empty when a closer arrives (the not stack guard), popped opener matches the closer's type (stack.pop() != pairs[ch]), and nothing left open at the end (return not stack).

Q: In RPN evaluation, why must you pop the right operand before the left?

A: The stack returns operands in reverse order of arrival, so the first pop is the most recently pushed, which is the right-hand operand. For subtraction and division the order is not commutative, so reversing it produces wrong answers.

Q: Why push min(val, current_min) unconditionally instead of only when val is a new minimum?

A: Equal stack heights make pop unambiguous — it always pops both. Conditional pushing forces pop to compare the outgoing value against the min-stack top to decide whether to remove it, and that comparison needs an explicit duplicate policy; pushing every value <= the current minimum is a correct alternative.

Q: What single input distinguishes a correct stack solution from a counter-based one?

A: '([)]'. Counters balance for both bracket types so a counter solution returns True, but the nesting is interleaved and invalid, so the stack solution correctly returns False.

Q: Basic Calculator requires evaluating infix expressions with parentheses and unary minus, but no operator-precedence table. How does the stack usage differ from RPN?

A: Instead of holding operands only, you push the accumulated result and the pending sign when you meet an open bracket, reset the accumulator for the sub-expression, then on the close bracket pop the sign and prior result and fold them back in. The stack stores suspended context rather than operands — the same LIFO principle applied to computation state rather than data.

Stretch: true

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.

• Nesting, matching, undo and postfix evaluation are one idea: the most recently opened thing must close first.

• Valid Parentheses needs three checks, not one — non-empty on close, type match on pop, empty at the end.

• Counters can express how many brackets are open but not the order, which is why '([)]' defeats them and a stack is required.

• Key the pairs dictionary closer-to-opener, because the closer is where the decision happens.

• For O(1) derived queries on a stack, maintain a parallel stack of equal height — equal heights make pop decision-free.

• In RPN, pop the right operand first, and use (-(abs(a) // abs(b)) if (a < 0) != (b < 0) else abs(a) // abs(b)) rather than // because Python floors toward negative infinity.

Corrective source notes

• CPython v3.14.0 numeric types — integer precision, floor-division direction and float-to-int truncation. Checked 2026-10-09; the earlier right-shift quotation was not evidence for this lesson's RPN division claim.
• CPython v3.14.0: lists as stacks — append and end-pop implement LIFO. Checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.