Skip to main content

20. Valid Parentheses

easyAsked at Bloomberg

Given a string containing only the characters '(', ')', '{', '}', '[' and ']', determine if it is balanced. Bloomberg asks this as a stack-fluency check: can you spot the data structure without prompting and implement it correctly on the first try.

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

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg phone-screen reports repeatedly mention Valid Parentheses as the canonical stack warm-up.
  • Blind (2025-11)— Bloomberg SWE intern + new-grad reports cite this as a near-guaranteed appearance.

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

Example 4

Input
s = "([)]"
Output
false

Approaches

1. Stack with pair map

Push opens onto a stack; on a close, pop and verify the pair matches via a small hash map.

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: The textbook solution. Linear time, linear worst-case space (a string of n opens). Clear and easy to defend in interview.

2. Repeated string replacement (anti-pattern)

Repeatedly remove the innermost (), [], {} pairs until no more changes.

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 === '';
}

Tradeoff: Cute one-liner but quadratic. Bloomberg interviewers want you to recognize a stack problem; do NOT submit this as your only solution.

Bloomberg-specific tips

Bloomberg interviewers expect you to identify the stack immediately — saying 'this is a classic LIFO matching problem' earns a checkmark before you write any code. They sometimes follow up with: 'what if we add () counts but not the bracket types' — that variant only needs a counter, not a stack, so know both reductions.

Common mistakes

  • Forgetting the final 'stack must be empty' check — "(" alone returns true if you only test pair matches.
  • Off-by-one when peeking instead of popping.
  • Building a regex 'solution' that quickly tangles on nested cases.

Follow-up questions

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

  • Longest Valid Parentheses (LC 32) — DP or stack of indices.
  • Generate Parentheses (LC 22) — backtracking with open/close counters.
  • Score of Parentheses (LC 856) — stack with running score.

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 use a hash map for pairs when there are only 3 pairs?

It scales cleanly if the interviewer adds more bracket types and it reads as one line. An if/else chain is also fine — both compile to the same.

Will Bloomberg accept the replacement approach?

Only as a discussion point. State it as O(n^2) and explain why the stack is better — Bloomberg's rubric flags the candidate who can't justify the asymptotic difference.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →