Skip to main content

20. Valid Parentheses

easyAsked at Twilio

Valid Parentheses is Twilio's go-to phone-screen stack question: given a string of brackets, decide if every opener is closed by the correct closer in correct order. The rubric grades whether you reach for a stack immediately and handle the three failure modes (wrong closer, unmatched closer, leftover openers).

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Listed across Twilio phone-screen reports as the second question after Two Sum.
  • LeetCode Discuss (2025-10)— Cited in Twilio SWE-1 and SWE-2 initial recruiter-coordinated screen reports.

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; 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
true

Approaches

1. String-replace until stable (rejected, O(n^2))

Repeatedly remove '()' / '[]' / '{}' substrings until the string stops changing.

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.length === 0;
}

Tradeoff: Cute on a whiteboard but O(n^2) — each replace is O(n) and we might do O(n/2) of them. Twilio will let you state this then ask for the linear solution; jumping straight to it without the stack is fine if you preempt the analysis.

2. Stack of expected closers (optimal)

Push the matching closer on every opener; on a closer, verify it matches the stack top. Valid iff the stack is empty at the end.

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

Tradeoff: Pushing the EXPECTED closer (not the opener itself) collapses the compare into a single equality check. Cleaner than the variant that pushes openers and compares to a closer-to-opener map at pop time.

Twilio-specific tips

Twilio interviewers explicitly look for the 'push the closer, not the opener' trick — it's the difference between a 5-line clean answer and a 15-line cluttered one. Walk through the three failure modes out loud (wrong-type closer like '(]', unmatched closer like ')))', leftover openers like '((') before writing code so the grader knows you've thought about edge cases.

Common mistakes

  • Forgetting to check that the stack is empty at the end — '(((' will pass the loop but is invalid.
  • Calling stack.pop() on an empty stack and not handling the undefined return value — JS returns undefined which !== any real closer, so this happens to work, but in Java/Python you'd crash.
  • Using a Set or Map of openers instead of a Map of opener-to-closer — that forces a second branch on the pop check that adds bug surface.

Follow-up questions

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

  • What if you needed to return the LENGTH of the longest valid prefix instead of a boolean? (LC 32 — Longest Valid Parentheses.)
  • What if the input could contain other characters (letters, digits) that should be ignored? (Same algorithm, just skip non-bracket chars.)
  • How would you adapt this to validate JSON or XML, where you have many more bracket types?

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 push the closer instead of the opener?

Single-equality compare on pop. If you push openers, the pop check is `pairs[opener] === closer`, which is a map lookup AND a compare; pushing closers turns it into one compare.

Is there an O(1) space solution?

Not for arbitrary input. You need a stack proportional to the worst-case nesting depth. For very-deep nesting that's O(n); for shallow input, the stack stays small.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →