The Balanced Parentheses Problem - Classic Stack Problem ("Valid Parentheses" on Leetcode)

Code - https://backtobackswe.com/platform/content/the-balanced-parentheses-problem/solutions Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Write a program that tests if a string made up of the characters '(', ')', '{', '}', '[', and ']' is balanced. Examples " [ () () () ] { } { [ ( ) ] } " valid " { } { ) [ ] " invalid This is another textbook stack problem. Very widely known. Notice how your brain tries to solve this problem subconsciously. Your eyes will try to scan from left to right keeping track of 2 critical things. 1.) The parentheses that are open 2.) The type of bracket that is open When the matching closing parenthesis is found you realize that opening bracket is ok, it has been matched, and your mind then worries about the rest of the open brackets. The Approach We will scan the string left to right. The key is that all points we will keep track somehow of the brackets that have been opened (left brackets) but not closed. When we see a closing bracket we want to be sure that the most recent open bracket is of the same type (and that there even is a left bracket that it is matching). A stack is perfect for this problem. (the LIFO property is a good fit) Our Algorithm -) When we see an open bracket we will push the bracket to the stack, it is now being tracked. It must be closed by the appropriate bracket at some point or else we have a problem. -) When we see a closing bracket, we peek the top of the stack to make sure it is the correct type of opening bracket. -) If it is another closing bracket or the wrong type or there is no bracket then we will return false, the parentheses set is not balanced -) If we get through the whole string without a mismatch then the set is balanced Time & Space Complexities Let n be the length of the parenth