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 Sam K., 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.

More Twilio coding interview questions

See all Twilio problems →

Companies that also ask Valid Parentheses