Approach Summary
Push open brackets. On close bracket, check if top of stack is the matching open bracket.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Stack Matching (Optimal) | O(n) | O(n) | Push opening brackets to stack and pop matching pairs on closing brackets in O(n) time. |
| 2 Approach 2: String Replacement Simulation (Baseline) | O(n²) | O(n) | Repeatedly replaces adjacent matching pairs "()", "[]", "{}" until no further reductions are possible. |
| 3 Approach 2: String Replacement Simulation (Baseline) | O(n²) | O(n) | Repeatedly replaces adjacent matching pairs "()", "[]", "{}" until no further reductions are possible. |
Step 1: Baseline
Approach 1: Stack Matching (Optimal)
Time: O(n)
Space: O(n)
Iterate through the string. Push opening brackets to a stack. When encountering a closing bracket, verify that the top element of the stack matches the expected opening partner. If it matches, pop it; otherwise the string is invalid. Finally, check that the stack is completely empty.
Approach 1: Stack Matching (Optimal) Implementation
Approach 1: Stack Matching (Optimal)
class Solution {
public boolean isValid(String s) {
Stack<Character> bucket = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (bucket.isEmpty()) {
bucket.add(s.charAt(i));
} else if ((bucket.peek() == '(' && s.charAt(i) == ')') ||
(bucket.peek() == '{' && s.charAt(i) == '}') ||
(bucket.peek() == '[' && s.charAt(i) == ']')) {
bucket.pop();
} else {
bucket.add(s.charAt(i));
}
}
return bucket.isEmpty();
}
}class Solution {
public:
bool isValid(string s) {
stack<char> bucket;
for (int i = 0; i < s.size(); i++) {
if (bucket.empty()) {
bucket.push(s[i]);
} else if ((bucket.top() == '(' && s[i] == ')') ||
(bucket.top() == '[' && s[i] == ']') ||
(bucket.top() == '{' && s[i] == '}')) {
bucket.pop();
} else {
bucket.push(s[i]);
}
}
return bucket.empty();
}
};class Solution:
def isValid(self, s: str) -> bool:
stack = []
for char in s:
if char in '({[':
stack.append(char)
else:
if not stack:
return False
top = stack.pop()
if (char == ')' and top != '(') or \
(char == '}' and top != '{') or \
(char == ']' and top != '['):
return False
return not stackfunction isValid(s) {
const stack = [];
for (const c of s) {
if (c === '(' || c === '{' || c === '[') {
stack.push(c);
} else {
if (stack.length === 0) return false;
const top = stack.pop();
if ((c === ')' && top !== '(') || (c === '}' && top !== '{') || (c === ']' && top !== '[')) {
return false;
}
}
}
return stack.length === 0;
} Step 2
Approach 2: String Replacement Simulation (Baseline)
Time: O(n²)
Space: O(n)
In a valid parenthetical expression, there must exist at least one adjacent matching pair "()", "[]", or "{}". We replace all such pairs with empty strings in a loop until the string stops shrinking. If the resulting string is empty, the original was valid; otherwise it contains unclosed brackets.
Approach 2: String Replacement Simulation (Baseline) Implementation
Approach 2: String Replacement Simulation (Baseline)
class Solution {
public boolean isValid(String s) {
int prevLen = -1;
while (s.length() != prevLen) {
prevLen = s.length();
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length() == 0;
}
}class Solution {
public:
bool isValid(string s) {
int prevLen = -1;
while (s.size() != prevLen) {
prevLen = s.size();
size_t p;
while ((p = s.find("()")) != string::npos) s.erase(p, 2);
while ((p = s.find("[]")) != string::npos) s.erase(p, 2);
while ((p = s.find("{}")) != string::npos) s.erase(p, 2);
}
return s.empty();
}
};class Solution:
def isValid(self, s: str) -> bool:
prev_len = -1
while len(s) != prev_len:
prev_len = len(s)
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return len(s) == 0function isValid(s) {
let prevLen = -1;
while (s.length !== prevLen) {
prevLen = s.length;
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length === 0;
} Step 2: Most Optimized
Approach 2: String Replacement Simulation (Baseline)
Time: O(n²)
Space: O(n)
In a valid parenthetical expression, there must exist at least one adjacent matching pair "()", "[]", or "{}". We replace all such pairs with empty strings in a loop until the string stops shrinking. If the resulting string is empty, the original was valid; otherwise it contains unclosed brackets.
Approach 2: String Replacement Simulation (Baseline) Implementation
Approach 2: String Replacement Simulation (Baseline)
class Solution {
public boolean isValid(String s) {
int prevLen = -1;
while (s.length() != prevLen) {
prevLen = s.length();
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length() == 0;
}
}class Solution {
public:
bool isValid(string s) {
int prevLen = -1;
while (s.size() != prevLen) {
prevLen = s.size();
size_t p;
while ((p = s.find("()")) != string::npos) s.erase(p, 2);
while ((p = s.find("[]")) != string::npos) s.erase(p, 2);
while ((p = s.find("{}")) != string::npos) s.erase(p, 2);
}
return s.empty();
}
};class Solution:
def isValid(self, s: str) -> bool:
prev_len = -1
while len(s) != prev_len:
prev_len = len(s)
s = s.replace("()", "").replace("[]", "").replace("{}", "")
return len(s) == 0function isValid(s) {
let prevLen = -1;
while (s.length !== prevLen) {
prevLen = s.length;
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}
return s.length === 0;
}Edge Cases to Watch
- Odd length string (cannot be valid, can exit early)
- Closing bracket appears first with empty stack (e.g. "]" or ")("; returns false)
- Unmatched trailing open bracket (e.g. "()("; stack is non-empty at end, returns false)
- Mismatched bracket types (e.g. "(]"; returns false)
Algorithmic Pattern
View Pattern Guide →
Master the Stack Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Stack pattern.
How to Recognize This Pattern
- Bracket matching
- Nested structure validation
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
String Stack
Frequently Asked Questions
What is the optimal time and space complexity for Valid Parentheses?
The optimal solution for Valid Parentheses achieves O(n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n) because each character in s is pushed and popped from the stack at most once. Space complexity is O(n) in the worst case (e.g. all opening brackets "(((((").
How do I identify that Valid Parentheses requires the Stack pattern?
In technical interviews, look for key problem signals: Bracket matching; Nested structure validation. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Stack strategy.
What critical edge cases must be handled in Valid Parentheses?
Essential edge cases to verify include: Odd length string (cannot be valid, can exit early); Closing bracket appears first with empty stack (e.g. "]" or ")("; returns false); Unmatched trailing open bracket (e.g. "()("; stack is non-empty at end, returns false); Mismatched bracket types (e.g. "(]"; returns false). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Valid Parentheses?
Valid Parentheses is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Amazon, Facebook, Bloomberg.