hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum swaps to group all ones together part two I don't think we've actually solved the first one but honestly this is a pretty difficult problem especially for the beginning of the month I think it's going to be a long month the problem is pretty simple to understand the idea is we have an array like this one and in this array we're only going to have zeros and ones so in this example we have three ones and we want to group them all together so that they're all adjacent so one way for us to do that is by swapping elements well that's actually the only way we can do that so we're going to swap these two together so this will be a zero this will be a one now obviously these are all continuous so it took us one swap to do this we want to figure out what is the minimum number of swaps in order for us to make them all continuous this example was pretty simple imagine though if we had a one over here well in that case we would just take this guy swap it here and then take this guy and swap it there and so then we'd have all four of the ones in the middle this is a bit more interesting so here you might think we need to take this guy move it there and probably take this guy and move it there and then we'll have all four of them in the middle but actually this already counts as grouping them together because the idea is that this array is considered to be circular so these are technically adjacent to these so that's going to be something we need to deal with and I'll show you kind of a trick that we can use to do that that actually will be probably the easiest part of the problem one thing I tried to solve this problem with was find the minimum length window such that it contains all of the ones and forgetting about the whole circular aspect of the problem it seems like it would work because we could do something like this for the original example this would be the minimum length window that contains all of the ones and so the length of it is four and if we knew the count of all the ones in the input we have three so if you take the difference between those 4 minus 3 we get one that's what I thought is a reasonable way to approach this problem it seems kind of like a greedy solution but it's not going to work let me actually give you a counter example of why that is so this is a pretty long string well I guess it's an array but you see a couple ones here a couple ones here and a couple ones here here are kind of the holes that we need to fill so if I took my original approach I'd say well this is of length 10 there are six one on so we take 10 - 6 and then we get four so of course it's going to take four operations four swaps to get this right we'd have to kind of push these two over here and then these two can go over here to fill that hole and then we're good right no it actually takes less than four we can actually do this in two swaps I don't want to spoil it for you so you try to figure it out yourself for a second the idea is that by taking these ones and actually filling them in over here we skipped this hole this isn't even a hole anymore because now our ones are all over here and they're already contiguous there's six of them or we could have obviously taken these two and moved them over there and then they'd be continuous here so our previous solution doesn't account for that so we have to get a little more clever I was just kind of staring at this for a second and thinking huh well what's another way we could think about this problem and then I realized it if we have all of our ones and they're all contiguous of course that's going to be of length six in this problem right cuz we have six ones in the input so we need a window of length six so a similar but slightly different approach would be find the window of size six that contains the maximum number of ones so here we have four ones that tells us we're trying to fill these two zeros right cuz 6 - 4 is 2 we're trying to fill those two zeros it doesn't really matter where the rest of the ones are they could be contiguous they could be scattered wherever they want to be but it would only take us two swaps to fill those holes so that's the approach that will work in this case in this example and it'll work in the previous examples find the window that has the maximum number of ones that is of size six in this case because six is the number of ones that were given to us in the input that's how you kind of handle that part of it now to address the circular part of the problem I'll show you two ways to do it one of them is going to require extra space and one of them is going to require constant space but it's going to be a little more tricky I guess for Simplicity consider we're given this input array now obviously you can tell that the ones are already contiguous but the way to approach this and considering the circular aspect is that any kind of postfix of this could be connected to a prefix of the beginning portion a better way to approach it is just to take a copy of the array and concatenate it like this now if you see we can kind of consider any subarrays from here those are valid we can consider any subarrays from here but they're going to be identical to the ones over here but now if we take a subray like this it is kind of the circular aspect we have elements from the end of the array connected to elements to the beginning of the array now the only thing is we can't have something like this like that's not a valid array cuz we can't just create elements how are we ever going to get a subarray of length nine it can't be longer than of length five that's what I'm getting at because five was the original length so no matter how we run it through the middle it cannot be larger than five but that doesn't really matter in our case because remember we're only looking at windows in this example there's two ones so we're only going to be looking at Windows of length two so that's going to be perfectly fine for us we would pretty much just do a sliding window like this sliding window like this this this and then this would be the one that we found that has the maximum number of ones two of them so we take the size of our window 2 - 2 we get zero zero swaps is going to be the result obviously L this approach requires extra memory cuz we're going to have to create a new array by concatenating one to the other is there a way to do this without that yes we can kind of Imagine like this is there the way I'm going to do that is by running my Loop I'm going to have two pointers that's how sliding window Works we're going to have a left pointer here and a right pointer here and the right pointer isn't going to go up until the end of the length of this array consider the length is n it's actually going to go up until 2 * n so we're kind of imagining like this part of the array is there but what happens when our right pointer is somewhere over here well let me quickly label the indexes of everything right now our right pointer is technically out of bounds if we try doing nums of right we're going to get an index out of bounds error but recall that the length of the array n is equal to 5 so if we want the actual value that should be here the trick is just take the index R and mod it by n which in this case is five if we do that this portion is going to be 6 modded by 5 it's going to be 1 so that tells us that the element over here is going to be the same element over here and that does make sense cuz there is a one toone mapping between these elements because they're just copies like these arrays are just copies of each other so that's how you make the Math Workout and how you can reduce the space complexity from oen down to constant so we won't actually have this in memory we'll just iterate our pointer up until 2 * n and then this is how we'll get what value should be in each spot so I'm going to get the length of the input array cuz we're going to need that a couple times I'm going to count the total number of ones in the input and thankfully we can do that with a built-in function called count in Python and I'm going to have a left pointer initially at zero and I'm going to have my right pointer go not up until n but actually 2 * n I'm also going to keep track of two things what are the number of ones in our window I'm going to call that window ones I'm also to keep track of the max window ones because that's going to tell us what was the window that had the maximum number of ones and how many ones could we find in a window of length this because then we can calculate the result like this we know our window has to be of length total ones and the max number of ones that we were able to get is going to be subtracted from this so if they were the same that means we had all ones in that window if there were a few zeros then this difference would be POS positive remember we're doing a sliding window where the sliding window is always going to be of this length or at least that's you know the one that we're going to be considering so um just like this we're going to say if nums of right is equal to one or we can just do this in Python then we're going to increment the number of window 1es and we're trying to maximize the number of window ones so we'll set it to the max of itself and the current window ones just like this this but remember we don't want our window to ever be larger than the total number of ones if it's smaller that's not really going to change the result so we don't really care about it but if it becomes larger then we have to do something so we'll check if the length of our window which we can calculate like this right minus left + 1 is greater than the total number of ones then we need to shift our left pointer but at the same time we should probably update the number of window ones in our current window that can actually easily be updated without using an if statement we can do this number of window ones is going to be decremented by this nums of left so if the number at the index left was a one we're going to subtract from this if it was a zero we don't want to do anything in which case this equation isn't going to do anything that's the whole idea behind this problem the only thing I haven't shown is the modding so remember that these two indices could technically be out of bounds so let's mod this by n and let's mod this guy by n as well whoops okay so that's the entire solution let's just run it and as you can see it works I think it's pretty efficient but I know that the leak code run times are pretty random as you can see though it's definitely a linear time solution technically we have one Loop here counting the total number of ones and we have a loop here if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon