20. Valid Parentheses

easyAsked at Robinhood

Given a string of brackets, determine whether the string is valid. At Robinhood this is a classic 15-minute warm-up that tests whether you reach for a stack instantly and handle empty-stack edge cases without prompting.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

Glassdoor (2026-Q1)— Robinhood SWE-I phone-screen reports cite Valid Parentheses as a recurring warm-up.
Reddit r/leetcode (2025-10)— Robinhood new-grad onsite trip report lists Valid Parentheses paired with a follow-up on min-stack.

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 and in the correct order.

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

Explanation: Brackets must close in order.

Approaches

1. Stack of expected closers

Push the matching closer for each opener. On a closer, pop and compare.

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

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

Tradeoff: Pushing expected closers means equality is a single comparison instead of a lookup, which reads cleanly under interview pressure.

2. Stack of openers with matching map

Push openers, on a closer pop and check via a closer-to-opener map.

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

function isValid(s) {
  const stack = [];
  const match = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch in match) {
      if (stack.pop() !== match[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

Tradeoff: Equivalent O(n) cost. Slightly more explicit about which side is the closer — interviewers don't prefer one over the other.

Robinhood-specific tips

Robinhood interviewers reliably probe two edge cases: an empty string (must return true under the constraint s.length >= 1 — but think about your guard) and a single closer with no opener (e.g. ')' → false because the stack is empty when you pop). Call these out before submitting. Skipping the empty-stack pop check is the #1 bug on the rubric.

Common mistakes

Forgetting to check that the stack is empty at the end — '(((' is invalid even though no mismatch occurred mid-scan.
Popping from an empty stack and crashing on closers-first input like ')'.
Building a counter (just count of each bracket) — fails on '([)]' which has matching counts but invalid order.

Follow-up questions

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

Generate all valid parentheses combinations of length 2n.
Longest valid parentheses substring (DP / stack-of-indices).
Min Add to Make Parentheses Valid — how many insertions to fix a string.

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 counter only tracks balance, not type-order. '([)]' has perfectly balanced counts for ( and [ but the nesting order is wrong. Only a stack can detect that mismatch.

Can I do this in O(1) extra space?

Not in the general case — the stack depth IS the structural complexity of the input. You could simulate nested counters per bracket type but that quickly becomes a per-type stack itself.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →