Balanced brackets & validation
In one line
Push every opening bracket and, on each closing bracket, check that it matches the top of the stack; the string is valid only if every check passes and the stack ends empty.
What it is
A bracket string is balanced when every opening bracket has a matching closing bracket of the same type, and pairs close in the right order: the most recently opened bracket must close first. '([]{})' is valid; '([)]' is not, even though the counts match.
That 'most recent first' rule is exactly what a stack models. For a single bracket type, a counter is enough (+1 for '(' and -1 for ')', never below zero, zero at the end), but with several types you need the stack to remember which type is open.
Why interviewers ask
Valid Parentheses is one of the most-asked easy interview questions and a common phone-screen opener. It tests whether you recognise nesting as a stack problem, handle all three failure cases (wrong type, closing with nothing open, leftovers at the end), and it often leads into harder follow-ups: minimum additions to fix a string, the longest valid substring, or removing invalid parentheses.
How it works
- 1Create a map from each closing bracket to its opening partner: ')' to '(', ']' to '[', '}' to '{'.
- 2Scan characters left to right. If a character is an opening bracket, push it.
- 3If it is a closing bracket: when the stack is empty, nothing is open, so the string is invalid. Otherwise pop the top; if it is not the matching opening bracket, the string is invalid.
- 4After the scan, the stack must be empty. Anything left means some brackets were never closed.
- 5Each character is pushed and popped at most once: O(n) time and O(n) space in the worst case (for example '((((((').
Worked example · Checking '{[()]}' and '([)]'
- '{[()]}': push '{', push '[', push '('. Stack ['{', '[', '('].
- ')' matches top '(': pop. ']' matches '[': pop. '}' matches '{': pop. Stack empty at the end: valid.
- '([)]': push '(', push '['. Stack ['(', '['].
- ')' arrives but the top is '[', not '(': invalid immediately. A simple count of each type (one of each) would have wrongly said valid.
Picture it
It is like nested boxes: you can only close the box you opened most recently. If you try to close the outer box while an inner one is still open, the packing is wrong.
Reference code
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs: # closing bracket
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else: # opening bracket
stack.append(ch)
return not stack # leftovers are unclosed
def longest_valid(s):
"""Length of the longest well-formed run of '(' and ')'."""
stack = [-1] # index just before the current valid run
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i) # unmatched ')': new base
else:
best = max(best, i - stack[-1])
return best
is_valid assumes the string contains only bracket characters and runs in O(n) time and O(n) space. longest_valid keeps indices instead of characters so it can measure lengths; for ')()())' it returns 4.
Key patterns
Validate with types
When: Valid parentheses with (), [] and {}
How: Stack of openers; closing must match the top; stack empty at the end.
Counter for one type
When: Only '(' and ')'; minimum additions to make valid
How: Track balance; when it would go below 0, count one needed '(' and reset; at the end add balance ')' to close the rest.
Longest valid substring
When: Longest well-formed parentheses run
How: Stack of indices starting with -1 as a base; on ')' pop, and if empty push i as the new base, else length = i - top.
Remove to make valid
When: Minimum removals to make a string valid (return one valid string)
How: Stack of indices of unmatched '('; mark unmatched ')' as you scan; remove all marked and leftover indices.
Real-world use
Code editors
Editors such as VS Code highlight matching brackets and colour bracket pairs; underneath they track open brackets with a stack-like structure as they parse the file.
Compilers and parsers
Parsers for languages like Python, Java and JSON reject unbalanced brackets with errors such as 'unexpected token' or 'unexpected EOF', using a parse stack to track nesting.
HTML and XML
The HTML parsing standard keeps a 'stack of open elements'; a closing tag such as </div> is matched against it, and XML parsers reject documents whose tags are not properly nested.
Linters and formatters
Tools such as Prettier and ESLint first parse source into a tree; a mismatched bracket stops formatting and reports the line where nesting broke.
In a project
Your team builds a template engine for marketing emails with tags like {{#if}} ... {{/if}} and {{#each}} ... {{/each}}, and broken templates keep reaching production and sending garbled emails.
- Tokenise the template into text, opening tags and closing tags, keeping line numbers.
- Push each opening tag (with its name and line) onto a stack.
- On a closing tag, check the stack is non-empty and that the top has the same name; otherwise report 'expected {{/each}} for the tag opened on line 12'.
- At the end, report any tags still on the stack as unclosed.
- Run the validator in the template editor on save and as a CI check.
Impact: Broken templates are caught in the editor with a precise line number instead of after a campaign is sent, and validation is O(n) so it runs instantly even on large templates.
Trade-offs
Use it when
- Several bracket or tag types that must nest correctly
- You need the position of the error or the matching partner of a bracket
- Nested structures like tags, blocks or quotes must be validated in one pass
Avoid it when
- Only one bracket type and you need yes/no: a counter is O(1) space
- You need full parsing with precedence and grammar rules: use a real parser, which still uses a stack inside
- Matching patterns like balanced brackets with regular expressions: plain regular expressions cannot count nesting
Cost: Time O(n). Space O(n) for the stack in the worst case, O(1) with a counter for a single bracket type.
Common mistakes
- Only counting brackets of each type, which accepts '([)]'.
- Popping from an empty stack when the string starts with a closing bracket.
- Returning True after the loop without checking the stack is empty, which accepts '(('.
- Odd-length strings are always invalid; a quick length check can return early, but do not rely on it alone.
- In the longest-valid problem, forgetting the -1 base index and getting lengths off by one.
Interview questions
Quick revision
- Push openers; on a closer, the top must be its partner.
- Fail if: closer with empty stack, wrong type, or stack non-empty at the end.
- Map closers to openers: {')': '(', ']': '[', '}': '{'}.
- One bracket type: a counter is enough (never negative, ends at 0).
- Longest valid: stack of indices with -1 base.
- Time O(n), space O(n).
- Odd length means invalid.
Check yourself
1. Which string is valid?
2. What does the stack contain after scanning '([{' with no errors?
3. Why is counting each bracket type not enough?
4. What is the length of the longest valid parentheses substring in ')()())'?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.