20. Valid Parentheses
easyAsked at AndurilDetermine 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 Sam K., 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^4s consists of parentheses only '()[]{}'.
Examples
Example 1
s = "()[]{}"trueExplanation: Each open bracket is immediately matched and closed.
Example 2
s = "(]"falseExplanation: The open parenthesis is closed by a bracket, which is a type mismatch.
Example 3
s = "([)]"falseExplanation: 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.
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.