Valid Parentheses is the friendliest stack problem out there, and it is Day 13 of the Tekraze DSA series. We are done with sliding windows and now we step into stacks. Almost every interview prep list starts with this problem for a good reason, and once it clicks, a whole family of matching and nesting problems becomes easy.
Also Read: Day 12, Minimum Window Substring wraps up the sliding window section that comes right before this one.
What is the Valid Parentheses problem?
You get a string s made only of the characters ( ) [ ] { }. Return true if the string is valid. It is valid when every opening bracket is closed by the same type of bracket, brackets close in the correct order, and every closing bracket has a matching opener. You can also try it on LeetCode, where it is problem 20.
Valid Parentheses examples
text
Input: s = "()[]{}"
Output: true
Input: s = "([)]"
Output: false
Why: "[" was opened last, so it must close before ")"
Input: s = "{[]}"
Output: true
How should you think about it in plain words?
Think of stacking plates. Every time you see an opening bracket, you put a plate on top of the pile. Every closing bracket must take off the plate on top, and that plate has to be the same type.
If the top plate is the wrong type, or there is no plate at all, the string is broken. When you reach the end, the pile must be empty, otherwise some brackets were never closed. That is the whole idea in four lines.
What does the brute force solution look like?
Keep deleting matched pairs like (), [] and {} until nothing changes. If the string ends up empty, it was valid.
python
def is_valid_brute(s):
prev = None
while prev != s:
prev = s
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return s == ""
Time is O(n²) because each pass scans the string and you may need about n/2 passes for deep nesting. Space is O(n) for the new strings each pass creates. It is cute and short, but it does far more work than needed.
How do we get the optimal Valid Parentheses stack solution?
Walk through the string once. For an opening bracket, push the closing bracket you expect to see later. For a closing bracket, pop the top of the stack and check that it equals the current character. If the stack is empty or the values differ, return false right away. At the end, return true only if the stack is empty.
Pushing the expected closer instead of the opener is a small trick that removes the need for a lookup when you pop. You just compare two characters.
The Valid Parentheses stack solution runs in O(n) time, since each character is pushed and popped at most once. Space is O(n) in the worst case, like a string of only opening brackets. For a quick refresher on reading these numbers, see our Big O helper post on time and space complexity.
Valid Parentheses in Java
Java’s ArrayDeque is the usual choice for a stack, since the old Stack class is slower and considered legacy.
java
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
// push the closer we expect to see later
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}
public static void main(String[] args) {
String[] in = {"()", "()[]{}", "(]", "([)]", "{[]}", "", "(", "]", "(((", "([]){}"};
boolean[] want = {true, true, false, false, true, true, false, false, false, true};
for (int i = 0; i < in.length; i++) {
boolean got = isValid(in[i]);
System.out.println((got == want[i] ? "PASS " : "FAIL ") + "\"" + in[i] + "\" -> " + got);
}
}
}
Valid Parentheses in Python
In Python, a plain list works as a stack with append and pop.
python
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
# a closer must match the most recent opener
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stack
tests = [("()", True), ("()[]{}", True), ("(]", False), ("([)]", False), ("{[]}", True),
("", True), ("(", False), ("]", False), ("(((", False), ("([]){}", True)]
for s, want in tests:
got = is_valid(s)
print("PASS" if got == want else "FAIL", repr(s), "->", got)
Valid Parentheses in Rust
In Rust, a Vec does the job, and pop returns an Option, so an empty stack is handled safely.
rust
fn is_valid(s: &str) -> bool {
let mut stack: Vec<char> = Vec::new();
for c in s.chars() {
match c {
// push the closer we expect to see later
'(' => stack.push(')'),
'[' => stack.push(']'),
'{' => stack.push('}'),
_ => {
if stack.pop() != Some(c) {
return false;
}
}
}
}
stack.is_empty()
}
fn main() {
let tests = [("()", true), ("()[]{}", true), ("(]", false), ("([)]", false), ("{[]}", true),
("", true), ("(", false), ("]", false), ("(((", false), ("([]){}", true)];
for (s, want) in tests {
let got = is_valid(s);
println!("{} {:?} -> {}", if got == want { "PASS" } else { "FAIL" }, s, got);
}
}
Do all three Valid Parentheses solutions pass the tests?
All three programs ran on the same ten tests, including “()[]{}”, the crossed “([)]”, nested “{[]}”, an empty string, a lone opener, a lone closer and “(((”. Every test passed in Java, Python and Rust.
Also Read: Our data structures cheat sheet has a stack section that pairs nicely with this post.
What are the 6 tips and tricks for an easy solution?
- Spot the pattern. Whenever the most recent open thing must be closed first, think stack. Last in, first out is exactly the rule in Valid Parentheses.
- Push the expected closer. It turns the matching check into a single comparison and keeps the code tiny.
- Exit early on odd length. A string with an odd number of characters can never be valid, so you can return false before the loop.
- Check for an empty stack before popping. A closer with nothing to match is the most common hidden failure.
- Test the edges. Try the empty string, only openers, only closers, crossed pairs like “([)]” and deep nesting.
- Say the plate analogy out loud first. In an interview it shows you understand why a stack fits, not just that it works.
What are the common mistakes people make?
These are the slips that break most first attempts at Valid Parentheses:
- Only counting brackets, which says “([)]” is valid even though the order is wrong.
- Popping from an empty stack and crashing, or treating a missing value as a match.
- Forgetting to check that the stack is empty at the end, so “((” passes.
- Using a list as a queue by mistake and taking from the wrong end.
- Building a big if else chain instead of a small map, which makes adding new bracket types painful.
Where is this pattern used in the real world?
Valid Parentheses is not just an interview exercise. Every code editor and compiler uses a stack to match brackets, which is how your editor highlights the partner of the bracket under your cursor and warns you about a missing one.
HTML and XML parsers check that tags open and close in the right order the same way. JSON validators, calculator apps that handle nested expressions and even the undo history in many apps all lean on the same last in, first out idea.
Which earlier posts in the series should you read?
If Valid Parentheses is your first stack problem, these earlier posts build the skills it leans on:
- Day 1, Two Sum for hash map basics.
- Day 2, Best Time to Buy and Sell Stock for tracking the best answer in one pass.
- Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams for the counting toolkit.
- Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water for the two pointer moves.
- Day 10, Longest Substring Without Repeating Characters, Day 11, Longest Repeating Character Replacement and Day 12, Minimum Window Substring for the sliding window section.
Conclusion
Valid Parentheses comes down to one rule: the most recent opener must close first. Push the expected closer, pop and compare on every closing bracket, and check the stack is empty at the end. Try rewriting it from memory, then run it against the ten tests above. Next up we keep going with stacks.
Frequently asked questions
What is the time complexity of Valid Parentheses?
The stack solution runs in O(n) time because each character is pushed and popped at most once. Space is O(n) in the worst case.
Why is a stack the right data structure for Valid Parentheses?
Brackets must close in the reverse order they opened. A stack gives you the most recently opened bracket first, which is exactly the one that must close next.
Can you solve Valid Parentheses without a stack?
If there is only one bracket type, a simple counter works. With mixed types like ( [ { you need a stack, or something that behaves like one, to remember the order.
Is an empty string valid?
Yes. An empty string has no unmatched brackets, so the usual expected answer is true.
What problems build on Valid Parentheses?
Min Stack, Evaluate Reverse Polish Notation, Generate Parentheses, Longest Valid Parentheses and Daily Temperatures all use the same stack thinking.
