Frontend Beauty
ESC

Type to search the knowledge base.

Valid Parentheses

Check if brackets are valid with a stack — matching pairs, edge cases, and the interview follow-ups.

beginner4 min read
  • dsa
  • stack
  • strings
  • Google
  • Amazon
  • Meta
  • Bloomberg

The problem

Given a string containing only ()[]{}, decide if it is valid:

  1. Open brackets must be closed by the same type.
  2. Open brackets must be closed in the correct order.
  3. Every close has a matching open.
Input:  "()[]{}"  → true
Input:  "([)]"    → false
Input:  "{[]}"    → true
Input:  "("       → false
Input:  ""        → true  (usually; confirm with interviewer)

This is the canonical stack warm-up. Frontend interviews use it because stacks also model undo, routing history, and nested UI.

Brute force (don’t ship it)

Repeatedly remove "()", "[]", "{}" substrings until nothing changes. Correct for small n, O(n²) worst case and ugly. Mention it only to discard it.

The move: stack of opens

Scan left → right:

  • Open ( [ { → push
  • Close → stack must be non-empty and top must be the matching open; then pop
  • End of string → stack must be empty
function isValid(s: string): boolean {
  const stack: string[] = [];
  const pair: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
      continue;
    }

    // closing bracket
    if (stack.length === 0) return false;
    if (stack.pop() !== pair[ch]) return false;
  }

  return stack.length === 0;
}
Time O(n)
Space O(n) worst case (all opens)

Walk "({[]})"

ch stack after
( (
{ ( {
[ ( { [
] ( {
} (
) empty → valid

Walk "([)]"

( → [ → ) wants ( but top is [ → false.

Edge cases to say out loud

  • Empty string → valid under classic LC
  • Starts with close → false immediately
  • Only opens → false at end
  • Odd length → still handle cleanly (algorithm doesn’t need a special case)
  • “What about other characters?” — clarify; either ignore or invalid

Early exit: if s.length % 2 === 1 return false — micro-optimization, optional.

Variants interviewers stack on top

  1. Minimum removals to make valid (LC 1249) — stack of indices
  2. Longest valid parentheses substring (LC 32) — stack or DP
  3. Score of parentheses (LC 856) — nested scoring
  4. Generate parentheses (LC 22) — backtracking, different problem
  5. HTML-ish tags — same idea, richer tokens

Frontend-flavored: validate nested JSX-like structures or matching markdown fences — still a stack.

Common bugs

  • Comparing the close char to the open without a map () vs ()
  • Forgetting the final empty check
  • Using a counter only (works for one type of bracket, not three interleaved types)
// counters are NOT enough for "([)]"
function isValidOnlyParens(s: string): boolean {
  let balance = 0;
  for (const ch of s) {
    if (ch === '(') balance++;
    else if (ch === ')') {
      balance--;
      if (balance < 0) return false;
    }
  }
  return balance === 0;
}
// "([)]" would need a real stack — types interleave

Implementation notes for JS interviews

  • Prefer an array as a stack (push / pop) — no need for a custom class.
  • A Map or plain object for close→open keeps the loop branch-free and readable.
  • If the problem allows only one bracket type, say that a counter is enough and when it stops being enough.
  • Avoid recursion here; interviewers want the iterative stack unless they ask for a parser.

Interview delivery

  1. Restate + ask about empty string and charset.
  2. Propose stack + map.
  3. Code cleanly.
  4. Trace one true and one false example.
  5. State O(n)/O(n).

Don’t over-engineer. Valid Parentheses is a handshake — then they move to harder stack/string work.

Further reading