Skip to main content

20. Valid Parentheses

easyAsked at Anduril

Determine if a string of brackets is properly nested and closed. Anduril surfaces this problem in early screens because stack-based state-machine reasoning maps directly to parsing command frames and protocol headers in autonomous systems firmware.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-12)— Reported as a phone-screen question for Anduril embedded software engineer roles.
  • Blind (2025-09)— Anduril early-round coding threads list Valid Parentheses as a common stack-fundamentals check.

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

Explanation: Each open bracket is immediately matched and closed.

Example 2

Input
s = "(]"
Output
false

Explanation: The open parenthesis is closed by a bracket, which is a type mismatch.

Example 3

Input
s = "([)]"
Output
false

Explanation: Brackets are interleaved in the wrong order.

Approaches

1. Stack

Push open brackets onto a stack. For each close bracket, check the stack top for a matching open bracket. Valid if the stack is empty at the end.

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

Tradeoff: Clean O(n) solution. The match map inverts the close-to-open mapping, avoiding a series of if/else chains. Always check stack.length before peeking to avoid undefined comparisons.

Anduril-specific tips

Anduril values concise reasoning. Open with: 'This is a classic stack problem — I push opens, match closes, and validate at the end.' Mention the edge cases explicitly: empty string (trivially valid), string starting with a close bracket, odd-length strings. Systems engineers at Anduril often follow up by asking how you'd handle malformed packets in a binary protocol — the same LIFO logic applies.

Common mistakes

  • Returning true when the stack is non-empty at the end — unmatched open brackets mean the string is invalid.
  • Forgetting to check stack.length === 0 before peeking — if the stack is empty and you hit a close bracket, you should return false immediately.
  • Using a counter instead of a stack — counters work for a single bracket type but fail when mixing '(', '[', and '{'.
  • Mishandling the empty string — the loop never runs, the stack stays empty, and the function correctly returns true.

Follow-up questions

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

  • Extend to support wildcard '*' that can match any single bracket or empty string (LC 678).
  • How would you validate a deeply nested binary protocol frame where delimiters are multi-byte sequences?
  • What is the minimum number of bracket removals to make the string valid (LC 1249)?

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 use a map instead of if/else for matching?

A map makes the close-to-open mapping explicit and easy to extend. If a new bracket type is added, you add one map entry instead of a new else-if branch.

Can I solve this without a stack?

Not robustly. A counter works for a single bracket type, but for mixed types you need to know which open bracket to match — that requires stack ordering.

Does an odd-length string need special casing?

You can short-circuit on odd length, but the stack algorithm handles it naturally since at least one bracket will be unmatched.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →