Valid Parentheses: The Stack Pattern That Unlocks Every Bracket Problem
The stack solution to Valid Parentheses, explained step by step — intuition, a worked walkthrough, JavaScript code, complexity analysis, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Valid Parentheses is the problem interviewers reach for when they want to know one thing: do you understand what a stack is for? Not the API — anyone can call push and pop — but the structural fact it models: whatever opened most recently must close first.
That fact is everywhere. Your editor uses it to highlight matching brackets. Compilers use it to parse nested expressions. HTML validators use it to catch a </div> that closes the wrong tag. Every one of those is this exact algorithm wearing a different costume.
It's also the front door to the bracket stack pattern. Get the reasoning airtight here and expression evaluation, monotonic stacks, and a family of medium-difficulty problems open up.
The problem
Given a string s containing only the characters (, ), {, }, [ and ], determine whether it is valid. A string is valid when every opening bracket is closed by the same type of bracket, in the correct order — and every closing bracket has a corresponding opener.
Input: s = "()[]{}" Output: true
Input: s = "([{}])" Output: true // nesting is fine
Input: s = "(]" Output: false // wrong type
Input: s = "([)]" Output: false // right types, wrong order
Input: s = "(()" Output: false // opener never closedThe third and fourth examples are the ones that kill naive solutions. "([)]" contains one of each bracket, perfectly balanced by count — and it's still invalid, because the ) arrives while [ is the innermost open bracket. Counting is not enough; order matters.
The brute force baseline
If a string is valid, it must contain at least one adjacent matched pair — (), [], or {} — somewhere inside it (the innermost pair). Delete that pair and the string is still valid. So: repeatedly strip adjacent pairs until nothing changes, and check whether anything survived.
function isValid(s) {
let prev = null;
while (prev !== s) {
prev = s;
s = s.replaceAll('()', '').replaceAll('[]', '').replaceAll('{}', '');
}
return s.length === 0;
}This is correct, and it's a genuinely useful way to think about validity. But each pass scans the whole string and rebuilds it, and a deeply nested input like ((((...)))) only loses one pair per pass. That's up to n/2 passes of O(n) work each — O(n²) time, plus a fresh string allocation on every pass. On a 10⁴-character input you're doing tens of millions of character copies to answer a question one scan could settle.
The key insight: nesting is LIFO
Look at what the pair-stripping approach was really doing: it always resolved the innermost unclosed bracket first. That's a Last-In-First-Out discipline — and LIFO has a purpose-built data structure.
Walk the string once. Every opening bracket is a promise: a matching closer must arrive before any earlier opener gets closed. Push that promise onto a stack. A closing bracket may only fulfill the most recent promise — the stack's top. Pop it and compare:
- Top is the matching opener → promise fulfilled, keep going.
- Top is a different opener → brackets crossed, invalid.
- Stack is empty → a closer with no opener at all, invalid.
At the end of the string, the stack must be empty. Anything left on it is an opener whose closer never showed up.
One scan, one stack, and both failure modes — wrong order and wrong count — fall out of the same two checks.
The optimal solution
This is the exact code the interactive visualizer steps through:
function isValid(s) {
const stack = [];
const pairs = { '(': ')', '[': ']', '{': '}' };
for (const ch of s) {
if (ch in pairs) {
stack.push(ch);
} else if (!stack.length || pairs[stack.pop()] !== ch) {
return false;
}
}
return stack.length === 0;
}Three details do all the work:
pairsmaps openers to closers, soch in pairsdoubles as the "is this an opener?" test. No second lookup table, no six-wayif.pairs[stack.pop()] !== chpops and validates in one expression: take the most recent opener, ask what closer it demands, and compare against the character in hand.!stack.lengthshort-circuits first. If a closer arrives on an empty stack, we returnfalsebefore ever callingpop()— no crash, noundefinedlookup.
And the return line matters as much as the loop: stack.length === 0 is what catches strings like "(()" that never produce a mismatch but leave an unfulfilled opener behind.
Walkthrough: s = "([{}])"
| Step | ch | Type | Stack check | Stack after |
|---|---|---|---|---|
| 1 | ( | opener | push | ['('] |
| 2 | [ | opener | push | ['(', '['] |
| 3 | { | opener | push | ['(', '[', '{'] |
| 4 | } | closer | pop { → pairs['{'] is } ✓ | ['(', '['] |
| 5 | ] | closer | pop [ → pairs['['] is ] ✓ | ['('] |
| 6 | ) | closer | pop ( → pairs['('] is ) ✓ | [] |
| end | — | — | stack empty → return true | [] |
Notice how the stack depth traces the nesting depth: it grows to 3 at the innermost point, then unwinds in exact reverse order. Now run the crossed case "([)]": after pushing ( and [, the ) arrives, we pop [, and pairs['['] is ] — not ). Mismatch at index 2, return false, and the rest of the string never even gets read.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Repeated pair-stripping | O(n²) | O(n) | up to n/2 passes, each rebuilding the string |
| Bracket stack | O(n) | O(n) | one pass; each char is pushed and popped at most once |
The stack's worst case is an all-opener prefix like "(((((" — n entries before anything pops. Every character enters the stack at most once and leaves at most once, so the total work is linear no matter how tangled the nesting gets. Invalid strings often finish even faster, because the first mismatch returns immediately.
Common mistakes
- Counting instead of stacking. Tracking three counters (one per bracket type) accepts
"([)]"— counts balance, order doesn't. Only a stack preserves which bracket must close next. - Popping before checking for emptiness. On input
"]", the stack is empty when the closer arrives. Without the!stack.lengthguard,stack.pop()returnsundefinedandpairs[undefined]silently compares wrong — in stricter languages it throws. The guard runs first. - Forgetting the final empty-stack check.
"((("sails through the loop with zero mismatches. Returningtrueafter the loop instead ofstack.length === 0is the single most common bug in first attempts. - Mixing push conventions. Some solutions push the expected closer (
pairs[ch]) and comparestack.pop() !== ch; this one pushes the opener and maps at pop time. Both work — but blend them and every comparison fails. Pick one and stay consistent. - Returning
truemid-loop. Seeing the stack hit empty at step 4 of 8 means nothing —"()]("empties its stack twice and is still invalid. Validity can only be declared after the whole string is consumed.
Where this pattern shows up next
The bracket stack is the front door to a whole wing of stack problems:
- Remove Outermost Parentheses — replaces the stack with a depth counter, the lightweight cousin that works when there's only one bracket type.
- Evaluate Reverse Polish Notation — the stack stores operands instead of brackets, but the LIFO "resolve the most recent thing first" logic is identical.
- Next Greater Element I — the monotonic stack: elements wait on the stack for the value that resolves them, exactly like openers waiting for closers.
- Daily Temperatures — the same monotonic idea at scale, where each stack entry is a day waiting for a warmer one.
Before moving on, step through Valid Parentheses interactively — watching the stack grow on openers and unwind on closers makes the LIFO discipline stick far faster than re-reading code.
FAQ
Why does Valid Parentheses need a stack instead of counters?
Because validity depends on order, not just balance. The string "([)]" has one of each bracket — every counter ends at zero — yet it's invalid, because ) arrives while [ is the innermost open bracket. A stack remembers which opener is most recent and therefore which closer is legal next; counters throw that ordering away. Counters alone only work with a single bracket type, where balance and order collapse into the same condition.
What is the time complexity of the Valid Parentheses stack solution?
O(n) time and O(n) space. The string is scanned once, and each character does constant work: openers push once, closers trigger at most one pop and one comparison. The space worst case is a string of all openers like "(((((", which puts every character on the stack. Mismatches return early, so invalid inputs often terminate before the scan finishes.
What happens when a closing bracket arrives and the stack is empty?
The string is immediately invalid — a closer with no opener means more closing brackets than opening ones at that point. In code, the !stack.length check short-circuits the || before the pop, so stack.pop() never runs on an empty stack. Input "]" returns false on its very first character for exactly this reason.
Why must the stack be empty at the end for the string to be valid?
Every entry still on the stack is an opening bracket whose closer never arrived. The input "(()" never produces a type mismatch — both closers it does have match correctly — but one ( remains stranded when the loop ends. Returning stack.length === 0 instead of a bare true is what distinguishes "no mismatches so far" from "every bracket fully resolved."
Can you solve Valid Parentheses with less than O(n) extra space?
Not in the general three-bracket-type case — the stack is load-bearing, because you may need to remember up to n/2 pending openers in a deeply nested input. If the problem is restricted to round parentheses only, a single integer depth counter suffices: increment on (, decrement on ), fail if it ever goes negative, and require zero at the end. That O(1) variant is exactly the technique used in Remove Outermost Parentheses.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.