Valid Parentheses

Valid Parentheses is the classic introduction to the stack — the data structure built for "match the most recent thing first." Once you see how a stack solves it, you will spot the same shape in dozens of other problems.

The idea

When you see a closing bracket, which opener should it match? Always the most recent one still open. That "most recent, not yet closed" rule is exactly what a stack gives you: last in, first out.

So we walk the string once:

• An opening bracket? Push it onto the stack — it is now "waiting to be closed."
• A closing bracket? Look at the top of the stack. If it is the matching opener, pop it (that pair is done). If the stack is empty, or the top is the wrong type, the string is invalid.

At the very end, the stack must be empty. If anything is left over, some opener was never closed.

A closing bracket with the wrong opener on top (or no opener at all) fails immediately. That is what catches "([)]": when ) arrives, the top of the stack is [, not (, so we return False.

Walk through it

Step through the animation on "([])". The pointer i scans left to right. The strip on the right is the stack. We push (, then [. When ] arrives, the top is [ — match, so we pop. When ) arrives, the top is ( — match, so we pop. The stack ends empty, so the answer is True.

Pseudocode

make an empty stack
for each character ch in s:
    if ch is an opening bracket:
        push ch onto the stack
    else:                               # ch is a closing bracket
        if stack is empty: return False        # nothing to close
        top = pop the stack
        if top is not the match for ch: return False
return (stack is empty)                 # leftovers mean an opener was never closed

The whole algorithm is one pass, and every decision looks only at the top of the stack.

The Python solution

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

• pairs maps each closing bracket to the opener it needs. Anything not in pairs is therefore an opener.
• if ch not in pairs: — ch is an opening bracket, so we append (push) it.
• Line 7 handles closers and does two checks at once: not stack means there is no opener to match (fail), and stack.pop() != pairs[ch] pops the top and fails if it is the wrong type.
• return not stack — True only if the stack ended empty. Any leftover opener means it was never closed.

Complexity

Each character is pushed and popped at most once, so the time is O(n). The stack can hold up to n openers (think "((((("), so the extra space is O(n).

When this pattern shows up

Practice