Skip to main content

20. Valid Parentheses

easyAsked at Google

Given a string of brackets, return true if every opener has a matching, correctly-nested closer. Google asks this to confirm you can model push/pop state with a stack and articulate why the LIFO property is what makes the problem cleanly solvable.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Common Google phone-screen warm-up before a follow-up that requires the underlying stack.
  • Reddit r/cscareerquestions (2025-10)— Multiple L3 reports cite this as a 10-minute easy with a basic-calculator follow-up.

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

Approaches

1. Repeated string replacement

Repeatedly remove '()', '[]', '{}' from the string until no more matches. Valid iff the string is empty at the end.

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

Tradeoff: Correct but quadratic in the number of replacements and unnecessarily clever. Mention it to show you noticed the structure, then move to the stack.

2. Stack of openers (optimal)

Push opener onto a stack; on a closer, the top of stack must be the matching opener, else invalid. Empty stack at the end means valid.

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

Tradeoff: Linear, single pass, conceptually crisp. The stack is exactly the right data structure because brackets are inherently LIFO.

Google-specific tips

Google interviewers want you to name why the stack works — the LIFO property mirrors the nesting structure. If you skip that articulation and just code, you'll be marked down on 'communication' even when the code is correct. Expect a follow-up on Basic Calculator II that requires the same stack pattern.

Common mistakes

  • Forgetting to check that the stack is empty at the end — '(' alone returns true if you only check matches.
  • Trying to count openers/closers without tracking type — that fails on '([)]'.

Follow-up questions

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

  • How would you handle a string with non-bracket characters mixed in?
  • What if you needed to return the index of the first invalid bracket?
  • Extend to Basic Calculator II (handles + - * / with parentheses).

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 solve this without a stack?

Not in a single pass for the multi-bracket variant. You can with counters for the single-type '()' variant, but the moment you have '[' and '{' the LIFO requirement forces a stack.

What's the most-common bug in interviews?

Forgetting the final emptiness check. Many candidates return true the moment they get through the loop without errors, which fails on '('.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →