Ones and Zeroes - Leetcode 474 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem ones and zeros we're given an array of binary strings and two integers M and N it's gonna be fun saying those two because they sound so similar so suppose these are the binary strings that were given there's five of them each of them is composed of just ones and zeros and we're given a couple integers let's say m in this case is 5 and N in this case is three just like in this example over here we want to return from this the length of the largest subset of this set of strings we can create if we're allowed to use at most this many zero characters so m in this case corresponds to zero and these are the zeros in our input strings and N corresponds to one so these ones over here and we can use at most three ones and at most five zeros so I guess the first thing you might consider is can we just take all of these strings all five of them well how many zeros would we get in that case we'd get one two three four five six seven that's too many zeros how many ones would we get in that case I think we're allowed to get three but we would get one two three four five six seven so more than we're allowed to get so we definitely can't take all five of these strings so then how do we intelligently figure out how many we can get well the Brute Force way to solve this problem would be with a decision tree so for each one of these we consider if we include it so in this path maybe we're including that string and the other path is where we skip it and we don't include it and we make this same decision for every single string so continuing with this decision tree here we can either choose to include zero zero zero one or we skip it here we can do the same thing include it or skip it so you can see each one of these paths is going to tell us by the time we get all the way to the bottom each one of these paths is going to tell us which one of these we would have included or not included and each one of these paths will be a different subset and how do we know which one we're going to return from all of those well we're going to find the one that is the longest as in it has the most strings in it and let's say in this case that's going to give us a 4 we're going to get a set of four I think that would look like this these four over here because in that case we'll have three ones and we'll have five zeros so these four do satisfy our requirements and it's the longest possible set we could create the largest as four strings in it so that's what we would return now this Brute Force approach the size of this decision tree the height of it is going to be in the worst case the length of this strings well the size of this array that's the height of this tree is going to be we can call that n and we're going to be branching twice every single time so to calculate the size of the tree it's going to be roughly 2 to the power of n so it's not super efficient how can we make this better well as we go along this decision tree we're going to be keeping track of how many M's and ends we have initially it's five and three this is how many we have available to us and then when we go down to this path we don't have five and three remaining we have four zeros remaining and two ones remaining because we used one of each and by the time we get down here we have three less M's remaining because those keep track of zeros so instead of having four and two like over here we'd have one and one because we used three zeros and we used one of our ones and we'd keep doing this now we're keeping track of our M's and our ends but we have a third variable which is going to be I it's going to tell us which string we're currently at first we start at the first string then we go to the second string then we go to the third that like decides what level of this tree we're in as well so we in total have three parameters M and an I but we can use these three parameters to implement a dynamic programming technique called caching or AKA memoization but we have to calculate how many possible combinations will there be for these three parameters well for M there's going to be what the capacity of M possibly was so we'll just use M to denote itself same with n it can't have more possibilities than these it'll be from zero all the way through what the true value of n is passed in as a parameter so we'll have M times n times times the length or the number of strings we have in the input let's say that's s so overall this is how many times the function could be called our recursive function when we cache the result every time we compute a possible value for it we're going to Cache it and then we're never going to have to repeat that work this time complexity will be the same as the memory complexity as well because this is the size of our cache now let me show you what I've been talking about this entire time so this is going to be the memoization code I'm going to show you our cache is initially going to be this dynamic programming hashmap it stands for dynamic programming this is our recursive function I'm going to call it DFS you can call it what you'd like but we have three parameters i m and n the other parameters we don't have to worry about because this function is nested inside of this one so in this recursion we know it's going to be pretty simple but we do have to worry about a few base cases one one is what if we go out of bounds like how do we know when we can stop going through all the strings well when our pointer I is equal to the length of that array in which case we can return 0 because there's zero strings that we could add at that point if we don't have any left to choose from and the other base case is if this has already been computed meaning if this Tuple is already a key in our DP hash map then we're just going to return the value that this key corresponds to now if neither of the base cases execute then we actually have our recursive step so we're going to call DFS now we have two choices remember we can either not include the value not include the string at index I what would we do in that case then we're going to call DFS on I plus one and we're going to leave M and N the same we're not going to do anything with them now the the other case is if we're going to include the string at index I in that case we're still going to pass in I plus 1 we're going to go to the next string but what are we going to pass in for M and N because we have to count how many zeros were in the string which string am I talking about well it's the string at index I we have to count how many zeros there were so I'm going to run that function count the number of zero characters we also have to count the number of one character so let's do the same thing here and let's store these in a couple variables let's say m count and N count and then using these counts we're going to subtract from these variables so M the new count of M is going to be what it originally was minus the M's in the current string that we just used same thing for n so let's do do just this now we have our two recursive calls what do we want to do with them we want to figure out which one led to the maximum that's what we're trying to do here we're trying to find what is the maximum number of strings we could include without overflowing these two restrictions so let's just take the max of both of these I'm going to write it like this I don't know what the cleanest way to write it in Python is but I'm going to put it onto multiple lines this Max we're going to set it equal to the value but we're going to store it in our DP hash map using this as the key and we of course want it to be set to the maximum and then after that we're going to go ahead and return that same value actually I missed something here maybe you already caught it but how do we know that the remaining count of M and the remaining count of n is actually valid what if this be became negative that means we didn't have enough zeros or ones to actually use the string at index I in the first place so actually we have to change this a bit I think the easiest way to write it is to initially set the value in DP equal to this value where if we were to skip the string at index I and then we check this if M count is less than or equal to how many M's we're allowed to use and N count is less than or equal to the number of ends we're allowed to use then in that case we will possibly be able to set the new DP value equal to a different one we'll have to set it equal to the max of what it currently is and the max of this call down here so let me cut that and add it down here clean this up a bit but maybe this was even more educational to have caught a bug la live as we're coding so these are the two cases now we just have to actually call our DFS we'll start at index 0 our M and N count will be whatever is supplied to us up here and then we're just going to return the value that we compute from that ah there was one last bug and it's over here if we are choosing to include the string at index I then the total number of strings is guess going to be the total number of strings from the sub problem which is if we were to have this new M and N remaining and starting at I plus 1 but we have to include the string that we just added so we're going to say one plus the result of this sub problem if we actually do include the string if we don't include the string we don't have to put a plus one because we didn't include anything we just have to go and solve this sub problem I hope that clears it up but now let's run the code and as you can see it works and it's pretty efficient let me quickly show you the more efficient dynamic programming solution without recursion now if we were to code this up without recursion we could do so with three Loops because in this case our cache is going to be three dimensions we're going to follow very similar ideas we're going to use the same key as you can see over here we're using i m and n as the composite key for the string we are counting how many zeros and ones it has and then we're iterating through possible M and N values in this case M and N are once again going to whoops refer to how many zeros and how many ones we have remaining so we're going to use the count of the string to make sure we have enough to actually use this string and if we do have enough to use it then we're going to take the max of pretty much the same value that we used before 1 plus the sub problem DP now here instead of saying I play plus one we're doing I minus 1 because we're iterating through from left to right you could iterate in Reverse I'll show you that one in just a second but here we're iterating in the opposite direction so we're doing I minus one that's the sub problem so in this case I refers to we're allowed to use the string at index I and every previous string that's kind of like the sub problem in this case that's why we say I minus 1 when we look to solve a sub problem now if we're not allowed to use it then we just set it equal to the value at I minus 1 because yes we can't use the string at I at index I but we're allowed to use every previous string so we just take the max value from I minus 1 with the same M and N values and then we will return the value at the largest possible indices in this case actually I change the M and N to be Capital so then I can actually use these two as like iterators through our Loops but you can see otherwise this is pretty similar to the recursive solution the complicated part is pretty much just figuring out which direction to iterate through and also that here we need to start at zero instead of one the reason being in some cases we might decide to use zero occurrences of a character of a zero or a one we can choose to not include any if we want to but otherwise this is the iterative solution the time and space complexity is pretty much the same though now let me show you a way we can actually improve the space complexity and this is how we could do it you can see we are once again using a hash map the fact that this is a default deck just means that if we go out of bounds it's going to return a default value in this case an integer and the value is going to be zero which is exactly what we need in our case this is pretty similar except we are iterating in reverse order and the previous solution I actually showed you will not pass I think it gives time limit exceeded even though the time complexity is the same as the recursive one leak code is just kind of weird but this one will pass this iterative solution will pass on leak code because it's a bit more efficient not just because we're using less memory here you can see when we set a value we're setting it once again equal to the max but we're not using I as a key in our hash map and we are iterating through this in reverse order while the M and N values in reverse order because the way we build the grid and it's going to be hard to explain so let me go back to the Whiteboard real quick we know that our cache is three dimension so it's going to be hard to describe it visually but let's say that this is one of the layers of the three dimensions this is like our grid M by n this is for I equals one basically the first string and then we have another grid over here for I equals one the second string previously I showed us filling in the grid like this from top to bottom this is what I meant when I said top to bottom but suppose from this position sometimes we need to take our M value and subtract it so we have to look up from here if we want to fill in the value at this position we have to look above us sometimes we have to subtract from the N so we have to look to the left so we might have to look to the left or up or maybe even to the top left because if we use the current string then we have less zeros and less ones remaining to choose from so we have to possibly look in this direction when we look in that direction we never look at the same grid we never look at the same I value right now what we're doing is taking the I value and saying I minus 1. we're going to look in the previous grid and we're going to look at it going in the top left Direction now what I'm doing instead of having both of these grids in memory though I'm only keeping a single Grid in memory because I want to reduce the memory complexity from being n times m times s I'm changing it to now only be n times M so doing it this way if we fill this in going top to left and then when we get to here and we want to look in the top left but what we actually want to find is the original value that we stored up here but if we overwrote that we can't do that anymore so what we instead do is don't fill top to bottom we fill bottom to top so like this so now if we got to this position and looked at the top left we would find the original values we would never search bottom or to the right so we'd never even care what we have stored here we'd only look at the top left so that's why we're doing this in reverse order and lastly not only are we doing it in reverse order but here starting at M we're going to go up until the count minus one the number of zeros minus one and the reason we have the minus one here is just because in Python this last value is non-inclusive so we have to go one past that but the reason we're going up until M count is because we don't need to go to any values smaller than that because if we need three zeros for this current string why should we even consider any of the loop iterations where we have less than that why should we even consider any of the loop iterations where we only have zero zeros or maybe we only have two zeros but we need three of them so we're not even going to consider this iteration of the loop this is kind of a shortcut and this is what helps get this solution to pass on leak code so lastly I'll run this just to prove it to you that it does work and as you can see it does but the runtime is kind of random on late cut I don't really pay too much attention to it but if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon