Minimum Number of K Consecutive Bit Flips - Leetcode 995 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum number of K consecutive bit flips it's a hard but I'm about to make it look relatively easy at least for a hard problem though I don't necessarily expect you to come up with all of this by yourself so the idea is we're given an array which is going to be a binary array it's going to be made up of zeros and ones so consider this example where this is the input array that we're given and we're given a second parameter which is k equal 3 so the idea is we want this entire array to just be all ones but the only operation we're allowed to do is we can perform a swap like we can flip K consecutive values so like we can pick a window of size K and then flip it in this example we'd probably want to do that with the first window here so let's turn all of these into ones next we see that all of these have been ones this is a one here the next zero is going to be over here now you tell me like obviously there are multiple ways to flip this right like we could flip it like this or we could flip it like this for some reason I don't know why you would want to do that like we already have these set as ones so probably the best way to do this is like kind of be greedy we know that this zero has to be flipped and so let's put it at the beginning of the window because everything before it is a one so as we go through this problem we're kind of going to assume that like wherever our pointer happens to be we're going to assume everything before that is good we don't want to touch that we don't want to ruin it so let's stick to this idea so here let's flip this this is going to be a one these are now going to be zeros and it turns out that it worked out for us in this case these two are uh Zer this is a zero we can pick this window we can flip it and I think that took us three flips what we would return in this case is going to be three basically what is the minimum number of flips that we have to perform to make the array all ones what if the example was slightly different what if we actually didn't have this last element here remember that these were still zeros there's nothing for us really to do like with this array we can't do anything we can flip these three I guess that'll fix this one we could flip these three that'll fix these two but then somebody's going to be ruined like one is going to turn into a zero somewhere and we can't only flip a single bit we have to flip K bits with this example we do not have a Solution that's why I'm frontloading all of the ones I want all the ones to be at the beginning because if we do have a few zeros left there should be exactly K of them and if not then we don't have a solution it's better to have it like this than to have like two zeros in the middle of the array and then ones everywhere else in that example we would return Nega 1 that's what we're told to do so how do we go about solving this problem like I've drawn pretty much everything out for this example but how would we keep track of of all of those things algorithmically like what kind of data structures do we need well this is the idea if we like are at this position we see it's a zero okay let's do a flip flip all K of these we could update the array itself to do that like there's nothing wrong with doing that let's turn all of these into ones and we're good now we move the pointer over here everything is kept in track with this array in the worst case we'll end up iterating over the entire array we might have to do a flip Maybe in every single position I don't know what the example would look like maybe something like alternating would probably lead us to an example like that where we would have to like flip these K to turn this into a one and then this would be a zero then flip these etc etc so something like that maybe but the point is that if we have to do that we have to do n flips a flip is going to take us K cuz we literally have to change each value then the overall time complexity is going to be o of n * K now we can do better than that not that this is a bad solution but we itely can do better and that's what I'm going to show you we actually don't need to perform every single flip is there some kind of way that we could keep track that these K elements have been flipped I mean our pointer is going to be over here this is where we performed the flip from like the next K elements from here and we know that once we flip this guy we're going to move our pointer here and we're never going to worry about anything that came before anyway but we should remember that we did perform a flip at index0 because that tells us that everything from index0 up until 0 plus K minus one that would be this index over here like if we do plus K we're going to go one out but if we do plus K minus one we're going to stop here and we want to know that these two have already been flipped like we need some kind of information we could store that in a single variable right like just say okay the last flip happened at index zero but what if we do another flip at index one and let's say k is really really big it could be 10 like it could include all of these then we would want to know that this value was flipped once and then it was flipped again so it went from one to zero to back to one the hard part about this is keeping track of multiple flips and how they influence the remaining portion of the array that's the hard part so how do we keep track of multiple flips that have occurred well just like yesterday's problem we can actually use a cue to do that because as we perform flips we're going to say okay I'm here I'm going to do a flip at index zero then I'm going to do a flip at index one then maybe I'm going to do a flip at index 3 well at some point if our window is K like now my pointer is over here well the only flips that should influence this guy are Flips that happened from here to here like in this range so I'd want to remove this I'd want to pop it and I'd want to pop it so we're going to be adding indexes that have been flipped and then popping them as we shrink the window like as we shift our pointer we don't want anything that's further than this like that K distance and that's pretty much the solution to solve this problem I'll kind of just dry run through it really quickly this is our Q down here it's going to keep track of the indexes that have been flipped so here we see it's a zero so go ahead and flip these three so I'm just going to turn them all into ones and our flip was performed here at index zero so I'm going to add that there I'm going to go to the next element it's all already a one how would we know that I mean I didn't literally change the input array how would we know that there's a one over here well I'm going to take the length of the Q because we're going to assume that everything in the Q every flip that happened that's present in the Q does affect the current position and so if there was one flip performed and the value here happens to be as zero what we're going to do the calculation I'm going to do is going to be 0 + 1 and then I'm going to mod that by two and here we're going to get a one the reason I'm doing the mod is because if a value starts at 0er and you mod it by two well it's going to stay zero if you have a one and you mod that by two it's going to stay as one but if you start introducing some flips so let's say I performed five flips 0 + 5 is five I mod that by two I get one that means if I flip zero five times I'm going to get one that makes sense cuz an odd odd number of flips should change Zero into a one and if you do the same thing for a one you'll get pretty much the same result so if I took one moded by two and then let's say I added five flips to it then this is going to be six 6 modded by two is going to be zero and that makes sense if you take one flip it five times the result is going to be zero so that's the calculation I'm going to do so when we look at this pointer at this position it's a zero plus the length of this that's one mod that by two it's a one as a result so there for we know that the True Value here is actually a one and we're going to move to the next position do the exact same thing the true value is a one now it's going to get interesting we haven't done any more flips in this area so now we're here we're at index 3 but our window should stop here so this is the part where we pop from the queue we're going to pop this guy cuz it's too far away and now we're here it's a one so we're good we just shift our pointer to the next position now here our Q is empty nothing to do there but this is a zero now so we're going to add the index I think it's four we're going to add that to the Q we're going to flip this even though we're not technically changing the array I'm just going to still redraw it this is going to be a one a zero and a zero okay now we move to the next position now this is a zero and we'll know that because 1 plus the length of the Q that's two mod that by two we get zero so the True Value here is a zero and so we perform another flip flip this is index 5 I believe so I'm going to add five to the Q and so now the values in all of these positions are just going to be11 and then I'm going to go here it's a one here it's a one and then we're done so we ended up doing three flips as you can see so our result would be three in this case so now let's code it up these were some of the notes that I took uh when I was coding it up myself it may or may not be helpful for you but just wanted to leave that there just in case but now let's restart so we are going to have that que I talked about I'm going to use a deck in Python we're going to have the total number of flips I'm going to call that result that's what we're going to end up returning and then I'm going to go through every position in the input and remember ultimately what we want to do is something like this we want to take the current element number at index I we want to add to it the length of the que because that tells us how many flips how many operations have been made that are relevant to this position and then we want to mod that by two and if it's a zero then want to perform a flip here now before I do that actually I guess I might as well cuz this is pretty simple so first we want to check if we have enough elements remaining cuz that's the case where we're going to return Nega 1 if I + K is greater than the length of nums that means we don't have K elements remaining starting from index I therefore at this point we'll return negative-1 we can't really perform a flip we have to return negative 1 otherwise we're going to try to do the flip now there's not a lot involved in doing that one we probably want to update the result if we're doing a flip let's increment that by one two let's add the flip to the Q so we'll say that we did a flip at this index aend index I and that's it the difficult part is the part up here well it's not really difficult but it gets into why we're using a q in the first place remember we want all flips that are in the que to be relevant to the current window so we're going to say this while the Q is non-empty and while our index currently is greater than the last valid index for the flip in the queue and we're going to look at the first flip in the queue we're going to go from left to right so we're going to take the flip at index0 and this will tell us the index that the flip happened at and to that we're going to add K minus1 if that doesn't make sense just think of a window like this 0 1 2 3 let's say k is equal to three and let's say we did a flip at index zero the last valid index that that flip would affect is going to be index two right so this window and if you do the calculation um at the top right 0 + 3us 1 is going to be 2 so that's the idea behind this equation so if I is greater than the last valid index that means that that flip does not affect the current index in which case we want to pop that flip so Q pop left and that's literally it this is the entire solution in my opinion the way I've coded it up is definitely more simple than the editorial but you can decide that for yourself on the left you can see that this solution does work it's pretty efficient but there's actually one little optimization that we can make to it so going back to the drawing board I want to show you a solution that doesn't actually save time but does reduce the space the solution I just coded up in front of you was a linear time solution but also linear space well I guess it actually wasn't linear space I think the max size of the Q would be K CU it's never going to be larger than like the window so I think this was the time and space complexity which I think is perfectly fine but you can reduce the space complexity which I do want to show you now the cavat is that we can only get the constant space solution if we modify the input array sometimes that's not allowed so check with your interviewer before you attempt to do something like that but the idea is very very similar to the solution like there's only going to be a few lines of code that we change here we did a flip instead of adding that to a separate data structure we're actually going to change this value to a two that's going to tell us that there was a flip that happened here and we're allowed to do that because once we flip like then we're going to move to the next index we're never going to consider that again because we're going to assume it's going to be a one and it's going to stay a one so it's fine for us to change this to a two but that alone is not enough we're going to have a variable that's going to tell us how many flips we've made that are relevant to the current window so instead of having a q which we just took the length of the Q to tell us how many flips we're actually just going to have a dedicated variable for exactly that purpose so here we did a flip now technically these are going to be one one and this variable here flips is going to be set to one we've done one flip that's relevant to the current window next we move the pointer here flip is going to stay one and this is one so we're good next pointer is here this is one so we're good now the pointer is going to be here we know that the flip that we made was over here but how do we know that like we didn't store that information anywhere well the way we're going to do this is actually very very simple we always know that the size of the window is always going to be K so if there was an element that we performed a flip at that was out of bounds it's always going to be at this this index minus K from here minus K is going to bring us all the way over here so all we do is check is the value over here a two if it is that means that that flip was a part of our window over here but now that we've shifted over here that flip is no longer a part of this window so we would decrement the count of flips down to zero now and now that we're here we have zero flips so what value is this this 1 + 0 well that's still one so it's a one so no need to flip this guy next we're going to be here it's a zero and we have zero flips so we know for sure that this actually is a zero so let's do a flip let's change this into a two not a one and we'll assume that these will look like zeros but we're not actually changing these and so now we would increment the number of flips to be one again now our pointer is over here we see a zero again because the original value is a one and we performed one flip so this is definitely a zero so let's perform another flip let's turn this into a two uh this will look like a one and this will look like a one and now the number of flips we'll have is going to be two and then we're going to look at this value the original value was a one with two flips it'll stay as a one and then we'll be over here and at that point we'll see that over here there was a flip but it's now outside of the window so we'll decrement the number of flips down to one that doesn't really change anything because this is still going to be a one and we're done so we had three flips and we didn't need any extra memory to do that so it's very similar to the last solution just kind of storing some information within the array like I said we're not going to need a lot of code modifications to this so I'm going to name this pretty descriptively I'm going to call it current window flips just because there's not a lot to code for this to be honest remember how we were using the length of the que well now we're going to use this variable so I'm just going to copy it and substitute it over here the rest of this code looks correct except the fact that we are appending to the Q instead of doing that let's go ahead and increment this variable and also let's change the number itself at index I to be a two that's going to be important for this part up here CU we don't have the Q anymore we're going to do something different we're going to say if I minus K first of all let's just make sure that that's in range and then we're going to check if the number at i- K is equal to 2 that element is now outside of the window so we have to then decrement current window flips and that's I think all the changes that we needed so it's pretty similar to the previous solution and as you can see it works and it's very efficient if you found this helpful check out NE code. I'll be launching a python for coding interviews course pretty soon it'll have a lot of interactive lessons thanks for watching and I'll see you soon on