Skip to main content

2. Valid Parentheses

easyAsked at Snap

Given a string containing brackets, determine if every opening bracket is closed by the matching type in the correct order. Snap uses this to verify you reach for a stack on linear matching problems.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • Glassdoor (2026-Q1)— Reported as the second screen at Snap right after Two Sum.
  • Reddit r/cscareerquestions (2025)— Common pre-screen at Snap; expected to be solved in under 10 minutes.

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 replacements happen; check if final string 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 === '';
}

Tradeoff: Cute but O(n^2) due to string copies; the stack is strictly better.

2. Stack with bracket map (optimal)

Push openings onto a stack. On a closing bracket, pop and verify the popped opener matches the expected pair. String is valid iff the stack ends empty.

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

Tradeoff: Single pass, O(n) time. The 'stack ends empty' check catches unclosed openers — easy to miss.

Snap-specific tips

At Snap, name the stack pattern out loud before coding ('LIFO matching is a stack signal'). Bonus signal: extend the explanation to how a similar approach handles HTML tag matching in their preview rendering pipeline. Snap engineers love when candidates connect the abstract pattern to a concrete product use-case.

Common mistakes

  • Forgetting the final stack.length === 0 check — '((' returns true otherwise.
  • Trying to pop from an empty stack — guard against ')' as the first character.
  • Using a Set instead of a stack — order matters here.

Follow-up questions

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

  • Return the minimum number of insertions to balance the string.
  • Generalize to N bracket types defined by a map.
  • Find the longest valid substring (LC 32).

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 Map of close-to-open instead of open-to-close?

Because the trigger for the lookup is the closing character — you have it in hand and want to ask 'what should be on top?' Mapping close to open lets you do that in one direct lookup.

Is the empty-stack check sufficient?

Yes. Every push must be matched by a pop of the correct pair, and any leftover opener makes the final stack non-empty. Both invariants are checked.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →