Valid Parentheses
Prompt
We're writing a tiny linter for a config format that uses parentheses, square brackets, and braces. Given a snippet, tell me whether the brackets are balanced — every opener closed by the right closer, in the right order.
How this round runs
I've left out what counts as a character and what we do with non-bracket text — clarify before coding, and expect me to add a requirement once the basic version works.
Model answer
Clarify first: do non-bracket characters get ignored, or is anything other than brackets invalid input? Three bracket types only, or could more get added later? Is an empty string considered balanced?
A stack is the natural fit, because closing must match the most recent unmatched
opener — last-in, first-out. Push openers; on a closer, the top of the stack
must be its partner or the string is unbalanced. A naive "count each bracket
type" approach is O(n) too but it's wrong — it accepts ([)], where the
counts match but the nesting is crossed. Stack is O(n) time and O(n) space.
function isBalanced(s) {
const stack = [];
const partner = { ")": "(", "]": "[", "}": "{" };
for (const ch of s) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch);
} else if (partner[ch]) {
if (stack.pop() !== partner[ch]) return false;
}
}
return stack.length === 0; // leftover openers means unbalanced
}
Two things people drop: the final empty-stack check (otherwise ( passes), and
popping an empty stack on a stray closer (pop() returns undefined, which
correctly fails the partner check here).
Dry-run on {[()]}: push {, [, (; ) pops ( (match); ] pops [
(match); } pops { (match); stack empty → balanced.
- Asked how non-bracket characters and the empty string should be treated
- Named the LIFO insight and why per-type counting is wrong (rejects ([)])
- Remembered the final empty-stack check and the pop-on-empty case
- Stated O(n) time and O(n) space and dry-ran a nested example
- Add angle brackets and a few more pair types → it's just more entries in the partner map, logic is unchanged
- Report the position of the first mismatch instead of a boolean → track indices on the stack and return the offending index