Valid Parentheses

Given a string containing only ()[]{}, decide whether it's valid: every opener is closed by the matching closer, in the right order. (LC 20)

The recipe

Say before you type: "Nesting means the most recently opened bracket must close first — that's a stack."

1. Build a lookup from each closer to its opener: ')' → '('.
2. Walk the string. Openers get pushed.
3. On a closer, pop the stack and demand it equals the expected opener. A mismatch — or an empty stack, which pop() reports as undefined — means invalid.
4. At the end, the stack must be empty. Leftovers are unclosed openers.

The code

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const stack: string[] = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false; // wrong match OR empty
    }
  }
  return stack.length === 0; // leftovers = unclosed
}

Why this shape

The rule of valid nesting is last-opened, first-closed — which is exactly LIFO, which is exactly a stack. Keying the lookup by the closer keeps the loop to a single clean branch: openers push, closers pop-and-compare.

The neat trick in the code: stack.pop() on an empty array returns undefined, which never equals an opener — so the "closer with nothing open" case ("]") fails through the same comparison as a wrong match. One line handles two failure modes.

Complexity

	Cost	Because
Time	O(n)	Each character is pushed and popped at most once
Space	O(n)	Worst case is all openers: "((((("

Traps

• Forgetting the final emptiness check. "((" sails through the loop and is invalid. The return line is stack.length === 0, not true.
• Mapping opener → closer instead of closer → opener, which forces an awkward peek-then-pop dance.
• Solving it once by reference and assuming it's owned. This one feels too easy to rep — verify you can produce it cold, because it appears constantly as a warm-up and fumbling a warm-up sets the tone.

The pattern this trains

"Matching / nesting / most recent" in a prompt means stack. The same muscle carries Min Stack (LC 155) and Implement Queue Using Stacks (LC 232), and it's the mental model under every parser you'll ever discuss in a design round.