#20 Valid Parentheses

EasyStack~12 min

You're handed a string made up only of the six bracket characters: (, ), {, }, [, ]. Decide whether the string is well-formed. That is, every opening bracket is eventually closed by a bracket of the same kind, and brackets close in the correct order (the most recently opened one must close first).

Return true if the string is valid, false otherwise.

Examples

Inputs = "()[]{}"

Outputtrue

Three pairs, each opened and closed in order.

Inputs = "([)]"

Outputfalse

The `[` is opened after the `(`, so it must close first, but `)` arrives before `]`.

Inputs = "(("

Outputfalse

Two brackets open and nothing ever closes them.

Constraints

1 ≤ s.length ≤ 10⁴
s consists only of the characters '(', ')', '{', '}', '[', ']'

Hints

Intuition

Nesting is a LIFO phenomenon. When you read ([{, the { opened last, so it must close first. The [ is frozen until the { is resolved, and the ( is frozen until both are. "Most recently opened, first closed" is the literal definition of a stack, so the algorithm writes itself:

Opener? Push it. It's now the most-recent obligation.
Closer? It must discharge the top of the stack. Pop and compare kinds. Any mismatch (or an empty stack) means the string is broken, and you can stop immediately.

At the end, an empty stack means every obligation was discharged. A non-empty stack means something opened and never closed, a failure people forget to check because the loop finished "without errors."

This exact shape (push obligations, discharge them in reverse order) is how compilers match braces, how editors highlight the matching paren, and how you'll solve half the stack problems in this track.

Approaches

1. Repeated pair deletion

O(n²) time · O(n) space

Keep deleting any adjacent matched pair ((), [], or {}), from the string until no deletions apply. A valid string collapses to empty; an invalid one gets stuck with leftovers. It's correct and a decent way to convince yourself what validity means, but each pass is O(n) and you may need O(n) passes (think ((((...)))), which collapses one layer at a time from the middle). Mention it, then beat it.

2. Single pass with a stack

O(n) time · O(n) space

One walk over the string, one stack:

Opening bracket → push it.
Closing bracket → if the stack is empty, fail (nothing to close). Otherwise pop; if the popped opener doesn't pair with this closer, fail.
After the loop, succeed only if the stack is empty.

A small quality-of-life trick: map each closer to its expected opener () → (, etc.). Then the loop body is "if it's a closer, pop and compare to the map; else push", no three-way branching on bracket kinds.

Worst-case space is O(n) when the whole string is openers, e.g. (((((.

Solution

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}  # closer -> required opener
    stack = []
    for ch in s:
        if ch in pairs:
            # A closer must discharge the most recent opener. Popping from an
            # empty stack means a closer with nothing to close, fail fast.
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack  # leftovers = openers that never closed

Common pitfalls

Forgetting the final empty-stack check, `"(("` sails through the loop with zero mismatches and is still invalid.
Popping from an empty stack on input like `")("`, in Python that's an exception, not a `false`. Guard it (or exploit JS's `undefined` from `pop()`).
Counting brackets instead of stacking them. `"([)]"` has balanced *counts* of every kind and is still invalid, order matters, and counters can't see order.

Going further

Min Remove to Make Valid Parentheses: instead of a yes/no, delete the fewest characters to make it valid, the stack now records *indices* to remove.
Longest Valid Parentheses (Hard): same matching idea, but you track how far back the valid stretch extends.
Generate Parentheses: flip the problem from checking to constructing. The 'never close more than you've opened' invariant becomes the backtracking rule.