Matching with a stack

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Is the bracket string {[()]}( properly balanced? By hand you read left to right and keep track of what is open. Open a curly, open a square, open a round; the round closes, the square closes, the curly closes; then a round opens and nothing ever closes it. Not balanced.

Notice the rule you used without naming it: a closer must close the most recently opened bracket that is still open. That is the only bracket it can legally match, because brackets nest. If you tried to track "what is open" with a plain count (opens minus closes), you would accept the illegal string ([)] where the counts are fine but the nesting is wrong. So the structure must remember which brackets are open and in what order.

Build the structure, one piece at a time

A stack is a pile where you can only put something on top or take the top off. It is exactly "the most recently added thing comes out first", which is exactly what nesting needs.

The procedure: read the string left to right. An opener goes on the stack. A closer must match the type of the top of the stack; if it does, pop the top; if it does not, or the stack is empty, the string is invalid. At the end the stack must be empty, or some opener was never closed.

The same push-on-open, pop-on-close skeleton handles anything with nesting or undo: a file path like /a/./b/../c (push a name, pop on "..", ignore "."), a typed string with backspaces (push a letter, pop on #), and "remove adjacent duplicate letters" (push a letter unless it equals the top, in which case pop).

Why it is correct

The invariant: after reading a prefix of the string, the stack holds exactly the openers in that prefix that have not yet been closed, in the order they were opened, most recent on top. Pushing an opener keeps it true. For a closer, the bracket it must close is the innermost unclosed one, which is the top; a match pops it, keeping the invariant, and a mismatch means the string cannot be balanced, because no later closer can fix an inner bracket that was closed by the wrong type. A closer with an empty stack has nothing to close. At the end, an empty stack means every opener was closed, and a non-empty one names an opener that was not.

Why it is fast

Each character causes at most one push or one pop, each O(1). So the whole scan is O(n) time, and the stack holds at most n items, O(n) space. A nested-loop approach that searches for each opener's partner would be O(n²); the stack avoids searching because the partner is always on top at the moment the closer arrives.

How to recognise it in an interview

Cues: "balanced", "valid parentheses", "matching tags", "nested", "simplify path", "backspace", "remove adjacent", "most recent". Whenever the problem has an undo or a "close the latest open thing" flavour, reach for a stack. Say: "Openers push, closers must match and pop the top, and the stack must be empty at the end."

Valid Parentheses is the example. Simplify Path pushes directory names and pops on "..". Backspace String Compare builds each string with a stack and compares the results, or walks both from the end skipping the right number of characters.

02The idea in one line

Push openers; a closer must match the top, then pop.

Reach for it when: Brackets, tag validation, path simplification, backspace strings.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Valid Parentheses on '{[()]}('. These are its captions in order, so you can follow without the video or check a step you missed.

1. Push every opener; a closer must match the top, then pop it
2. '{' opens: push it
3. '[' opens: push it
4. '(' opens: push it
5. ')' closes the top '(': match, pop
6. ']' closes the top '[': match, pop
7. '}' closes the top '{': match, pop
8. '(' opens: push it
9. End of input but '(' is still open: invalid
10. Each character is pushed or popped once: O(n)

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Stack: Nested structure via stack, Expression evaluation, Auxiliary-min stack, Collision simulation.