Solving Valid Parantheses - Leetcode problem


Problem Statement
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Leetcode link - https://leetcode.com/problems/valid-parentheses/
Idea
We can use stack to keep track of the opening brackets and ensures that they are matched correctly with their corresponding closed brackets.
Pseudo Code
Loop through the String and for each element:
If the element exists in the opening brackets array:
Insert it into the stack.
ELSE:
Get the top element from the stack and compare.
IF matching, continue.
ELSE return false.
End Loop
If Stack is not empty then return false
Time Complexity: O(N)
Space Complexity: O(N) // because of the stack
Implementation
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = new Array();
let map = {
"(":")",
"[":"]",
"{":"}",
}
for(let i=0; i<s.length; i+=1) {
// console.log({stack})
if(['(', '[', '{'].includes(s[i])) {
stack.push(s[i]);
} else {
let last = stack.pop();
if(map[last] !== s[i]) {
return false;
}
}
}
if(stack.length > 0) return false;
return true;
};
Subscribe to my newsletter
Read articles from ajith manmadhan directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

ajith manmadhan
ajith manmadhan
Hey, Iโm Ajith ๐ โ a Senior Software Engineer who loves building things that scale and actually move the needle. Iโve spent 17 years working across full-stack, cloud (AWS Certified), and growth engineering โ from launching new subscription models to optimizing performance for millions of users. I write about growth engineering, AWS, and system design, sharing lessons learned (and mistakes made) along the way.