Flip String to Monotone Increasing - Leetcode 926 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem flip string to monotonic increasing so we're given a binary string and it's defined as being monotonic increasing if it consists of some zeros possibly none and some ones possibly none but all of the zeros are on the left side and all of the ones are on the right side basically the zeros and ones have been partitioned in this way zeros on the left and ones on the right now it's possible that these could all be zeros that would be fine it's possible that these could all be ones that's fine as well but we can't mix and match like something like this we can't have a 0 1 1 0 and we can't have 0 1 0 and Etc we can't mix these together and we're given a string where we could have them mixed together like these two examples but our goal is to make it monotonic increasing and we want to do so in the minimum number of flips so just by brainstorming you might think that it's possible to solve this with two pointers we could initialize a left pointer and we could initialize a right pointer and maybe do something intelligent but the problem is that we don't have enough information on the left and right side we need to know what's in the middle to be able to intelligently come up with the minimum number of flips so in a sense we do have to brute force it at least that's one way to do it which is basically to say we go digit by digit let's take this example actually I'm going to take the second one cuz it's a bit more interesting but for every single digit we have two choices we start with a zero we can leave it as is or we can flip it to a one and we can make this choice for every single digit in the input string but there's one little catch so we can keep going like this zero one but what about on this right side if we took this zero and flipped it to a one then we can't just go to the second digit and say well it could either be we could either swap it to a zero or swap it to a one or you know depending on what it is it'll be remaining as a one or maybe if it was Zero it'll be remaining as a zero but we can definitely not have zeros come after a one value so we have to make sure if we either flipped a zero into a one we can only have ones that come after it or if we were just given a one like maybe the first value here was a one and we left it as is then we have to make sure that everything that comes after it is also a one because remember we want this to be monoton increasing we're not just looking for every possibility so this is one way to do it and by doing it this way we'll end up with two variables one is going to be the index it's going to help us iterate through this and we're going to do so recursively as you can see with this tree it's going to be a recursive backtracking tree but there's going to be a second parameter that second parameter is going to be a Boolean to indicate whether our string is monotonic increasing so far or a better way to say it would be so far we have only zeros on the left hand side because remember what happens as soon as we encounter a one that we don't change then everything after that has to also be a one so we kind of run out of choices at that point here we would not be able to make this second choice and here as we see ones we would leave the ones as they are but if we ever saw a zero we would have to flip it so we'd have a second parameter but it's a Boolean so with these two parameters we can take this backtracking solution and add a dynamic programming technique called caching to it and the dimensions of these parameters I mean what are all possibilities I could be there's n possibilities one for each position of the length of the input string and the second is a Boolean so there's two possibilities for it so the total number of possibilities for these input parameters is 2 * n so if we cache this then the overall time complexity will also be Big O of n I'm going to quickly show you the code for that but since we are caching the size of our cache is also going to be 2 * n so we're going to need extra memory and there is a more efficient way to do so which I'll show you in just a moment but first let's take a look at the code for this solution so this is what the code would look like it might be a bit confusing but let's focus on these four cases here it is recursive and I have this a second Boolean parameter called Mono it could have had a better name but I hope you kind of understand what it means the base case here is that if we run into an input option that we've already seen and cached in our DP cache before and in that case we would immediately return it and we wouldn't have to go through the recursive case you can see there's actually another base case if our ey pointer is out of bounds then we would want to return zero and I've kind of done that up above I've added those two base cases to our cache itself so that basically allows us to not have to write out this if statement so if I is equal to length s then return zero I've basically reduced the need to do that but that's a small point and you wouldn't really have to know or understand that but these four cases are the important part if we have all zeros up until now and the value we see right now is a zero then we have two possibilities we can either take this zero and swap it that's this case over here where we're taking mono it was originally true we've seen all zeros but then we change it to become false and of course we increment I to one that's we're going to increment I to one in all of these cases because we want to move to the next character regardless but if we take this zero and swap it to a one then we're going to say 1 plus the result of whatever the recursive call is the other option is we leave the zero as is that's this case up down here where I'm not adding the plus one I'm passing I +1 and I'm leaving mono as it is it's originally true and we leave it as true now we don't know which one of these is going to produce the minimum result that's why we're taking the minimum of both of these and assigning it to our DP cache the second case here is that we've seen all zeros up until now but now we encounter a one if that's the case we can choose to swap this one to a zero and that's this down here so we're making a swap so we have the plus one and we're also calling our DFS our backtracking and we pass in mono as it is we know it's still monotonically increasing or rather we know there's all zeros still up until now because we swapped the one to a zero but the other Cas is where we leave this one as it is in that case we don't add a plus one cuz we're not doing a swap but then we have to say mono is no longer true now it's set to false we can't say that we've seen all zeros up until now because we saw this one and we left it as it is these two cases are a little bit more straightforward because we know up until now we don't have all zeros we've seen some ones before and that means every value that comes next also has to be a one so if the character we see is a one then that's good because we don't have to add plus one we just call uh DFS on I +1 leaving mono as it is which is false in the last case since there's only four total possibilities we just say else but we know that mono is is going to be false or actually I just realized I have these comments in opposite order I'm going to take this and move it here sorry for the confusion so this case means since up above we had the character is one down here we know the character is going to be zero if it's zero unfortunately we do have to make a swap because we have to make sure that now every character is a one so we say plus one and we pass an i + one and leave mono as it is it's false and that's all we care about and then we just take that value and then return it that value that we have cached and outside we are just calling our DFS function initially passing in zero that's the index that we're going to start at in our string and initially passing in true we're basically saying that we've seen all zeros up until now because we haven't even seen any characters so we can pretty much say it's monotonically increasing and running this code you can see the run time isn't super efficient but the overall time complexity actually is about as good as you can get but I'll show you a more efficient and pretty tricky way to solve this problem I'll show you the linear time solution that does not take any extra space and we're going to use the same example so let's try to understand this solution we're going to start at the first character it's a zero so we don't really have to do anything then we get to the next character it's a one the main problem we have here is that we don't know what is going to produce the string that takes the minimum number of flips to create we don't know if that means this should be a zero or it should be a one so we still have to consider both possibilities but how can we do that without doing it recursively with two branches well one way to do it is we know that no matter at what point we get in the string as long as we count the number of ones we can always say we can get to the end of the string and say okay we had a three ones total well let's just decide we wanted to flip all of them to zeros so one thing we're going to do is keep track of the ones it's better to keep track of the ones instead of keeping track of the zeros we could do that if we wanted to but remember the zeros have to be on the left side and the ones have to be on the right side and we're iterating from left to right so we're going to be keeping track of the ones because we can retroactively flip them if we later decide to so that's what we're going to do anytime we see a one we're going to uh keep track of it so so count one is going to be one at this point when we get here and then we're going to go to the next position notice how up until now our string is monotonically increasing but now we get to a zero and we do have that choice to make do we want to flip this to a one or do we want to leave it as a zero the good thing is we can make both choices and figure out which one leads to the minimum you want to know how because we have the number of ones that we previously saw in the string if we decide to leave this as a zero we can say let's just flip all of those ones to a zero how many were there just a single one so let's leave this as a zero that's one possibility how many flips would it take to make this string monotonically increasing in that case just one we just have to flip this one bit otherwise we can say let's just take this guy and flip it to a one how many flips is that going to take well in this case just a single flip so what's the minimum of those two well it's going to be one cuz we're basically taking the minimum of one and one so that's going to be one so far so that basically tells us that if we want to make this string monotonically increasing it just takes a single flip notice how it doesn't tell us though what the string looks like it could have looked like this 011 or it could have looked like this 0 0 the good thing is as we continue going through the string we can fall back on either of those but another variable I haven't mentioned yet is the result variable that of course we're going to need to keep track of and this is going to keep track of how many flips we need to make and so far at this point it is one to make this monotonic increasing now let's go to the next character here we see a one what are we going to do we're just going to take our count one and increment it now to be two well hold on I thought every time we go through the string we have to guarantee that this is monotonic increasing how do we know it's only going to take a single bit flip to make that happen well remember we saw a one right now and we guaranteed that it only takes one flip to make this monotonic increasing but the question you might have is we don't know if that means the string looks like 0000 0 or it looks like 011 my answer to you would be does it matter look at this one this would be monotonic increasing and the other possibility 00 01 is also monotonic increasing that's the tricky part that you don't really realize until you actually start looking at a bunch of examples and start playing around with it and this the rest of this algorithm will hold let me kind of run through it very quickly we see another one we don't have to increment our result at all we just take our count one and change it to now three we've seen three ones so far now we finally see the last zero so we have a choice do we want to take all the ones we've seen so far and flip them that would take obviously three flips or we have another choice We Know It took one flip just a single flip to make this monotonic increasing we don't know again if it looks like 0011 something or if it was all zeros but either way if we're going to flip this guy it wouldn't matter if we had 0000001 or if we had 00111 and then one here it doesn't matter so what I'm saying is the choice we have is the minimum of three which is how many ones we'd have to flip or just flip this guy plus however many bit flips it took to do all previous stuff so one plus one from here and which one of these two is the minimum it's two of course I know this is pretty tricky but I hope that it's starting to make sense for you so now let's code it up notice how we didn't need any complex data structure so the memory complexity for this is constant okay the good thing about this solution is it's pretty easy to cat up but not super easy to come up with the result we are going to initialize as zero we're going to initialize the count one also as zero we're going to go through every character in the input string if the character is equal to one remember what are we going to do just increment our count one by one otherwise the other case is we see a zero then we want to take the minimum of whatever the result is so far plus one initially it's going to be zero which makes sense or we're going to take the minimum of count one which is also initially going to be zero and say that this is the number of bit flips it would take to make the string monotonic increasing up until this point and that's what we're going to assign the result to and after all of that is done we're just going to go ahead and return the result I know that looks really easy but don't feel bad if you weren't able to come up with this but let's run it to make sure that it works and as you can see yes it does and it is pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out NE code .io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon