Beginner LevelData Structures & Algorithms
How do you validate balanced parentheses using a Stack?
ā Interview Prompt: Solve the Valid Parentheses problem for brackets {, (, [ using a stack and explain the algorithm.
Algorithm:
1
Iterate each character in the string.
2
If it is an opening bracket (
(, [, {), push it onto the stack.3
If it is a closing bracket, check if the stack's top matches the expected opener:
ā¢
If yes ā pop the stack.
ā¢
If no or stack is empty ā invalid (return false).
4
After iterating, the string is valid only if the stack is empty.
ā¢
Time: $O(N)$, Space: $O(N)$.
Code Implementation Example
typescript
function isValid(s: string): boolean {
const stack: string[] = [];
const map: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
for (const ch of s) {
if ('([{'.includes(ch)) {
stack.push(ch); // opening bracket ā push
} else {
if (stack.pop() !== map[ch]) return false; // mismatch
}
}
return stack.length === 0; // must be fully matched
}
console.log(isValid("()[]{}")); // true
console.log(isValid("([)]")); // falseš”Stack-based balanced parentheses validation in O(N).
šÆ Interview Key Takeaway
A stack is the natural data structure for matching nested/balanced structures. This pattern extends to HTML/XML tag validation.
#DSA#Stack#Parentheses#Strings#Beginner
Back to all Data Structures & Algorithms Questionsā