Minimum Add to Make Parentheses Valid - Leetcode 921 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum add to make parentheses valid so they give us kind of an interesting way to define parentheses they basically say an empty string is valid and then if you take that empty string and then you wrap it in parentheses it is also valid and if you take two strings that are valid like these two and you concatenate them together that's also valid and now we could kind of keep doing that we could either wrap these or add additional strings that are also valid and just concatenate them so basically what that means is every open parentheses has to have a matching closing parentheses and the order matters the closing one has to come after the open one now if you're familiar with this kind of concept you probably know that the data structure that's commonly used for these types of scenarios is the stack let's see if that's actually going to be useful for us here or not what we want is given some string as suppose something like this we want to know what is the minimum number of parentheses we have to add to make this string valid we don't actually want to build the string just give me the number we only need a single one and that is going to look like this just add it at the beginning because as you can see if we were scanning from left to right we could look at this value and say okay we have an open parentheses we need to remembered that in some kind of way commonly you can use a stack I'll kind of draw that down here we have an open parentheses and then we come to a closing parentheses and what we usually do with that is this should close the previous open parentheses so anytime we see a closing parentheses it's actually not going to be pushed to the stack the stack is mainly going to keep track of the open parentheses so with this one we can actually pop it the fact that our stack is empty right now indicates that so far the string is balanced now when we get to the last parentheses open we notice that our stack is empty there is isn't a matching open parentheses so if we were maintaining our result the number of parentheses we have to add initially it would be zero well now clearly we would increment that guy by one so it would be one by the end of the string again this closing parenthese would not be added the fact that we incremented our result should assume that it was added in a position that makes this valid anyway so while this solution will definitely work is it actually necessary for us to use a stack let's consider a different example the second example down there has three consecutive open parentheses this might make you think you need a stack add those three open parentheses onto the stack because the idea is that we could have some closing parentheses that come after and each closing parentheses would end up popping one of these guys so we might have a chain of these we might need to remember that we have three open parentheses that's why we have a stack to have multiple characters added to it but that's actually not necessary why not just have a single variable which says open right the count of open parentheses initially it's zero as we scan through this we'll increment it every time we see an open one and it'll be set to three by the end if we don't see any closing parentheses well we're going to say that we have three open parentheses that were never closed so our result is going to be three suppose we did have like let's say one closing parentheses well then we would have decremented this count down to two suppose we had two more we would have decremented this guy down to zero maybe if we had one more a fourth one we would add that see that our count is already zero we don't have any open parentheses so this is kind of similar to the stack when our stack was empty remember what we did we took that result which is zero and we will increment it by one so now suppose we had like a couple more open parentheses one two we're going to end up incrementing this count to two and so now at the end what would we return remember this fourth parentheses we actually did close it when we incremented the result so this is like the only parentheses we added that open parentheses and then we ended with a surplus of open parentheses two of them so what should we return probably the sum of these two which would be three in this case that means that this is the one that we added and we would add two more closing parentheses here this actually indicates the number of closing parentheses that we have to add the result indicates the number of open parentheses that we did add and you accumulate them you get the result now this is better than the stack solution because because we have a variable rather than a data structure so constant space and linear time because we're just scanning through the input before I jump into coding this I want to quickly mention you might start to think well that really old classic leak code problem I think it's leak code 20 validate parenthesis don't ask me how I remember that but that one you can't solve without a stack you can't just keep track of the variables and remember that problem actually had three types of parentheses these square and then the curly ones that I'm bad at drawing they had three different types of parentheses that's why you could not just count the number of open parentheses in this problem because if you did let's say you had something like this and then this and then this and then you come across a closing parentheses if you just had the count you have two open parentheses and now one closing parentheses you might think that this can close that but no it doesn't work like that we have to close the curly ones first so not only do we have to keep the count of them but we have to maintain the order of them as well and that's why a stack is necessary for that problem but not for this one okay now let's code it up we'll keep it nice and short I'm going to keep track of the open count since this is a keyword I think it's like a built-in function I'm going to call it open count like that and what we're going to end up returning I'll have my result here as well this is kind of the good part of doing a drawing explanation because now we know exactly what we're going to do return the result as well as the open count then in between let's go through every character there's only two cases either the character is open or it is a closing parentheses if it's open that's the simple case all you got to do is take the open count and increment it by one in the other case we will take the open count and decrement it by one now what if it was already zero well maybe we should set it to the max of itself well itself minus one and zero because maybe decrementing it by one will make it negative so this is one way to handle this you could also do that with an if statement and then um maybe before we decrement the count we check if the open count is already equal to zero then we shouldn't decrement it and that's what this will do it won't really change the open count value but if it's zero and we just got a closing parentheses that means we don't have a matching open parentheses and therefore we're going to increment the result by one so this is the entire solution I'll run it just to show you that it works I promise you it's more efficient than this is indicating but but I wanted to code it a slightly different way if you're kind of a beginner or Noob it might make more sense to see the code written like this where we just decrement the count and then we check if it went negative if it's less than zero now what should we do probably reset it back to zero and increment the result by one because we need a matching open parentheses so this will also work and for whatever reason this time it's more efficient if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon