Know this before you start: “Push / pop for matching pairs”

Stacks for matching pairs

A stack takes and gives back items last-in, first-out. Push each opener; a closer must match the opener on top.

The idea

A stack is a pile: push puts an item on top, pop takes the top one off. Both are O(1). The last thing pushed is the first thing popped.

Brackets close in the reverse order they open, which is exactly last-in, first-out. Push every '(' '[' '{'; when a closer arrives, the top of the stack must be its partner.

In Python a list is a stack: append to push, pop() to pop, stack[-1] to peek.

See it step by step

Is “{[()]}” valid?

{ [ ( → push all three: stack = { [ (
) matches top ( → pop. ] matches [ → pop. } matches { → pop.
Stack is empty at the end → valid.

In code (Python)

def valid_brackets(s):
    partner = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in partner:
            if not stack or stack.pop() != partner[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(valid_brackets("{[()]}"))   # True
print(valid_brackets("([)]"))     # False

O(n) time, O(n) space.

When you'll use it

Brackets, HTML tags, undo, removing adjacent pairs, evaluating expressions.

Common mistakes

Popping from an empty stack.
Forgetting the stack must be empty at the end.