Skip to main content

3. Valid Parentheses

easyAsked at Notion

Given a string of brackets, return whether it's properly nested and matched. Notion asks this because their block editor literally validates nested markdown delimiters this way.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion frontend phone screens use this as a stack warmup.
  • Blind (2025-09)— Reported alongside follow-ups about parsing markdown delimiters.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and open brackets are closed in the correct order.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'

Examples

Example 1

Input
s = "()[]{}"
Output
true

Example 2

Input
s = "(]"
Output
false

Explanation: Wrong bracket type closes the open paren.

Example 3

Input
s = "([)]"
Output
false

Explanation: Brackets must close in LIFO order.

Approaches

1. Repeated removal of matched pairs

Repeatedly remove '()' '[]' '{}' substrings until none remain.

Time
O(n^2)
Space
O(n)
function isValid(s) {
  let prev;
  do { prev = s; s = s.replace(/\(\)|\[\]|\{\}/g, ''); } while (s !== prev);
  return s.length === 0;
}

Tradeoff: Clever but O(n^2). Mention only as an anti-pattern.

2. Stack (optimal)

Push opens onto a stack; on a close, pop and verify it matches. The stack must be empty at the end.

Time
O(n)
Space
O(n)
function isValid(s) {
  const match = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch in match) {
      if (stack.pop() !== match[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

Tradeoff: Linear time, LIFO captures nesting exactly. Don't forget the final empty-stack check.

Notion-specific tips

Notion grades this on whether you say 'stack' within 10 seconds and whether you remember the final stack-is-empty check (50% of candidates forget this). Bonus: extend the discussion to how Notion's markdown parser validates nested bold/italic/code delimiters with the same pattern.

Common mistakes

  • Forgetting that stack.pop() on empty returns undefined — the match check still needs to fail.
  • Forgetting the final stack.length === 0 check — '(((' would pass without it.
  • Trying to use a counter instead of a stack — works for one bracket type but not three.

Follow-up questions

An interviewer at Notion may pivot to one of these next:

  • Generalize to arbitrary opener/closer pairs from a config.
  • Return the longest valid prefix, not just true/false.
  • Longest Valid Parentheses (LC 32) — much harder.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Can I use a single counter instead?

Only if there's one bracket type. With three types you need a stack to know which closer matches the most recent opener.

Why is the empty-stack check needed?

An input of just opens like '(((' would return true without it. The stack tracks 'unclosed' state; non-empty means unmatched.

Practice these live with InterviewChamp.AI

Drill Valid Parentheses and other Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →