HARD Lab · Strings · 14

20. Valid Parentheses

A bracket string is valid when every opener is closed by the correct closer in the right order. A stack makes this a single linear scan: push openers, pop and verify on every closer.

● EasyStackTypeScript

PROBLEM What we're solving

Given a string s containing only ( ) [ ] { }, return true if every opening bracket is closed by the same type in the correct order, false otherwise. "([{}])" → true. "([)]" → false (crossed nesting). "{[]}" → true.

KEY IDEA Last-in, first-out — a stack handles nesting naturally

Insight → the most recently opened bracket must always be closed first. That is exactly the LIFO property of a stack. Push every opener; when you see a closer, the stack top must be its matching opener. If it isn't — or the stack is empty — the string is invalid. If the string ends with a non-empty stack, unmatched openers remain.

RECIPE Push on open, pop-and-match on close

  • 1 · Initialise. Create an empty stack and a closer→opener lookup: ) → (, ] → [, } → {.
  • 2 · Scan each character.If it is an opening bracket, push it. If it is a closing bracket, pop the top — if the popped value doesn't equal the expected opener (or the stack was empty), return false.
  • 3 · Final check. After the loop, return stack.length === 0. A non-empty stack means unmatched openers were never closed.
Classic confusion → forgetting the final empty-stack check. The string "(" never triggers a mismatch during the loop — only the trailing length check catches the unclosed opener.

COST Complexity

Naïve repeated-replace
O(n²)
Keep removing "()" pairs until stable — O(n) passes of O(n) each.
Stack
O(n)
One pass; stack holds at most n/2 openers → O(n) space.

Stack space is O(n) in the worst case (e.g. "(((((") but never more than that.

Pattern transfer → the same push/pop pattern powers Daily Temperatures (monotonic stack), Min Stack (augmented stack), Largest Rectangle in Histogram, and almost every "matching/nesting" problem.

RUN IT Push openers, pop & match closers

step 0 / 7
STARTScanning "([{}])" — push opening brackets, match closing brackets against the stack.
(0[1{2}3]4)5
State
(empty)
stack
current charpushed onto stackmatched & poppedmismatch / leftover
slowfast

TYPESCRIPT The solution, annotated

isValid.ts
function isValid(s: string): boolean {
  const stack: string[] = [];
  const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' };

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);                // push opener
    } else {
      if (stack.pop() !== match[ch]) // pop & verify closer
        return false;
    }
  }
  return stack.length === 0;         // unmatched openers?
}

Reading it block by block

Lines 2–3 — setup. stack holds unmatched openers; match is a O(1) lookup from closer to its expected opener.
Lines 5–8 — push openers. For every opening bracket we simply push it. The stack naturally preserves nesting order via LIFO.
Lines 9–11 — pop and verify closers. stack.pop() removes the top and returns it (or undefinedif empty). If it doesn't equal the required opener, the bracket is unmatched or crossed — return false immediately.
Line 13 — trailing check. If any opener was never closed the stack is non-empty. Only an empty stack means every bracket was balanced.
Complexity → O(n) time (single pass) and O(n) space for the stack — at most ⌊n/2⌋ openers can be pending simultaneously.

INTERVIEWFollow-ups they'll ask

  • "What if the string is empty?" An empty string has no brackets to check, so the stack stays empty and we return true — which is correct per the problem definition.
  • "Can you do it without a stack?"Only for a single bracket type (just track a counter). With mixed types the LIFO structure is fundamental; a counter alone can't distinguish "([)]" from valid input.
  • "What if new bracket types are added?" Just extend the match map and the opener check. The algorithm is O(1) per bracket type.
  • "Minimum add to make valid?" (LC 921) Track unmatched opens and closes separately during the same stack scan.
  • "Longest valid parentheses?" (LC 32) Push indices onto the stack instead of characters to track span lengths.

MNEMONIC The one-liner

"Openers in, closers check the door — empty stack at the end means all square."

TRIGGERS When you see ___ → reach for ___

matching/nesting order mattersstack (LIFO)
closing bracket must pair with most-recent openerpush opener, pop on close
detect unclosed openersstack.length === 0 at end
"balanced brackets" variantsame push/pop skeleton ± augmentation

SKELETON The reusable shape

skeleton.ts
function isValid(s: string): boolean {
  const stack: string[] = [];
  const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' };

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== match[ch]) return false;
    }
  }
  return stack.length === 0;
}

FLASHCARDS Tap to flip

Why does a stack naturally solve bracket matching?
Brackets nest — the last opened must be closed first. That is exactly LIFO.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What does "([)]" return?
QUESTION 02
What is the time complexity of the stack solution?
QUESTION 03
The string "((" — which check catches the error?
QUESTION 04
Why can a simple counter replace the stack for single-type brackets but not mixed types?
QUESTION 05
What is the worst-case space usage of the stack?
QUESTION 06
stack.pop() on an empty stack in JavaScript returns undefined. How does the solution handle this?
QUESTION 07
Which of these is not a valid use of the bracket-stack pattern?