Valid Parentheses
Problem statement
You are given a string s that contains only the six characters (, ), [, ], { and }. Return true if the brackets are balanced, and false if they are not.
The brackets are balanced when two rules hold:
- Every opening bracket is closed by the same kind of bracket.
(must be closed by), not by]. - Brackets close in the right order. The bracket opened most recently must be the first one closed.
Think of a quick check on a config file or a template before you deploy it: every { and [ has to be closed properly, or the file will not parse.
Examples
Example 1
Input: s = "()"
Output: true
Explanation: The ( is closed right away by a ) of the same kind.
Example 2
Input: s = "()[]{}"
Output: true
Explanation: Three pairs, one after another. Each pair opens and closes before the next one starts.
Example 3
Input: s = "(]"
Output: false
Explanation: The ( is closed by a ], which is a different kind of bracket.
Hints
([)]. Every bracket has a partner of the right kind, yet the string is not valid. Think about what is wrong with the order.Approach
Optimal: Stack
Intuition
A stack is a pile where you can only add to the top and take from the top. The last item you put on is the first one you take off.
That is exactly how brackets behave. The bracket opened last is the one that must be closed first. So we walk through the string and keep a pile of "opened but not yet closed" brackets.
- When we see an opening bracket, we put it on the pile.
- When we see a closing bracket, it must match the bracket on top of the pile. If it does, we take that bracket off. If it does not match, or the pile is empty, the string cannot be valid.
At the end the pile must be empty. A leftover bracket means something was opened and never closed.
This is faster than removing pairs because we never rescan the string. Each character is handled once.
Steps
- Make a lookup that maps each closing bracket to its opening partner:
)to(,]to[,}to{. - Start with an empty stack.
- For each character
chin the string:- If
chis a closing bracket: if the stack is empty, or the top is not its partner, returnfalse. Otherwise pop the top. - If
chis an opening bracket: push it.
- If
- After the loop, return
trueonly if the stack is empty.
Dry run
s = "([])"
| step | ch | action | stack after |
|---|---|---|---|
| 1 | ( |
opening, push | ( |
| 2 | [ |
opening, push | ( [ |
| 3 | ] |
top is [, matches, pop |
( |
| 4 | ) |
top is (, matches, pop |
empty |
The stack is empty at the end, so the answer is true.
Now s = "(]". Step 1 pushes (. Step 2 sees ], but the top is (, which is not its partner, so we return false straight away.
Edge cases: an empty string returns true because the stack is empty. A string that starts with a closing bracket, like ")", hits an empty stack, so it returns false. A string like "((" ends with a non-empty stack, so it returns false.
Complexity
Time O(n) - We look at each character exactly once. Pushing onto a stack and popping from it each take constant time. So the whole pass costs O(n), and the worst case is the same as the average case.
Space O(n) - The stack holds opening brackets that are still waiting for a partner. In the worst case, such as `"((((("`, every character is an opening bracket and all of them sit on the stack. We do not count the input string itself.
class Solution:
def isValid(self, s: str) -> bool:
match = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in match:
if not stack or stack.pop() != match[ch]:
return False
else:
stack.append(ch)
return not stack
if __name__ == "__main__":
print(str(Solution().isValid("()")).lower()) # true
print(str(Solution().isValid("()[]{}")).lower()) # true
print(str(Solution().isValid("(]")).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: brackets or tags that must open and close in the right order
- Idea: push each opening bracket; for a closing one, the top of the stack must be its partner, then pop
- Cost: O(n) time, O(n) space
- Trap: popping an empty stack on input like
")"; also the stack must be empty at the end, or"(("passes wrongly
Interview follow-ups
The string has only one kind of bracket,
(and). Can you use less memory?Yes. With one kind of bracket you do not need to remember which one is on top, only how many are open. Keep a counter: add 1 for
(and subtract 1 for). If the counter ever goes below zero, returnfalse, because a)had no partner. At the end the counter must be 0. This is still O(n) time but only O(1) space.Return the position of the first bracket that breaks the rule, not just true or false.
Push the index of each opening bracket instead of the bracket itself, so you know where it was. When a closing bracket does not match, or the stack is empty, that closing bracket's index is the first error. If the loop ends with a non-empty stack, the first error is the unmatched opener at the bottom of the stack. Time and space stay O(n). This is how a real linter points at the exact line.
Frequently asked questions
Brackets must close in the reverse order they opened. That "last in, first out" rule is exactly what a stack gives you. The top of the stack is always the bracket that must be closed next. Any other structure, like a plain counter, forgets which bracket came last.
A string like ")" starts with a closing bracket and nothing was opened yet. If you pop from an empty stack, Python raises an error and Java throws an exception. Checking first turns that case into a clean false. This is the most common bug in this problem.
No. Counting only checks that the numbers match, not the order or the kind. The string "([)]" has one of every bracket, so the counts match, yet it is invalid because the ) arrives while [ is still open. The stack catches this because the top is [ when ) shows up.
Yes. A valid string always has an even length, because brackets come in pairs. If the length is odd you can return false at once. It saves time on some inputs but does not change the O(n) cost.
Configs and templates are full of nested brackets: JSON, YAML flow style, Terraform blocks, shell ${...} expansions and Jinja {{ ... }}. A linter or a pre-commit hook checks that brackets balance before the real parser runs. The same stack idea sits inside every parser, so interviewers use this as a warm-up for harder parsing questions.
