CodingwithDom
Subscribe

Valid Parentheses: why a stack is the answer

Interview Prep 2 min read
Short answer

Push opening brackets onto a stack; on a closing bracket, pop and check it matches. The string is valid if every check passes and the stack ends empty.

python
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False

    return not stack

O(n) time, O(n) space.

#Three failure modes, all covered

Wrong type: ([)] — popping ( when [ was expected.

Closing with nothing open: ) — not stack catches it before the pop.

Unclosed at the end: ((( — the final not stack catches it.

That last one is the check people forget. Returning True at the end without it passes (((.

#Why a stack

Nesting is last-in-first-out by definition: the most recently opened bracket must be the next one closed. That is exactly a stack's contract, which is why it fits so cleanly.

The same shape solves:

  • Matching HTML or XML tags
  • Evaluating expressions and converting infix to postfix
  • Undo/redo
  • Depth-first traversal
  • Balanced-quote checking in a parser

#Recognising it in an interview

If the problem involves nesting, matching pairs, or "most recent unmatched thing", reach for a stack before writing anything. Saying "this is a stack problem because nesting is LIFO" is most of the answer.

#The counter trick does not generalise

For one bracket type you can just count up and down. With three types you need to know which bracket is open, and a counter cannot tell you. Interviewers often start with one type and add the rest to see whether you notice.

Related answers