Valid Parentheses (LeetCode 20)

The problem

You get a string made only of the characters ( ) [ ] { }. Return True if the brackets are balanced: every opener has a closer of the same type, and they close in the correct order (the most recently opened bracket closes first). Otherwise return False.

Input:  "([]{})"
Output: True

Input:  "([)]"
Output: False

In the first string each inner pair closes before the outer ( does. In the second, ) arrives while [ is still open, so the nesting is crossed.

How to think about it

Start with brute force. Repeatedly delete any adjacent pair (), [] or {} until nothing changes. If the string ends up empty, it was valid. This works, but each pass is O(n) and you can need up to n/2 passes, so it is O(n²).

Counting is not enough. A tempting shortcut is to count openers and closers of each type. That accepts "([)]", where the counts are fine but the order is wrong. The real rule is about order: a closer must match the most recent unmatched opener.

The key insight: “most recent unmatched” is exactly the top of a stack. Push each opener. When a closer arrives, the only opener it may legally close is the one on top. Pop it and compare. If the stack is empty, or the top is the wrong type, the string is invalid. At the end, any openers left on the stack were never closed.

Which pattern is this? A plain stack used for nested structure. The tell is “things that open and close and must nest”, which also covers HTML tags, function calls and expression parsing. It sits in the monotonic-stack lesson because it builds the push/pop reflex every stack problem needs.

Approach

1. Keep a pairs map from each closer to its opener, and an empty stack st.
2. For each character c:
   • If c is a closer, the stack must be non-empty and its popped top must equal pairs[c]. If not, return False.
   • Otherwise c is an opener, so push it.
3. After the loop, return True only if the stack is empty.

Solution

def is_valid_paren(s):
    st = []; pairs = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in pairs:                                  # c is a closer
            if not st or st.pop() != pairs[c]:          # nothing open, or wrong type
                return False
        else:
            st.append(c)                                # opener: remember it
    return not st                                       # leftovers were never closed
# is_valid_paren("()[]{}") -> True
# is_valid_paren("(]")     -> False

Dry run

On "([]{})":

The stack is empty at the end, so the answer is True. On "([)]", the third character ) pops [, which does not match, so the function returns False immediately.

Complexity

• Time: O(n). Each character is looked at once, and each push or pop is O(1).
• Space: O(n). In the worst case (all openers, like "((((") every character sits on the stack.

Edge cases and pitfalls

• Empty string is valid: the loop never runs and the stack is empty.
• A closer first, like ")(": the not st check stops you popping an empty list, which would raise an error.
• Leftover openers, like "((": you must check the stack is empty at the end, not just that nothing failed during the loop.
• Odd length strings can never be valid. Returning False early for len(s) % 2 is a small, safe speed-up.
• Counting instead of stacking passes "([)]" wrongly. Order matters, not just totals.

Related problems

• Valid Parenthesis String (LeetCode 678): adds a wildcard *, so you track a range of open counts instead of a stack.
• Generate Parentheses (LeetCode 22): build every balanced string using the same “never close more than you opened” rule.
• Evaluate Reverse Polish Notation (LeetCode 150): another stack that processes an expression one token at a time.