Skip to main content

2. Valid Parentheses

easyAsked at Square

Given a string of brackets, decide whether it is well-formed. Square uses this to check whether you reach for a stack the instant 'matching' enters the picture — the same instinct they want when reconciling open transactions against captures.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • Blind (2025-09)— Square POS phone screen; interviewer pushed for early-exit on mismatch.
  • LeetCode Discuss (2026)— Cash App backend warmup.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input is valid if open brackets are closed by the same type and 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

Approaches

1. Repeated replace

Repeatedly strip '()', '[]', '{}' until no change, then check if 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 quadratic; Square interviewers want the stack solution.

2. Stack of openers

Push every opener. On a closer, pop and verify the top matches. Empty stack at end = valid.

Time
O(n)
Space
O(n)
function isValid(s) {
  const stack = [];
  const match = { ')': '(', ']': '[', '}': '{' };
  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: Single pass, O(n) time. Bail on mismatch instead of fighting through — early exit matters on Square's interview rubric.

Square-specific tips

Square interviewers want to see the early-exit instinct: the moment a closer fails to match, return false — don't 'collect errors and tally at the end.' That mirrors how their payment-state machines fail fast on inconsistent close events. Articulate which character class triggers which action before coding.

Common mistakes

  • Forgetting to check that the stack is empty at the end — '(((' passes the per-character checks but is unbalanced.
  • Popping from an empty stack when a closer appears first — guard for that.
  • Treating '(' and '[' as the same; the type must match exactly.

Follow-up questions

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

  • What if non-bracket characters can appear and should be ignored?
  • What if you must return the index of the first mismatch?
  • How would you parallelize this for a 1GB streaming file?

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 not just count opens vs closes?

Counting fails on '(]'. The TYPES must match, not just the totals.

Can I use recursion?

Yes but the call stack mirrors a manual stack with extra overhead — Square interviewers prefer the explicit stack for clarity.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →