Valid Parentheses

The problem

Given a string containing only the characters ()[]{}, decide whether the string is valid: every opening bracket must close with the matching kind, and they must close in the right order. Empty string is valid; "(]" is not; "([)]" is not.

Pattern: stack as LIFO matcher

Bracket matching is the textbook use case for a stack. Push every opener onto the stack; on a closer, pop the top and check that it's the matching opener. The LIFO ordering is exactly what "innermost bracket closes first" means.

Reach for a stack any time the problem has nested structure that must unwind in reverse order — function call frames, HTML/XML tags, expression evaluation, the parser's recursion-descent machinery, Dyck-language recognition. All the same shape.

Optimal: one pass with a stack

A dictionary maps each closer to its opener. Single pass over the string. Three failure modes to catch: stack is empty on a closer (closer with no opener), top doesn't match (mismatched kinds), and stack non-empty at the end (unclosed opener).

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

Trace

A valid case:

s = "({[]})"

ch = '('   open   stack = ['(']
ch = '{'   open   stack = ['(', '{']
ch = '['   open   stack = ['(', '{', '[']
ch = ']'   close  pop '['  → matches pairs[']'] = '['   ✓   stack = ['(', '{']
ch = '}'   close  pop '{'  → matches pairs['}'] = '{'   ✓   stack = ['(']
ch = ')'   close  pop '('  → matches pairs[')'] = '('   ✓   stack = []

End of string, stack is empty → return True

And a failing case where the kinds don't nest correctly:

s = "([)]"

ch = '('   open   stack = ['(']
ch = '['   open   stack = ['(', '[']
ch = ')'   close  pop '[' → but pairs[')'] = '('   ✗   return False

Complexity

• Time: O(n) — one pass, constant work per character.
• Space: O(n) in the worst case (a string of all openers pushes everything onto the stack).

Variations worth knowing

• Minimum removals to make valid: instead of yes/no, count the minimum number of characters to delete. Use the same stack pattern but count unmatched openers (left at the end) plus unmatched closers (caught mid-pass).
• Longest valid parentheses substring: stack stores indices rather than characters; popping reveals the length of the matched span ending at the current position.
• Generate all valid parentheses of length 2n: different problem entirely — backtracking with counts of open and close used so far.

A use case: Lisp

Now, where would we actually use this valid-parenthesis tool in production? The programming language Lisp is a great use case, because a Lisp program is made of nested parentheses: (+ 1 (* 2 3)). This makes the compiler pretty straightforward to write. Like many programs, a compiler is a combination of a few different tricks — and the front of a Lisp compiler is made of exactly two: this parenthesis-matching trick, plus some tree-building. Push on ( starts a new list, pop on ) closes it and attaches it to its parent, and the two invalid cases of the interview problem become the only two syntax errors the reader can raise:

def read(src):
    tokens = src.replace('(', ' ( ').replace(')', ' ) ').split()
    stack = [[]]
    for t in tokens:
        if t == '(':
            stack.append([])                 # push: begin a new list
        elif t == ')':
            if len(stack) == 1:
                raise SyntaxError("unexpected )")   # pop of empty stack
            done = stack.pop()               # pop: close the current list
            stack[-1].append(done)
        else:
            stack[-1].append(t)
    if len(stack) != 1:
        raise SyntaxError("unclosed (")      # stack nonempty at the end
    return stack[0]

read("(+ 1 (* 2 3))")   # -> [['+', '1', ['*', '2', '3']]]
read("(+ 1 (* 2 3)")    # SyntaxError: unclosed (
read("(+ 1) )")         # SyntaxError: unexpected )

Fifteen lines, and it is a real parser — because matched parentheses are the entirety of Lisp's surface syntax. Programs are written directly as the tree the parser would have built anyway, which is what makes Lisp macros possible and Lisp parsers trivial. And once you see a compiler built like this, it's almost like music: swap out a few notes here and there and all of a sudden you're improvising — change what happens on push and pop and the same two tricks read JSON, s-expressions, or your own little language.