Problem 12 · Stacks

Valid Parentheses

EasyClassic DSA & systems

01Problem

Given a string of brackets ()[]{}, determine whether every opener is closed by the matching type in the correct order.

02Key insight

Nesting is LIFO, so a stack of expected closers models it directly; fail fast on mismatch and require an empty stack at the end.

03Solution

solution.pypython10 lines

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert is_valid("()[]{}")
assert is_valid("{[()]}")
assert not is_valid("(]")
assert not is_valid("((")

04Staff-level follow-up

Only one bracket type and huge input? Replace the stack with a depth counter (O(1) space); for parallel validation each chunk emits (unmatched_closes, unmatched_opens), which combine associatively.