Skip to main content

2. Valid Parentheses

easyAsked at Snowflake

Determine whether a string of brackets is balanced. Snowflake uses this to test whether you can build a parser-like stack walk — the same primitive used to validate SQL parenthesization in their query parser.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake compiler-team phone screens cite this as the warm-up.
  • Blind (2025-09)— Recurring at Snowflake new-grad onsites.

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, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket of the same type.

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 string replacement

Keep replacing '()', '[]', '{}' with empty string until no change; valid iff result is empty.

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

Tradeoff: Cute but O(n^2) due to repeated string copies. Don't ship in a query parser.

2. Stack with matching map (optimal)

Walk the string. Push opens; on a close, check the top matches and pop. At the end, the stack must be empty.

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

Tradeoff: Linear, single pass. This is exactly how SQL parsers validate parenthesization of subqueries and function calls.

Snowflake-specific tips

Snowflake interviewers reward candidates who tie this to query-parser internals: the same stack pattern validates parenthesized subqueries, function calls, and CTEs. Bonus signal: discuss error reporting — where in the input the mismatch occurred — since Snowflake's SQL errors are graded on developer-friendliness.

Common mistakes

  • Forgetting the case where the stack is empty when you hit a closing bracket — pop returns undefined and you have to handle it.
  • Returning true at the end without checking that the stack is empty (e.g., '(((' would pass).
  • Using a string and slicing instead of a stack — O(n^2) due to slice copies.

Follow-up questions

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

  • Return the index where the mismatch occurs (parser-style error reporting).
  • Support other bracket types and quotes.
  • What if the input is streamed — can you validate as bytes arrive?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why a hash map instead of a switch?

Cleaner extension to more bracket types and easier to test. In a SQL parser you'd want this table-driven anyway.

Can I solve this without a stack?

Yes for the trivial '()' case with a counter, but it fails the moment you add multiple bracket types — the counter can't track which type closes which. Stack is the only generalizable answer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →