Valid Parentheses: Why a Stack Is the Whole Answer

Valid parentheses is an easy question with a hard failure mode: almost everybody produces working code, and a good fraction of that code is wrong on an input nobody tried. The interesting part is not the stack. It is knowing precisely which inputs are allowed to be false.

The problem it solves

Given a string of brackets — round, square, curly — decide whether every opener is closed by the matching type, in the right order.

"()[]{}" is valid. "([{}])" is valid. "(]" is not, and neither is "([)]", which is the case that separates a real solution from a counter.

Why counting is not enough

The first instinct is to count: as many closers as openers, per type, and never more closers than openers so far.

That check passes "([)]". There is one of each opener and one of each closer, and the running counts never go negative. But the string is invalid, because the square bracket opened inside the round one and has to close inside it too.

The missing idea is order. Brackets nest, and nesting means the most recently opened one must be the first to close. That sentence is a definition of a stack, which is why the data structure is not a clever choice here — it is the only structure that stores exactly the fact the problem cares about.

The intuition

Walk the string once.

• An opener? You now owe a matching closer. Push it and carry on.
• A closer? It must settle the most recent debt. Look at the top of the stack: if it is the matching opener, pop it — that pair is resolved. If it is anything else, or if there is nothing there at all, the string is invalid and you can stop immediately.
• End of string? The stack must be empty. Anything still on it is an opener that was never closed.

Three checks, and every one of them is a way to fail. That is the part worth saying out loud in an interview, because two of them are the cases people forget.

Watch it run

The stack grows on every opener and shrinks on every matched closer. Coral is the character being read; the top of the stack is the one thing the algorithm ever looks at.

Step through a nested case and watch the stack height. It is a picture of how deep the nesting currently is — which is also why the space cost is what it is.

The code

def is_valid(text):
    partner = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)                       # a debt to settle later
        elif ch in partner:
            # Nothing open, or the wrong thing open: both are failures.
            if not stack or stack.pop() != partner[ch]:
                return False
    return not stack                               # nothing may be left over

for sample in ["()[]{}", "([{}])", "(]", "([)]", "(((", ")(", ""]:
    print(repr(sample), is_valid(sample))

# '()[]{}' True
# '([{}])' True
# '(]'     False
# '([)]'   False
# '((('    False
# ')('     False
# ''       True

The dictionary maps each closer to the opener it requires, which is the direction the lookup actually needs — you meet the closer and ask what it expects to find.

"(((" is false because of the final return not stack. ")(" is false because of the not stack guard inside the loop. Two different lines catching two different mistakes; remove either and the function is wrong while still passing the obvious tests.

The complexity

Time: O(n). One pass, and every character does at most one push and one pop. No character is examined twice.

Space: O(n). In the worst case — "(((((" — every character is an opener and the stack holds all of them. That is not a pathological input; it is just deep nesting, and it means the space is genuinely linear rather than "usually small".

Where it goes wrong

• Popping an empty stack. In Python [].pop() raises IndexError, so the not stack check has to come first. In a language with an unchecked pop, it is undefined behaviour instead of an exception.
• Comparing the wrong direction. Mapping openers to closers and then peeking at the stack means comparing a stack entry against a closer's partner's partner. It can be made to work; it is easy to get inverted under pressure.
• Checking only the count at the end. As above, "([)]" defeats it. If your solution has no stack and no recursion, it is wrong.
• Returning early on success. There is no point at which the string is known to be valid before the end. Validity is a property of the whole input.
• Ignoring other characters. If the input may contain letters, decide whether they are skipped or rejected. The code above skips them, because elif ch in partner only reacts to real closers — a deliberate choice that should be stated, not discovered.

How to say it in an interview

Start from the ordering constraint, because that is the insight the question tests:

"Brackets nest, so the most recently opened one must close first — that is last in, first out, which is a stack. I push openers; on a closer I check the top. Failure has three shapes: a closer with an empty stack, a closer whose top does not match, and a non-empty stack at the end. One pass, O(n) time, and O(n) space in the worst case where the input is all openers. The empty string is valid under this definition."

Then write it, and test it out loud on "([)]" and "". Those two strings are the whole interview.