Valid Parentheses
Check that every bracket in a string is closed by the right kind in the right order, using a stack of the closers still expected, in O(n) time.
Updated Short read: 5 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Remove matched pairs repeatedly | O(n²) | O(n) |
| Stack of expected closers | O(n) | O(n) |
The problem
Given a string containing only the six characters (, ), [, ], { and }, decide whether the brackets are valid. They are valid when:
- every opening bracket is closed by a bracket of the same kind, and
- brackets are closed in the right order: the most recently opened one first.
"()" → true
"()[]{}" → true
"{[]}" → true (nested correctly)
"(]" → false (wrong kind)
"([)]" → false (right kinds, wrong order)
"(" → false (never closed)An empty string is valid: there is nothing left unclosed.
Approach 1: remove matched pairs
In any valid string there is at least one opener sitting directly next to its closer: (), [] or {}. Delete it, and what remains is still valid. Keep deleting until nothing changes. A valid string shrinks to nothing; an invalid one gets stuck.
JavaScript
function isValidParenthesesByRemoving(text) {
let previous;
do {
previous = text;
text = text.replace("()", "").replace("[]", "").replace("{}", "");
} while (text !== previous);
return text === "";
}Python
def is_valid_parentheses_by_removing(text):
previous = None
while text != previous:
previous = text
text = text.replace("()", "").replace("[]", "").replace("{}", "")
return text == ""Time O(n²): each pass scans and rebuilds the string, and a deeply nested input such as ((((…)))) loses only one pair per pass. Space O(n) for the copies of the string.
Approach 2: a stack of expected closers
Read the string once, left to right. The rule "most recently opened, first closed" is exactly how a stack returns things, which makes this the standard introduction to the stack pattern.
- On an opening bracket, push the closer it will need.
- On a closing bracket, pop the stack. The popped value is the closer that was expected at this point. If it is not the character just read, the string is invalid.
- At the end, the stack must be empty. Anything left is an opener that was never closed.
Pushing the expected closer, and not the opener itself, means the check on a closing bracket is a plain comparison.
JavaScript
function isValidParentheses(text) {
const closerFor = new Map([
["(", ")"],
["[", "]"],
["{", "}"],
]);
const expected = [];
for (const ch of text) {
if (closerFor.has(ch)) {
expected.push(closerFor.get(ch));
} else if (expected.pop() !== ch) {
return false;
}
}
return expected.length === 0;
}Python
def is_valid_parentheses(text):
closer_for = {"(": ")", "[": "]", "{": "}"}
expected = []
for ch in text:
if ch in closer_for:
expected.append(closer_for[ch])
elif not expected or expected.pop() != ch:
return False
return not expectedWhen a closer arrives and the stack is empty, pop() returns undefined, which does not equal the closer, so the function returns false. The case of "a closer with nothing open" needs no separate check.
Walkthrough
"{[]}":
| Character | Action | Stack after |
|---|---|---|
| { | Opener: push } |
} |
| [ | Opener: push ] |
}, ] |
| ] | Closer: pop gives ], a match |
} |
| } | Closer: pop gives }, a match |
empty |
The stack is empty at the end, so the result is true.
"([)]":
| Character | Action | Stack after |
|---|---|---|
| ( | Opener: push ) |
) |
| [ | Opener: push ] |
), ] |
| ) | Closer: pop gives ], not ) |
Return false |
Time O(n): each character is pushed or popped once. Space O(n) in the worst case, a string made only of openers.
Why counting is not enough
A tempting shortcut is to count: add one for an opener, subtract one for a closer, and check that the count never goes negative and ends at zero. For a single kind of bracket that is correct, and it uses O(1) space.
With several kinds it fails, even with a separate counter for each. "([)]" has one (, one ), one [ and one ]. Every counter ends at zero and none goes negative, yet the string is invalid, because the brackets overlap instead of nesting. Counts record how many are open. Only a stack records which one was opened most recently.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(isValidParentheses("{[]}")); // true
console.log(isValidParentheses("([)]")); // falsePython
print(is_valid_parentheses("{[]}")) # True
print(is_valid_parentheses("([)]")) # FalseThe comment after each line is the result you should see.
Common mistakes
- Forgetting the final check.
"(("never fails inside the loop. It is invalid because the stack is not empty at the end. - Popping from an empty stack without care. In a language where that is an error, check the size first. In JavaScript
pop()on an empty array returnsundefined, which this solution relies on. - Using counters for several kinds of bracket. See above.
- Returning
trueas soon as the stack is empty. It can become empty in the middle, as in"()(". Only the state at the end matters. - Checking that the length is even and stopping there. An odd length is always invalid, which makes a good early exit, but an even length proves nothing.
Original problem: LeetCode 20: Valid Parentheses