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

Key Takeaways

so it is a new year it's a time to reflect on our pasts and our futures so it's about [ __ ] that took a long time it's about 7:00 the university just reopened we have whiteboards so that means a video is going to happen Mama we made it all right so we found a room and I think it's time to talk about New Year's resolution my goals for this year here for this channel are to reach 100,000 subscribers and to get as many software Engineers students Engineers offers at companies big four other software engineer companies offers as many as possible and for me personally my goal is to be a great teacher an energetic teacher and also very clear and concise and and just a good teacher because I feel like a lot of Cs videos and these videos for these interview questions the people that are teaching are really boring and that's one thing that really sucked when I was learning that even though they taught well I really didn't want to watch the videos I think my videos are still kind of like that cuz these questions aren't that interesting they're necessary to like get a job and stuff which matters to people so that's my goal for this Channel and yeah I'm probably going to like do an annoying pitch to subscribe every video so if you're not subscribed subscribe and um yeah let's get into today's video all right so today we have a classic stack problem this is a textbook problem called balance parentheses so sometimes you get this problem you get just a single parentheses like this but in this problem we have three types the way we solve this does not change it just we have three types of parentheses now so the question is write a program that tests given a string of parentheses different bracket types is this a balanced string is this balanced so for example this is balanced you can see the these two brackets pair up these two brackets pair up those two pair up this is not balanced the outside two pair up the inside two do not pair up and now you see outside pair up pair pair and then here they do not pair up so we know this okay this is a classic stack problem cool that makes sense but I want to go through the intuition and if you did not know this is a stack problem what is your mind doing when we're solving this problem this is critical when we're solving this so let's walk through a little example to see what your mind does to solve this all right so let's look at this example right here is this balanced or is this not balanced I want you to look at this string and tell me I hope I didn't write it bad but let let me give you a second and just think about this like is this balanced or not and see what your mind does 2,000 years later all right all jokes aside okay so when we look at this string what your brain will do to see if it's balanced is it's going to look for something critical the critical thing here is when do we open a left parenthesis so let's see we open one here we open one right there there we open one right here we open one right here we open one right here and then what do you notice you notice that we get a closing parentheses and what does that mean our brain says if we are closing a parenthesis two things need to happen it needs to be the same type as what it is closing it needs to be the same type as what it is closing and it needs to be matched to an opening parenthesis so for this example if we see a closing parentheses we know this is one of the three closing parentheses types we know that it has has to match up to the most recent the most recent left parenthesis that we see that is what it has to match to and as you can see here let's use a different color as you can see here they neutralize each other and now the next parenthesis that we need to worry about is this guy he has not been closed and then you see here there's this closing and these neutralize each other and now we need to worry about these two so we keep advancing this is neutralized this guy he neutralizes him that's fine they're the same type and then we see him but that's an open parentheses wrong color and then we see him that's an open and now do you do you notice something we're keeping track of the opens but the most important one the one that matters to us is the open parentheses right here the most recent open we see because that's what will match to the next closing so we see a closing and what has to match to that is the most recent open we have not even gotten to a stack we don't even we're not even thinking about a stack right now we're thinking about how is this solved without anything so now all we have to worry about is this guy and what do we see this is the last this is the last element what do I need to expect the most recent opening bracket is right there it's not the same type and what do I immediately do I immediately know that this is not a balanced parentheses string because I reached the end of my iteration and I am not able to close this off I do not close this off with the right bracket and and we reach the end of the iteration but more importantly we have the wrong bracket type here and therefore this string is not correct so do you notice all we care about is the most recent left open parenthesis that we see and this is why a stack is used for this problem Stacks have a last in first out Behavior we push push an item and the last item to go in is the first out the last left parenthesis that we see is the first one we care about it is the first one we want to eject from the stack that is why we we use a stack for this problem all right so now let's walk through this using a stack so now we're going to look at the each item one by one if we see an open we push it onto the stack it is of interest to us until it is closed and then when we see a closing we want to know that the item at the top of the stack the most recent open parentheses that we saw must be matched correctly so let's walk through this one by one we pick this first guy push him on the stack it's an open it's another open we push him on the the stack it's another open push it on the stack and then it's another open push it onto the stack and so as you can see right now we've touched four elements and now we have four items on the stack and now we see a closing item and we see we look at the top item on the stack is it the closing for this yes correct we pop it or we could just Peak the stack we could pop or Peak we could use either of those from the API and then we remove this item it's checked off and we're good and next we see this closing peek the top of the stack we're fine pop it and now we look here check this check the top of the stack we need to see this kind of parenthesis that closes it we're fine pop it from the stack check this that's an open parenthesis that's an open so we push it and now now we see a close we see a close Peak the top of the stack it turns out we're fine and now we see another close and Peak the top of the stack we have a mismatch so if we popped we'd have this and then we'd have this so what happens is we know immediately that there is a m mismatch we immediately return false because a closing parenthesis is closing a parenthesis that is not a match to it and this is it this is the balanced parenthesis problem you can give me any type of parenthesis you can just deal with this deal with this or all three of them at one time what matters is the last in first out behavior and what do we care about the most recent La the most recent open parenthesis and that's what this is about so let's look at the code and get to it all right so here's the code everything is very basic so what we do is we get our input string we create a stack and then we create an iteration through every single character in the string like we showed before so what we do is if we see a left we push it to the stack or you see a left you push it to the stack if it's one of these opening brackets push it to the stack if we see if it's not a left what we're going to do is see first if the stack is empty that means that we're seeing a right bracket and we have no left bracket to match it to that means then it's not a balanced string so if we just had a string of a closing bracket then our stack is empty there's no left to match it to then it's unbalanced so we need to check for that case an unmatched right character and then we have our normal case where we need to ensure a match so if we have a opening like this on the stack we want to make sure that we have a closing so if we have this we want to make sure it's balanced to this we Peak the top of the stack we don't remove the element we Peak we we see this we need to make sure it's that we see this make sure it's that this make ures that so we're ensuring a match if it is a right bracket in the first place left charge we're going to pop the item if it is a match it will not return false we're going to pop the item continue our iteration and that is the for Loop and then when we reach the end we say we return the result of an is empty call On The Stack why do we do that we do that because in the case we have an unmatched left so say we had two left two left openings and then one right the one right's going to close this but then we're going to have one left opening left and that's not a balanced string so this is the problem this is the problem of balanced parentheses whenever you see parenthesis problem often we're either going to use a stack or we might use recursion if it's like generating parentheses which uses the implicit call stack so this is the balanced parenthesis problem let's look at time complexity very quickly all right so whenever we are solving a problem we want to think of the best case the average case and the worst case time complexity whenever we're declaring time complexity always Define your variables so here n here is the number of characters in our string it is the length of our string we're going to be running in linear time o of n time as our input gets very large our runtime of our algorithm will scale in a linear fashion to the input we don't worry about constants we worry about tail behavior of the way our algorithm scales for the space complexity if the string is valid the worst case we're going to have is n /2 but that still we drop the constant 1 over two gets dropped we still have linear time we scale linearly with the input because this is our worst case we have a left left left left and then we get closed by left left left left we we on the stack we're going to push four lefts and get them all closed but in but in average case you would open one close it open one close it open two close it and that still would have a size of eight but the thing is that is only going to have what two or three elements Max on the stack or that was a rough example but you know what I mean this is the worst case if this string is valid we're going to store half of it but it still scares scales linearly still that so the worst case if we're trying to bound against an invalid input is if we just have a string of all left brackets we are going to put all the items on the stack we're going to put all the items at the stack our last return will return false of course because the stack will not be empty but we're going to have a string we're going to put the whole string which is n elements onto the stack so that is automatically o of n so the worst case space for both of these is still o of N and our space complexity is O of then um and this is iterative we don't need to worry about the call stack so this is the time complexities all right so that's all for this problem if you like this video hit the like button subscribe to this channel share this video I'm trying to do a video every day we are trying to get Engineers offers this is the goal these problems suck to do but I want to see others succeed in the interview so that's all [Music]