Introduction to Valid Parentheses
The "Valid Parentheses" problem is one of the most classic algorithm challenges you'll encounter in coding interviews and competitive programming. At its core, the problem asks you to determine whether a string containing only bracket characters—(, ), {, }, [, ]—is properly balanced. This means every opening bracket must have a corresponding closing bracket of the same type, and they must close in the correct order.
For example, the string "()[]{}" is valid, while "(]" is not. The string "([)]" is also invalid because the brackets interleave incorrectly, even though every opening bracket has a matching closing bracket somewhere in the string.
Why This Problem Matters
Beyond being a common interview question, the Valid Parentheses problem reflects a real-world concern: ensuring that nested structures are correctly formed. Compilers and interpreters use similar checks to validate syntax in code. HTML and XML parsers verify that tags open and close properly. Expression evaluators confirm that arithmetic expressions with nested parentheses are well-formed before computing results.
From a learning perspective, this problem is the perfect introduction to the stack data structure. Stacks follow a Last-In-First-Out (LIFO) ordering, which mirrors exactly how nested brackets must close: the most recently opened bracket must be the first one closed. Mastering this problem builds intuition that transfers to parsing, tree traversal, undo mechanisms, and backtracking algorithms.
Understanding the Approach
The Stack Strategy
The key insight is that when we encounter a closing bracket, it must match the most recently opened bracket that hasn't been closed yet. A stack is ideal for tracking this because we push opening brackets onto the stack as we see them, and pop from the stack when we encounter a closing bracket to verify the match.
Here's the algorithm in plain English:
- Create an empty stack.
- Create a mapping from each closing bracket to its corresponding opening bracket.
- Iterate through each character in the string.
- If the character is an opening bracket, push it onto the stack.
- If the character is a closing bracket, check the top of the stack. If the stack is empty or the top doesn't match the expected opening bracket, return false. Otherwise, pop the top element.
- After processing all characters, the stack should be empty. If it is, the string is valid; if not, some brackets were never closed.
Edge Cases to Consider
Several edge cases can trip up a naive implementation. An empty string is typically considered valid. A string with only opening brackets like "(((" should return false because nothing closes them. A string with only closing brackets like ")))" should return false immediately because there's nothing on the stack to match. A single bracket like "(" is invalid, as is a single closing bracket like ")".
Implementing the Solution
Let's translate the strategy into JavaScript. We'll use a simple array as our stack since JavaScript arrays provide push and pop methods that operate on the end of the array in constant time.
function isValid(s) {
const stack = [];
const map = {
')': '(',
'}': '{',
']': '['
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === '(' || char === '{' || char === '[') {
stack.push(char);
} else if (char === ')' || char === '}' || char === ']') {
if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
Let's trace through this with the input "({[]})" to see how it works. We read ( and push it, giving a stack of ['(']. We read { and push it, giving ['(', '{']. We read [ and push it, giving ['(', '{', '[']. We read ], which maps to [, and the top of the stack is [, so we pop, leaving ['(', '{']. We read }, which maps to {, and the top is {, so we pop, leaving ['(']. We read ), which maps to (, and the top is (, so we pop, leaving an empty stack. The loop ends and the stack is empty, so we return true.
A Cleaner Implementation
We can make the code more concise by leveraging the mapping object to detect closing brackets rather than listing them explicitly. If a character exists as a key in the map, it's a closing bracket; otherwise, it's an opening bracket.
function isValid(s) {
const stack = [];
const map = {
')': '(',
'}': '{',
']': '['
};
for (const char of s) {
if (map[char]) {
const top = stack.pop();
if (top !== map[char]) {
return false;
}
} else {
stack.push(char);
}
}
return stack.length === 0;
}
This version is shorter and arguably more readable. Note that we use stack.pop() directly when checking a closing bracket. If the stack is empty, pop() returns undefined, which will not equal map[char], so the function correctly returns false. This elegantly handles the case where a closing bracket appears with no matching opening bracket.
Testing the Solution
Thorough testing is essential. Let's write a set of test cases covering valid strings, invalid strings, and edge cases.
function runTests() {
const tests = [
{ input: '()', expected: true },
{ input: '()[]{}', expected: true },
{ input: '(]', expected: false },
{ input: '([)]', expected: false },
{ input: '{[]}', expected: true },
{ input: '', expected: true },
{ input: '(', expected: false },
{ input: ')', expected: false },
{ input: '(((', expected: false },
{ input: ')))', expected: false },
{ input: '({[]})', expected: true },
{ input: '({[}])', expected: false }
];
tests.forEach(({ input, expected }) => {
const result = isValid(input);
const status = result === expected ? 'PASS' : 'FAIL';
console.log(`${status}: isValid("${input}") = ${result} (expected ${expected})`);
});
}
runTests();
Running these tests confirms that our implementation handles all the scenarios correctly. The interleaved case "({[}])" is particularly important because it catches implementations that merely count brackets without respecting nesting order.
Complexity Analysis
Understanding the time and space complexity of your solution is crucial, especially in interviews. For this algorithm, we iterate through the string exactly once, performing constant-time operations (push, pop, and dictionary lookup) for each character. This gives us a time complexity of O(n), where n is the length of the string.
For space complexity, in the worst case—such as a string of all opening brackets like "((((("—we push every character onto the stack. This means the space complexity is also O(n). In the best case, where brackets are matched immediately like "()()()", the stack never grows beyond one element, but we still describe the complexity by the worst case.
Best Practices
Use the Right Data Structure
Always reach for a stack when a problem involves nested or matched structures. While you could theoretically solve this problem with recursion, the stack approach is more efficient and easier to reason about. JavaScript arrays work well as stacks, but if you're working in a performance-critical context, be aware that arrays in JavaScript are dynamic and may occasionally incur reallocation costs. For most practical purposes, this is negligible.
Handle Edge Cases Explicitly
Even though our cleaner implementation handles empty stacks gracefully through the undefined return from pop(), it's often wise to add an early return for an empty string to make the intent clear. Explicit edge case handling improves readability and makes the code self-documenting.
function isValid(s) {
if (s.length === 0) return true;
const stack = [];
const map = { ')': '(', '}': '{', ']': '[' };
for (const char of s) {
if (map[char]) {
if (stack.pop() !== map[char]) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
}
Validate Input
In production code, you should validate that the input is a string and that it contains only bracket characters. The basic algorithm assumes well-formed input, but real-world data is rarely so cooperative. Adding a guard clause or a regex check can prevent unexpected behavior.
function isValid(s) {
if (typeof s !== 'string') {
throw new TypeError('Input must be a string');
}
if (!/^[()\[\]{}]*$/.test(s)) {
throw new Error('String must contain only bracket characters');
}
const stack = [];
const map = { ')': '(', '}': '{', ']': '[' };
for (const char of s) {
if (map[char]) {
if (stack.pop() !== map[char]) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
}
Consider Extensibility
If your application might need to support additional bracket types in the future—such as angle brackets < and >—design your mapping object to be easily extended. Simply adding new key-value pairs to the map is all that's required, and the rest of the algorithm remains unchanged. This is a small but meaningful example of the open-closed principle in action.
Common Variations
Interviewers often extend this problem to test deeper understanding. One common variation asks you to return the minimum number of insertions needed to make the string valid. Another asks you to remove the minimum number of characters to make it valid. A third variation involves multiple types of brackets with different nesting rules. The stack-based approach remains the foundation for all of these, with additional logic layered on top.
Another interesting variation is generating all valid combinations of n pairs of parentheses. This shifts the problem from validation to generation and typically requires a backtracking approach, but the intuition about matching and nesting that you build from the validation problem directly informs the generation strategy.
Conclusion
The Valid Parentheses problem is a deceptively simple challenge that teaches a fundamental lesson about the power of the stack data structure. By pushing opening brackets and popping them when we encounter their closing counterparts, we can verify proper nesting in linear time with minimal code. The solution is elegant, efficient, and extensible, making it a valuable tool in any developer's repertoire. Whether you're preparing for interviews, building a parser, or simply sharpening your algorithmic thinking, mastering this problem provides a strong foundation for tackling more complex challenges involving nested structures and pattern matching.