Core pattern

Stack: matching brackets with a stack of plates

Learn the stack pattern through one picture you won’t forget, worked on Valid Parentheses.

The example problem

Given a string made of brackets ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type, in the correct order.

Input:  "([]{})"
Output: true

Picture it

Picture a stack of plates. Each opening bracket is a plate placed on top. Each closing bracket must match the plate on top: a “]” can only remove a “[” plate. If the top plate is the wrong kind, or there is no plate at all, the string is invalid. At the end the stack must be empty, otherwise something was never closed.

The key idea

Last opened must be first closed, which is exactly what a stack (last in, first out) gives you. O(n).

Python

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

Practise stack

NeetCode 150 problems that use it

Stack ·