20. Valid Parentheses

Q: Why use a Map over a switch statement?

A Map (or object literal) is O(1) lookup and trivially extensible. A switch requires adding a case for every new bracket type. At Citadel, extensibility is a real concern — their DSLs evolve.

Q: Can this be done without a stack?

Not reliably. You need to remember the most recent unmatched open bracket, which is exactly what a stack tracks. Counter-based approaches break on interleaved types like '([)]'.

Q: What if the string contains non-bracket characters?

Per constraints, the string contains only bracket characters. But note this assumption — in a real parser you'd skip non-bracket tokens rather than treating them as errors.

easyAsked at Citadel

Citadel asks Valid Parentheses to test stack discipline. In financial systems, bracket-matching logic underpins expression parsers for formula engines, query validators, and order-instruction parsing — getting the stack mechanics exactly right under all edge cases matters.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2025-12)— Citadel SWE intern and full-time reports list Valid Parentheses as a common warm-up in technical phone screens.
Blind (2025-09)— Several Citadel SWE candidates noted stack-based questions appear consistently in first-round coding assessments.

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 must be closed by the same type of brackets, open brackets must be 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

Explanation: Each open bracket is immediately closed by the matching bracket type.

Example 2

Input

s = "([)]"

Output

false

Explanation: The closing ')' does not match the most recent open bracket '[', so the sequence is invalid.

Example 3

Input

s = "{[]}"

Output

true

Explanation: Inner brackets are closed before outer brackets — valid nesting.

Approaches

1. Stack with map

Push open brackets onto a stack. On a closing bracket, check if it matches the top of the stack. At the end the stack must be empty.

Time: O(n)
Space: O(n)

function isValid(s) {
  const stack = [];
  const match = { ')': '(', '}': '{', ']': '[' };
  for (const ch of s) {
    if (!match[ch]) {
      // It's an opening bracket
      stack.push(ch);
    } else {
      // It's a closing bracket
      if (stack.pop() !== match[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff: O(n) time, O(n) space. The match object is a constant-size lookup table. Using a Map literal over a switch-case makes the code cleaner and easier to extend. This is the canonical single-pass solution.

Citadel-specific tips

Citadel expects you to handle all three edge cases before writing code: (1) a closing bracket with an empty stack, (2) a mismatched top-of-stack, and (3) leftover open brackets after the loop. Name all three out loud. In a trading system, an unmatched bracket in a formula string is a hard error — your validator must be exhaustive, not optimistic. Follow up by noting that an optimized version could short-circuit early if the string length is odd (O(1) check before the loop).

Common mistakes

Forgetting to check that the stack is empty at the end — a string like '((' returns false, not true.
Calling stack.pop() without checking whether the stack is empty first — this silently returns undefined in JavaScript and the comparison fails in a confusing way.
Using an if-else chain for matching instead of a lookup map — less extensible and more error-prone.
Not considering the odd-length early exit — a quick win to mention even if not strictly required.

Follow-up questions

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

Minimum Remove to Make Valid Parentheses (LC 1249) — which brackets need deletion to make the string valid?
Longest Valid Parentheses (LC 32) — find the longest contiguous valid substring.
How would you extend this to validate a simple arithmetic expression like '(3 + [4 * {2 - 1}])'?

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 Map over a switch statement?

A Map (or object literal) is O(1) lookup and trivially extensible. A switch requires adding a case for every new bracket type. At Citadel, extensibility is a real concern — their DSLs evolve.

Can this be done without a stack?

Not reliably. You need to remember the most recent unmatched open bracket, which is exactly what a stack tracks. Counter-based approaches break on interleaved types like '([)]'.

What if the string contains non-bracket characters?

Per constraints, the string contains only bracket characters. But note this assumption — in a real parser you'd skip non-bracket tokens rather than treating them as errors.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →