Valid Parentheses

Interview Prep

Warm-upStackstackstrings

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.