The problem
Given a string made of brackets ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type, in the correct order.
Input: "([]{})"
Output: truePicture it
Picture a stack of plates. Each opening bracket is a plate placed on top. Each closing bracket must match the plate on top: a “]” can only remove a “[” plate. If the top plate is the wrong kind, or there is no plate at all, the string is invalid. At the end the stack must be empty, otherwise something was never closed.
How to recognise it
- The input has openers and closers that must pair up, and pairs may sit inside other pairs.
- The most recent unclosed opener is the only one the next closer may match. "Last opened, first closed" is exactly how a stack (a list where you only add and remove at the end) behaves.
- The answer is a yes/no check, so you can stop at the first bracket that breaks the rule.
- Up to 10^4 characters, so one pass over the string is expected.
Start with brute force
A valid string always contains at least one adjacent pair like (), [] or {}. Delete those pairs again and again until nothing changes. The string was valid if nothing is left.
def is_valid_brute(s):
prev = None
while s != prev:
prev = s
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return s == ""
Each pass copies the string in O(n) time. A deeply nested string such as ((((...)))) loses only one pair per pass, so it needs n/2 passes: O(n²) time and O(n) space for the copies. For n = 10^4 that is about 5 × 10^7 character copies, and the work grows with the square of the length.
From brute force to the idea
- Find the waste. Every pass re-reads the whole string just to find the few pairs that touch. Most characters are copied again and again without changing.
- Notice what decides a closer. When you read a closing bracket, only one opener matters: the most recent one that is still open. Everything older is waiting underneath it.
- Keep the open brackets on a stack. Read left to right. An opener is pushed with
stack.append(ch). - Check each closer at once. The dictionary
pairsmaps each closer to its opener. A closer is fine only if the stack is non-empty and the popped top is its partner. If the stack is empty, or the top is the wrong type, returnFalseimmediately. - Check what is left. At the end, any opener still on the stack was never closed, so the answer is
not stack.
This is the key idea: the latest unclosed opener is always on top of the stack, so each closer is checked in O(1).
The key idea
Last opened must be first closed, which is exactly what a stack (last in, first out) gives you. O(n).
Python solution
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch not in pairs:
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
return False
return not stackIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): up to n/2 passes, each copying the string | O(n): the string copies |
| Stack (shown code) | O(n): each character is pushed or popped at most once | O(n): a string of only openers fills the stack |
Edge cases
- Empty string: returns
True(nothing to match). LeetCode promises at least one character. - Starts with a closer (
"]"): the stack is empty, sonot stackis true and the function returnsFalsewithout popping. - Only openers (
"(("): the loop finishes, the stack still holds two items, returnsFalse. - Crossed pairs (
"([)]"): returnsFalse; when)arrives the top is[. - Other characters (
"a"): the shown code treats anything that is not a closer as an opener and pushes it, so"a"returnsFalse. The problem only allows brackets, so this does not matter there. - Odd length: always invalid. A length check is a cheap early exit, but the stack already gets it right.
Common mistakes
- Counting each bracket type separately. Counts accept
"([)]", where every type is balanced but the order is wrong. - Popping without checking for an empty stack first, which crashes on
"]". - Returning
Trueafter the loop without checking that the stack is empty, which accepts"((". - Mapping openers to closers but then looking up the wrong side, so every comparison fails.
Instead of True or False, return the position of the first problem: the first closer that has no matching opener, or, if every closer matched, the position of the earliest opener that was never closed. Return −1 if the string is valid. For "([)]" the answer is 2; for "(()" it is 0. Describe your approach, then write it if you like.
Compare with our answer
Use the same stack, but push positions instead of characters, so you can report where things went wrong. A closer that fails returns its own position. After the loop, the bottom of the stack is the earliest opener that never closed.
def first_error(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = [] # positions of open brackets
for i, ch in enumerate(s):
if ch not in pairs:
stack.append(i)
elif not stack or s[stack.pop()] != pairs[ch]:
return i
return stack[0] if stack else -1
first_error("(]") is 1 and first_error("()[]") is −1. Time O(n), space O(n).
A strong answer mentions: storing positions so the character can still be read with s[i], why the bottom of the stack (not the top) is the earliest unclosed opener, and that the result is −1 exactly when is_valid is true.
1. A template engine must check that tags like <b> and <i> are closed by </b> and </i> in nesting order. Which approach fits best?
Tags nest exactly like brackets: a closer must match the most recent open tag, which is the top of a stack. Counting ignores order, so <b><i></b></i> would pass; repeated deletion works but is O(n²).
2. Why is the shown solution O(n) time even though a closer may pop from the stack?
Appending and popping at the end of a Python list are O(1), and every character causes at most one of them. The loop does read the whole string; it does not stop halfway.
3. A learner shortens the check to elif stack.pop() != pairs[ch]:. Which input now crashes?
With "]" the stack is empty, so stack.pop() raises IndexError. In the other inputs every closer arrives when the stack holds at least one opener, so the missing check changes nothing.
Score 60% or more and the lesson is marked complete.