Skip to main content

2. Valid Parentheses

easyAsked at Vercel

Given a string of brackets, decide if it's balanced. Vercel uses this to test whether you recognize the stack pattern instantly — it's the same shape as their route-segment matching in nested layout trees.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2026-Q1)— Frequent warm-up at Vercel for platform engineers parsing Next.js route segments.
  • Blind (2025-11)— Reported in onsite recap; followed by a 'now extend to brackets in template strings' twist.

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
true

Example 3

Input
s = "(]"
Output
false

Explanation: Mismatched bracket types.

Approaches

1. Repeated substring removal

Repeatedly remove '()', '{}', '[]' substrings until no change; valid iff result is empty.

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

Tradeoff: Cute but O(n^2) due to repeated string allocation. Mention as the regex-y anti-pattern.

2. Stack with match map (optimal)

Push opens onto a stack. On a close, pop and verify the popped open matches. Valid iff stack is empty at the end.

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

Tradeoff: Single pass, O(n). The match-map lookup keeps the close-bracket branch tight and readable.

Vercel-specific tips

Vercel grades whether you reach for the stack pattern without prompting and whether you handle the 'extra closing bracket' case (pop on empty stack returns undefined) without a separate guard. Bonus signal: connecting this to how their build system validates the bracket structure of nested route groups in App Router.

Common mistakes

  • Forgetting to check that the stack is empty at the end — '(((' would pass without that check.
  • Using `stack.pop()` without handling the empty-stack case explicitly — in JS, undefined !== '(' so it's safe, but only if you reason about it.
  • Building a string-replace loop instead of the stack — works but quadratic.

Follow-up questions

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

  • Allow wildcard '*' that matches '(' or ')' or empty (LC 678).
  • Find the longest valid substring (LC 32, hard).
  • Generate all valid bracket combinations of length 2n (LC 22).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What if the input has non-bracket characters?

The constraint says only brackets, but if relaxed, ignore non-brackets — don't push, don't pop. Confirm with the interviewer; Vercel likes when you ask the input-shape question up front.

Why is the stack the right data structure?

Brackets are nested LIFO by nature: the most recently opened bracket must close before any earlier one can. That's the literal definition of a stack.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →