Valid Parentheses
Valid Parentheses is a easy stack problem solved with the stack basics pattern.
The best approach, optimal (stack), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (remove matched pairs) up.
Problem
Given a string of brackets ()[]{}, decide whether it is valid: every opening bracket is closed by the same type, and brackets close in the correct order.
Examples
Example 1
- Input
s = "{[()]}()"- Output
true
Example 2
- Input
s = "([)]"- Output
false- Why
- The ] arrives while ( is still open.
Example 3
- Input
s = "(("- Output
false- Why
- Brackets left open at the end.
Constraints
1 <= s.length <= 10^4- s contains only ()[]{}.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (remove matched pairs) | O(n²) | O(n) |
| Optimal (stack) | O(n) | O(n) |
1Brute force (remove matched pairs)
O(n²)O(n)Repeatedly delete adjacent pairs (), [] and {} until nothing changes. The string is valid if it ends up empty.
- Loop: replace every (), [], {} with nothing.
- Stop when the length stops changing.
class Solution {
public boolean isValid(String s) {
int prev = -1;
while (prev != s.length()) {
prev = s.length();
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.isEmpty();
}
}class Solution:
def isValid(self, s: str) -> bool:
prev = -1
while prev != len(s):
prev = len(s)
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return not sclass Solution {
public:
bool isValid(string s) {
int prev = -1;
while (prev != (int) s.size()) {
prev = s.size();
s = removeAll(removeAll(removeAll(s, "()"), "[]"), "{}");
}
return s.empty();
}
private:
string removeAll(const string& s, const string& p) {
string out;
size_t i = 0, pos;
while ((pos = s.find(p, i)) != string::npos) {
out += s.substr(i, pos - i);
i = pos + p.size();
}
out += s.substr(i);
return out;
}
};function isValid(s) {
let prev = -1;
while (prev !== s.length) {
prev = s.length;
s = s.split("()").join("").split("[]").join("").split("{}").join("");
}
return s.length === 0;
}2Optimal (stack)
O(n)O(n)Push each opening bracket. For a closing bracket the top of the stack must be its matching opener; pop it. At the end the stack must be empty.
- For '(' push ')', and likewise for '[' and '{' (push the expected closer).
- For a closer: if the stack is empty or pop() != c, return false.
- Return stack.isEmpty().
class Solution {
public boolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (c == '{') st.push('}');
else if (st.isEmpty() || st.pop() != c) return false;
}
return st.isEmpty();
}
}class Solution:
def isValid(self, s: str) -> bool:
st = []
for c in s:
if c == '(':
st.append(')')
elif c == '[':
st.append(']')
elif c == '{':
st.append('}')
elif not st or st.pop() != c:
return False
return not stclass Solution {
public:
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (c == '{') st.push('}');
else {
if (st.empty() || st.top() != c) return false;
st.pop();
}
}
return st.empty();
}
};function isValid(s) {
const st = [];
for (const c of s) {
if (c === '(') st.push(')');
else if (c === '[') st.push(']');
else if (c === '{') st.push('}');
else if (st.length === 0 || st.pop() !== c) return false;
}
return st.length === 0;
}Edge cases to test
- A closing bracket with an empty stack
- Unclosed brackets left at the end
- Odd length (always false)
Hints
Hint 1
The most recent unclosed bracket must be closed first.
FAQ
What is the best time complexity for Valid Parentheses?
Optimal (stack) runs in O(n) time and O(n) extra space.
Which pattern does Valid Parentheses use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Baseball Game, Asteroid Collision, Min Stack.
Is there a brute force solution for Valid Parentheses?
Yes. Brute force (remove matched pairs) takes O(n²) time and O(n) space. Repeatedly delete adjacent pairs (), [] and {} until nothing changes.
Which edge cases should I test for Valid Parentheses?
A closing bracket with an empty stack; Unclosed brackets left at the end; Odd length (always false).