p02 Valid Parentheses — Progressive Hints

One hint, 5-min timer, retry. Repeat.

Hint 1 — Pattern family

The string is processed left to right. At any point, you have unresolved openers. The closer you read needs to match the most recent unresolved opener — not just any opener. What property does “most recent” have?

Hint 2 — Data structure

LIFO — last-in-first-out. There is exactly one data structure for this.

Hint 3 — Key insight

Push every opener onto a stack. When you see a closer, the top of the stack must be the matching opener — pop and compare types. If it isn’t, or the stack is empty, the string is invalid. At the end of the string, the stack must be empty.

Hint 4 — Pseudocode

stack = []
pairs = { ')':'(', ']':'[', '}':'{' }
for c in s:
    if c is an opener:
        push c
    else if c is a closer:
        if stack is empty: return false
        if pop() != pairs[c]: return false
return stack is empty

There are exactly three failure branches. Make sure you have all three.

Hint 5 — Full algorithm with the three correctness branches

Three places the answer becomes False — miss any one and you have a bug:

1. Mid-loop, empty-stack on close: A closer arrived with no unmatched opener to match. Example: "]".
2. Mid-loop, top-mismatch on close: The top of the stack is an opener of the wrong type. Example: "(]" — top is (, closer is ], mismatch.
3. End of loop, non-empty stack: Openers remain unmatched. Example: "((".

Use a constant dict {')':'(', ']':'[', '}':'{'} so the match check is one line, not six. This is what the interviewer flags as “data-driven code” — it generalizes when they add <> as a follow-up.

Time O(N), Space O(N) worst case (all openers, no closers).