Skip to main content

20. Valid Parentheses

easyAsked at DRW

DRW surfaces Valid Parentheses as a proxy for expression-tree reasoning — a skill that maps directly to parsing FIX protocol tags, validating order-routing rule expressions, and interpreting nested config syntax in trading systems.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2025-Q4)— DRW SWE phone screen candidates report stack-based string-parsing questions in early rounds, with Valid Parentheses as a common example.
  • Blind (2025-09)— DRW interview threads cite bracket-matching as a gateway to nested-expression parsing, which appears in trading-rule engine discussions.

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, and open brackets must be closed in the correct order. 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: Simple matched pair.

Example 2

Input
s = "()[{}]"
Output
true

Explanation: All brackets close in correct order.

Example 3

Input
s = "(]"
Output
false

Explanation: Mismatched bracket types.

Approaches

1. Stack (canonical)

Push open brackets onto a stack. On encountering a close bracket, check whether the stack top is the matching open bracket. If not, or if the stack is empty, return false. After processing, return true only if the stack is empty.

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

Tradeoff: O(n) time and O(n) space in the worst case (all open brackets). This is the expected solution. The match map makes the pairing logic explicit and easy to extend.

DRW-specific tips

After the base solution, DRW typically asks: 'How would you extend this to validate nested operator-precedence expressions in a trading rule DSL — e.g., conditions like ((price > 100) AND (volume < 5000))?' Walk through: the same stack logic handles operator nesting, but you'd also need to track operator precedence. Mention that financial rule engines often use a two-stack variant (operands + operators) — the Shunting-Yard algorithm. Shows breadth relevant to DRW's domain.

Common mistakes

  • Returning true when the stack still has unmatched open brackets — always check stack.length === 0 at the end.
  • Not handling the empty-stack case on a close bracket — popping an empty stack causes a runtime error.
  • Using a counter instead of a stack — a counter cannot distinguish between mismatched types like '([)]'.
  • Forgetting that a string of only close brackets (e.g., ')))') must return false immediately.

Follow-up questions

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

  • Longest Valid Parentheses (LC 32) — find the longest valid substring; requires a more nuanced stack strategy.
  • How would you handle a stream of characters arriving one at a time, returning valid/invalid after each character?
  • What is the expected number of stack operations if the input is a uniformly random string of brackets?

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 stack and not a counter?

A single counter cannot distinguish types. '([)]' has balanced counts but is invalid. The stack preserves the order of open brackets, so you can match each close bracket against the most recent open one.

Can you do this in O(1) space?

Not in general for arbitrary nesting. For pure '()' strings you could use a counter. For mixed brackets you need the stack to track order.

How does this relate to DRW's domain?

FIX protocol messages and trading rule configuration languages often use nested scoping — the same stack invariant validates them. Interviewers want to see you make this connection.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →