p02 — Valid Parentheses

Source: LeetCode 20 · Easy · Topics: String, Stack Companies: Amazon (high), Google (medium), Meta (medium), Microsoft (high), Bloomberg (high), Salesforce (very high) Loop position: phone screen, sometimes paired with p80 (Basic Calculator II) at onsite

1. Quick Context

The canonical stack problem. Looks trivial; the trap is the early-return logic and the empty-stack-on-close case. Senior candidates lose points by writing 15 lines when 8 suffice, by forgetting to check the stack is non-empty at end, or by not asking whether non-bracket characters can appear.

What it tests: Disciplined use of the right data structure (stack), not loop-and-counter hacks. Anti-signal: counting opens and closes separately (“balanced count”) — that fails on "(]". If you proposed this and didn’t catch it yourself, you’ve failed the cognitive-trap check.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/valid-parentheses/

STOP. Set a 12-min timer. Solve cold. Do not read on until done or timed out.

3. Prerequisite Concepts

• LIFO semantics of a stack; why “matching last-opened” is intrinsically a stack property — phase-01 §5
• Mapping closed → open via a constant dict (O(1) lookup, more idiomatic than chained if)

4. How to Approach

Restate: “Given a string of ()[]{} characters, return true iff every opener has a matching closer of the right type, in the right nesting order.”

Clarify:

• “Can the string contain other characters?” (LC: no, only brackets — but ASK, real interviews vary.)
• “Empty string?” (LC: valid = true. Yes, common gotcha.)
• “Maximum length?” (Implies whether we care about stack overflow in recursive solutions; iterative + explicit stack avoids that anyway.)

Constraints: N up to 10⁴. O(N) expected.

Examples to build:

• "()[]{}" → true (sequential pairs)
• "([{}])" → true (full nesting)
• "(]" → false ← the counter-fail case
• "]" → false (close-first; empty-stack case)
• "((" → false (unmatched open at end; non-empty-stack-at-end case)
• "" → true (empty)

Brute force: Repeatedly scan and remove adjacent (), [], {} pairs until no change. If empty, valid. O(N²).

Pattern: “Match most recent unclosed thing” → stack. Period.

Optimal: One pass. For each char: if opener, push. If closer, pop and verify match. At end, stack must be empty.

Proof of correctness: Stack invariant — at any point, the stack contains exactly the unmatched openers in order of opening. A closer matches iff it pairs with the top (most recent opener). If a closer arrives with empty stack, it has no match → false. If non-closer remains at end → unmatched openers → false.

5. Progressive Hints

If stuck >5 min: hints.md. One at a time.

6. Deeper Insight — Why It Works

Why a stack and not a counter? A counter (opens - closes) is sufficient for a single bracket type — but it cannot detect "(]". The stack is necessary because we need to remember not just that a bracket is open, but which type. Each push commits the type; each pop verifies the type. The stack is the minimum data structure that captures both “how many open” and “which order/type.”

Why we check empty BEFORE popping: If we blindly pop an empty stack on a closer, we error out (or in some languages, get undefined behavior). The check if not stack: return False handles "]", "})", etc.

Why we check empty at END: The string "((" walks through pushing twice; loop ends; stack non-empty; without the final check, we’d return True. The end-check is the second necessary correctness step.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Count-and-compare:

if s.count('(') == s.count(')') and s.count('[') == s.count(']') and ...:
    return True

Fails on "(]" (each count is 1, returns True). This is the single most common bug junior candidates ship. If you proposed this, you missed the type-ORDER requirement.

Wrong-but-tempting #2 — Regex / replace loop:

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

Works but O(N²) and signals you reached for a hammer. Interviewer’s note: “didn’t recognize stack pattern.”

Wrong-but-tempting #3 — Forgetting end-check:

for c in s:
    if c in '([{': stack.append(c)
    elif c in ')]}':
        if not stack or pairs[c] != stack.pop(): return False
return True   # ← BUG: returns True for "((" because stack non-empty but no closer caught it

The fix is return not stack. Forgetting this is the #2 bug here.

8. Skills & Takeaways

Generalizable pattern: “Match most recent unresolved item” → stack. Applies to:

• LC 32 — Longest Valid Parentheses (stack of indices, harder cousin)
• LC 84 — Largest Rectangle in Histogram (monotonic stack — same family)
• LC 739 — Daily Temperatures (monotonic stack — same family)
• LC 71 — Simplify Path (each segment as stack frame)
• LC 394 — Decode String (stack of (count, prefix) frames)
• LC 1249 — Minimum Remove to Make Parentheses Valid (stack of indices)

When NOT to use: Single bracket type, just balance counting → counter is sufficient and uses O(1) space.

9. When to Move On

• Solved unaided in <8 min on second attempt
• Tested "(]", "]", "((", "" without prompting
• Can articulate why a counter fails for multiple bracket types
• Implemented with constant closer → opener map (not chained ifs)
• Stress test in solution.py passes
• Solved LC 1249 and recognized the same pattern with index tracking

10. Company Context

Amazon

• The framing: Often paired with “and write the matched pairs as (open_idx, close_idx)” — extends to index-tracking variant.
• Misleading example: They give "{[()]}" and let you confirm true. Then sneak in "{[(])}" — looks balanced character-counts-wise; trips candidates who didn’t catch the type-order failure.
• Extension: “Now allow <> too.” → tests whether your code generalizes (constant dict makes it 1-line; chained ifs make it 4 new branches).

Salesforce (this is THEIR favorite)

• The framing: Often appears in onsite, not phone screen — they care about the cleanliness more than the algorithm.
• What they want to hear: “I’ll use a stack and a dictionary mapping closers to openers.” That sentence alone is a green check.
• Adversarial extension: “What if [ could match ) (mixed mode)?” → tests whether your code is data-driven enough to change one line of config.

Microsoft

• The framing: Phone screen warmup, sometimes followed by p80 (Basic Calculator).
• What they want to hear: Single-pass justification, end-of-loop empty-check stated out loud.

Bloomberg

• The framing: Often as part of a JSON/parser problem — “validate this serialized message structure”.
• Extension: “Parse the bracketed expression into an AST.”

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Return the index of the first invalid character instead of true/false.”

Signal: Can you adapt without rewriting? Answer: Track current index i; when popping mismatches or empty-pop happens, return i. At end if stack non-empty, return the index of the unmatched opener at stack top (so push (char, index) tuples, not just chars). One-pass O(N), no extra time cost.

Q2: “Mixed bracket modes: also accept [) and (] as valid in this protocol.”

Signal: Data-driven code awareness. Answer: Replace {')':'(', ']':'[', '}':'{'} with {')':'([', ']':'[(', '}':'{'} and change the match check from stack.pop() == pairs[c] to stack.pop() in pairs[c]. Zero algorithm change — only the config dict moves. Demonstrates extensibility.

Q3 (Hard): “Parse and evaluate the matched expression as a Lisp-like AST.”

Signal: Stack-of-frames extension. Answer: Each frame is a list of tokens accumulating between matching opens. On open: push current frame, start new. On close: pop, append the inner frame to the outer. Same stack discipline, now each entry is a list, not a char. This is the bridge from p02 to LC 394 (Decode String) and to p80 (Basic Calculator).

Q4: “Now there are millions of strings per second — same algorithm, but optimize for throughput.”

Signal: Production thinking. Answer: Three wins. (a) Replace Python list-as-stack with a fixed-size preallocated array + integer top pointer — eliminates allocation. (b) Use a 256-entry lookup table mapping char codes to (type, is_opener) instead of dict lookup — branch-free hot loop. (c) For truly hot path, write a SIMD-friendly state machine in C — but only after profiling shows this is the bottleneck.

Q5: “How would you test it?”

Signal: Testing discipline. Answer: (1) Unit: all 6 fail modes + valid + empty. (2) Property test: brute (replace-loop) vs optimal on random bracket strings, must agree. My solution.py does this. (3) Adversarial: deeply nested input (depth = 10⁵) — confirms iterative, not stack-overflowing. (4) Fuzz: random non-bracket chars to confirm the “ask about other characters” clarification.

14. Full Solution Walkthrough

See solution.py.

• is_valid_brute: repeated replace loop. Correct but O(N²). Used as oracle.
• is_valid: stack + closer→opener dict. Three correctness branches: (i) push on open, (ii) check-then-pop on close (empty + mismatch both → False), (iii) final stack-empty check.
• stress_test: generates random bracket strings (balanced and unbalanced), asserts brute and optimal agree.

15. Beyond the Problem

Real systems this is the kernel of:

• JSON / XML / YAML parsers — every structural parser uses this exact stack discipline. Errors in production parsers (e.g., “Unexpected end of input”) are the end-empty-check firing.
• IDE bracket matching — your editor’s “matching bracket” highlight runs this algorithm on every keystroke, scoped to a window around the cursor.
• Code linters — eslint’s no-unbalanced-brackets rule is this with position tracking.
• Network protocols with framing (e.g., BSON, MessagePack) use stack-based parsers.

Principal-engineer code review comment: “We have three places in the codebase that re-implement bracket matching (JSON parser, query parser, markdown renderer). They’ve each drifted to handle their edge cases differently. Extract a generic match_pairs(input, pair_table, on_unmatched) and centralize. The bug we hit last quarter was the JSON parser missing the end-check; the markdown one had the check but the wrong error message.”