Skip to main content

20. Valid Parentheses

easyAsked at Microsoft

Valid Parentheses is the Microsoft warm-up that tests whether you can pick the right data structure on the first try. The answer is always a stack — explain why before writing code, and use a closing-to-opening hash map so the matching logic is a single comparison.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft new-grad and L60 phone-screen reports consistently list Valid Parentheses as the 10-minute warm-up.
  • Levels.fyi (2025-12)— Microsoft new-grad interview compilation flags Valid Parentheses as the most-repeated stack question.

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, and 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
false

Example 5

Input
s = "{[]}"
Output
true

Approaches

1. Stack with closing-to-opening map (optimal)

Push opening brackets. On a closer, check the stack top matches the expected opener via a hash map. At the end the stack must be empty.

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

Tradeoff: Linear scan with linear stack. The 'must be empty at the end' check catches the unclosed-opener case; the pop-and-compare catches the wrong-type closer. Both early-return on the mismatched-type case.

2. String replace until stable

Repeatedly replace () [] {} with empty string until the string stops changing. Empty string means valid.

Time
O(n^2) worst case
Space
O(n)
function isValid(s) {
  let prev = '';
  while (s !== prev) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}

Tradeoff: Clever but quadratic — each replace scans the string. Microsoft will accept it for correctness and grade you down for not picking the linear-time data structure. Useful only as the 'I know this is wrong but it works' counter-example.

Microsoft-specific tips

Microsoft is grading first-data-structure intuition. Say 'I'll use a stack because the matching pattern is LIFO — the most recently opened bracket has to be closed next' BEFORE writing any code. The hash-map trick for closers is a small detail that signals you've seen this pattern before; without it, you end up writing 6 nested if-statements that work but read sloppily.

Common mistakes

  • Forgetting the final stack.length === 0 check — '(((' passes the per-character logic but is invalid.
  • Popping into a variable, then comparing without checking that pop returned undefined (empty stack with a closing bracket — return false).
  • Hand-writing the six match cases as nested if/else instead of using a map — slow to write, easy to miscopy.

Follow-up questions

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

  • Longest Valid Parentheses (LC 32) — same stack trick with index tracking.
  • Generate Parentheses (LC 22) — backtracking instead of stack.
  • Minimum Remove to Make Valid Parentheses (LC 1249) — two-pass scan.

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 does the empty-stack check matter?

Because the per-character logic only catches mismatches when a closer arrives. Unclosed openers '(((' leave the stack non-empty at the end and would otherwise be wrongly accepted.

Can I do this without a stack?

If only one bracket type exists, a counter suffices. With multiple bracket types you need order tracking, which is what the stack gives you for free.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →