Valid Parentheses: Using a Stack for Matching
The Prompt
Given a string `s` containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.
Understanding the Problem
Valid nesting means every closer matches the most recently opened, still-unclosed bracket. That phrase — "most recent, not yet handled" — is the definition of last-in-first-out, which is why a stack is the natural data structure here.
Scan left to right: push every opener; on a closer, it must match the stack top (pop it) or the string is invalid. At the end, leftover openers on the stack also mean invalid.
The Interview Flow
Interviewer
How can you validate a string containing different types of parentheses?
Candidate
This problem is a perfect use case for a stack. The "Last-In, First-Out" nature of a stack helps ensure the brackets are closed in the correct order.
Interviewer
How would that work?
Candidate
I would iterate through the string. If I encounter an opening bracket (`(`, `{`, `[`), I push it onto the stack. If I see a closing bracket, I check the top of the stack. If the stack is empty or the top element is not the corresponding opening bracket, the string is invalid. If they do match, I pop from the stack.
Interviewer
What happens at the end of the string?
Candidate
After the loop, if the stack is empty, it means every opening bracket had a matching closing bracket in the right order, so the string is valid. If the stack is not empty, it means there are unclosed opening brackets, so it's invalid.
Interviewer
Sounds correct. Please implement this.
Why does a stack capture correct nesting?
The invariant: at any point in the scan, the stack holds exactly the brackets that are open and unclosed, in opening order — so the top is the innermost open bracket, the only one a closer is allowed to match. A wrong-type top, a closer with an empty stack, or a non-empty stack at the end each pinpoint a distinct way nesting can fail.
Each character is pushed and popped at most once: O(n) time, O(n) space in the worst case (a string of all openers). No cheaper structure works, because matching depth can be arbitrarily deep.
Solution using a Stack
- Initialize an empty stack.
- Create a map to store the matching pairs of brackets, e.g., `)` maps to `(`, `}` to `{`, and `]` to `[`.
- Iterate through each character of the input string `s`.
- If the character is an opening bracket (`(`, `{`, `[`), push it onto the stack.
- If the character is a closing bracket (`)`, `}`, `]`), check if the stack is empty or if the top element of the stack is not the corresponding opening bracket from our map. If either is true, the string is invalid, so return `false`.
- If they match, pop the opening bracket from the stack.
- After the loop has finished, check if the stack is empty. If it is, return `true`; otherwise, return `false`.
Try it yourself
Write your solution and run it against 5 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
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 (stack.length === 0) {
return false;
}
const lastOpen = stack.pop();
if ( map[char] !== lastOpen ) {
return false;
}
}
}
return stack.length === 0;
}Explanation
Scan s = "({[]})" and watch the stack grow and unwind.
1Three openers in a row: push '(', then '{', then '['. Stack (bottom → top): ( { [.
2i = 3 is ']': the map says it needs '[' — exactly the top. Pop it. Stack: ( {, so the innermost open bracket is now '{'.
3'}' pops '{', then ')' pops '('. The scan ends with an empty stack — every opener was closed in order, so return true.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.