LeetCode #20 - Valid Parentheses, and the stack instinct

Problem (LeetCode #20, Easy): Given a string containing only (, ), {, }, [ and ], decide whether the brackets are valid. Every opener must be closed by the same type of bracket, and brackets must close in the correct order.

The problem in plain English

This is not just asking "do we have the same number of opening and closing brackets?"

This is valid:

()[]{}

This is not:

([)]

Both have matching counts, but the second one closes [ before closing (. The order matters.

The naive instinct

One tempting idea is to count each type:

def isValid(s):
    return (
        s.count("(") == s.count(")") and
        s.count("[") == s.count("]") and
        s.count("{") == s.count("}")
    )

That fails because counts do not remember order. For ([)], the counts look perfect, but the nesting is broken.

Another idea is repeatedly removing valid pairs:

def isValid(s):
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

This works for many cases, and it is a nice mental model: valid adjacent pairs disappear until nothing remains. But it keeps scanning and rebuilding strings, so it can drift toward O(n^2) time.

The reframe: last opened, first closed

When we see an opening bracket, we cannot validate it immediately. We have to wait for a future closing bracket.

But when a closing bracket arrives, it must close the most recent unmatched opener.

That is exactly a stack:

• Push every opener.
• When a closer appears, pop the most recent opener.
• If the popped opener does not match, the string is invalid.
• At the end, the stack must be empty.

The phrase to remember is last in, first out.

The accepted solution

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []
 
        for ch in s:
            if ch in pairs:
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)
 
        return not stack

The map is written from closing bracket to opening bracket because closing brackets are the moment where we can verify something.

When ch is ), the top of the stack must be (. If the stack is empty, there is nothing to close. If the top is something else, the nesting is wrong.

Walkthrough

For s = "{[]}":

The stack ends empty, so the string is valid.

For s = "([)]":

The first wrong closer proves the whole string is invalid. We can return immediately.

Other possibilities

The repeated-replacement solution is readable, but less efficient because strings are immutable in Python. Every replacement builds a new string.

You could also push the expected closer instead of the opener:

def isValid(s):
    stack = []
    expected = {"(": ")", "[": "]", "{": "}"}
 
    for ch in s:
        if ch in expected:
            stack.append(expected[ch])
        elif not stack or stack.pop() != ch:
            return False
 
    return not stack

This version makes the comparison even more direct: "the next closer I accept is on top of the stack." Both versions are fine.

Complexity

The stack solution is O(n) time because each character is pushed or popped at most once. It is O(n) space in the worst case, for an input like "(((((" where every character waits on the stack.

The pattern to remember

When a problem cares about the most recent unfinished thing, think stack.

Valid Parentheses is the cleanest version of that idea, but the same pattern shows up in browser history, undo operations, nested expressions, monotonic stacks, and "next greater element" problems.