Skip to main content

20. Valid Parentheses

easyAsked at Uber

Given a string of brackets '()[]{}', determine if every opener has a matching closer in the right order. Uber asks this to test stack fluency and whether you reach for the open->close map without prompting.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber phone-screen reports list Valid Parentheses as a 10-minute opener.
  • Blind (2025-12)— Recurring in Uber new-grad recruiter screens.

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

Example 5

Input
s = "{[]}"
Output
true

Approaches

1. Repeated string-replace

Repeatedly remove '()','[]','{}' until no more reductions are possible. Empty string means valid.

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 and easy to write, but each .replace is O(n) and you may need O(n) iterations. Worth mentioning, then pivoting to the stack.

2. Stack (optimal)

Push openers. On a closer, the stack top must be the matching opener (else invalid). Stack must be empty at the end.

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

Tradeoff: Linear time, linear extra space. The stack matches the natural nesting structure of brackets — push on open, pop+verify on close.

Uber-specific tips

Uber interviewers want you to articulate why a stack is the right data structure here. Say: 'Brackets nest — every closer must match the most-recent unmatched opener, which is exactly the top of a stack.' That sentence is worth more than the code itself at the phone-screen stage.

Common mistakes

  • Forgetting to check that the stack is empty at the end — '((' would pass without it.
  • Pushing the closer and popping on an opener (reversed logic).
  • Returning early as 'true' on the first match — has to scan the whole string.

Follow-up questions

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

  • Generate parentheses (LC 22) — backtracking, related but different.
  • Longest valid parentheses (LC 32) — DP or stack with indices.
  • Minimum remove to make valid parentheses (LC 1249) — stack tracking indices.

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 not just count opens and closes?

Counting works for one bracket type but fails for mixed: '([)]' has equal opens and closes but isn't valid. The stack captures the nesting order, which counting alone can't.

Can this be done in O(1) extra space?

Not for arbitrary inputs. The stack depth can be up to n/2 (e.g., '(((...(((') so O(n) space is the lower bound.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →