Remove Duplicates from Sorted Array II - Leetcode 80 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem remove duplicates from sorted array 2. so we're given an integer array nums that's sorted in non-decreasing order that basically means that it's sorted in increasing order but there could be duplicates so they say non-decreasing just to be absolutely correct but maybe an array that looks like this the problem is that we might have a bunch of duplicates as we can see here we have three copies of one we have two copies of two and we have two copies of three but we are only allowed to have at most two copies of any value in this array so we can have two twos two threes and two ones but we can't have three one so we remove it but how do we remove it because we could just pop from the middle of an array but that's not very efficient so instead what we do is just shift the values so what we would actually want to do in this case is remove this too but we'd also remove these two guys and move the two values over here same with these two threes we'd want to remove them from their original positions and then push them over here where the next available slots are so this is what our actual array would look like now when we say remove from here we're not actually deleting that memory or even overwriting the value in this position but we consider it deleted our actual output array will look like this one one two two three three but we need some way to indicate that these are the only real values like this is taking up space but don't consider this as an actual value so what we do is return an integer indicating the size of this portion of the array which this problem refers to as k the convenient thing is that the way we're going to solve this problem we're going to have a pointer I think it's going to be called I but it might be called something else but at some point that pointer is going to be all the way over here and the way that indexes work they start at 0 1 2 all the way up until 6 in this position and look at that the size of this array happens to be six so wherever we leave off at the end of the array is also going to be the length of this portion so that's exactly what we can return whatever value this pointer lies on and it's possible that maybe we end up going out of bounds like our eye pointer over here is actually out of bounds that's also going to work so that's what we're looking to do now how exactly can we solve it that's the tricky part I'll show you a valid way but first let's go over the thought process so let's take a look at a slightly different example I basically just added another two over here so now the values that we're going to remove is this and this but if you try to solve this problem like the first version of this remove duplicates from sorted array what you would do is have two pointers let's call them a left pointer and a right pointer initially they're gonna both start here and we're gonna take the right pointer and increment it any time we see a value like in this case the right pointer okay we see one one then the right pointer is over here another one that's fine we can have up to two of them but now over here we see a third one so what we would do here is we'd say the left pointer is going to be incremented because we have a one here we're allowed to have that so we move the left pointer over here and we move the right pointer as well the right pointer is going to tell us what value we're looking at and I'll show you what the left pointer is going to tell us here we have another one but that's okay we've only seen two so far because this array is sorted all duplicates are going to be adjacent to each other just like the first variation of this problem but now we shift the right and left pointer again now over here we see the third one that's not good so what we're gonna do at this point is not shift the left pointer we're gonna leave it here what the left pointer tells us is that every value before this point is our array so far like this is our array so far with the duplicates removed we've seen these three values but we know this doesn't count so this is our array so far the first two values that's why we're going to leave the left pointer here and we also know that this is the spot next time we see a value we're going to push this over here and actually that was the spot the entire time when the left and right pointer started over here and we saw that this is not a duplicate so far what we would actually have done is taken the value at the right index and moved it to the left index now in this case it didn't really do anything because both of the pointers are over here so we didn't swap anything and here we didn't swap anything when the left and right pointers are here and over here when the left and right pointers are here we didn't swap anything but we just left the left pointer over here and now we're Shifting the right pointer over here now we see that we have a two value this is not a duplicate so we're going to push it to the index over here so we're going to overwrite the value here we're going to put 2 over here and now our left pointer from here is going to be shifted to be over here and our right pointer which was here is now going to be shifted by one again over here now this is kind of the problem with this approach and I'll show you how to fix it in just a second but now notice how there's four twos in our array so over here now we're going to say well this is only the second two we have seen so far but how are we actually going to determine that like how are we going to know if there are more than two copies of this value the easiest way to do it would be to compare this value to the previous value and the previous value before that which would tell us that this is the third two in a row so what we would say now is we're not going to take this value and move it to the left position we're actually just going to skip this value leaving our left pointer here and taking our right pointer now and incrementing it over here but do you kind of see the problem with this approach now we're going to get to this two do the same thing there are multiple copies of it consecutively so we skip this one and we move our right pointer over here to the 3 over here now we see this three does not have duplicates so we're going to move it to the position with our left pointer but we're going to end up over writing this guy we need two twos we're not allowed to have three of them consecutively but we can have a couple in a row but we're going to end up over writing this one so that's kind of a problem with this approach the solution is actually really really simple especially when we're going to look at the code but in terms of drawing it out the main thing is just that when we get to a value we're just going to count how many there are like we're gonna have a nested Loop which is going to bring our pointer over here our right pointer and I'm just going to keep counting how many of these twos there are and by the time we get to the end of it let's say our left pointer is still over here but by the time we get to the end of that streak we counted three twos so we only want two of them so what we do is take the first two and then shift them over by one we've moved this one into the left position so put the two over here and then take our left pointer and shift it by one over here then we take this two and put it in the left position and then we take our left pointer and once again shift it over here but we've already added two twos over here so now we're done then we take our right pointer increment it just by one because we're at the end of this streak now we want to get to this streak so just to clean this up a little bit right pointers over here and now we do the same thing here there's two of these we're gonna count them our right pointer is going to end over here yes we have two of them and we're going to start pushing both of these at the point where our left pointer starts so we would put the three here and then put another three over here and then our left pointer would be over here by the end of it so I'm gonna just draw that out our left pointer is here and at this point our right pointer would be incremented by one again now we're out of bounds so we would return this value if I didn't make it clear at the beginning all we're returning is this integer value K which in our case is going to be zero one two three four five six six is going to be what we're returning because there are six values in this array we're doing everything in place so we don't have to worry about additional data structures but as you can see this is definitely the correct array with no more than two copies of a single value and we did it in linear time even though we have nested Loops you can see the two pointers we had left and right both of them are going to iterate through the entire array at most once we're not you know doing it a variable number of times so the time complexity is going to be 2 times n which we know reduces to B Big O of n there's no extra memory that we're using so the memory complexity is constant so now let's code this up so I'm going to have a left and right pointer both initialized at the beginning of the array and then just like in the drawing I'm going to have a right pointer that will iterate through the entire length of the array and then we want to count how long the current streak is so what we're gonna do is first set the count equal to one because whatever number we're at right now at index R is going to be a new number and we want to compare it to the next value in the sequence so nums at index R plus one while this is true then we want to increment the right pointer and for convenience we'll increment the count as well having extra variable for the count makes things a bit easier but there's a couple catches with this what if R plus 1 isn't even in bounds well then we wouldn't be able to increment this so let's add a guard here while R plus 1 is less than the length of the array and this is true we're going to increment by one so now we have the count of this streak it could have two values in it it could have more than two values like three or four or it might even just have a single value it won't have less than that but it might have a single value we want to do at most two copies of this this value so what we do is take the minimum of 2 and the current count so if the count is greater than 2 we're only going to get two copies of it but if the count is one then we're only going to get one copy of it we're going to take the minimum of these two values and that's how many times we're going to iterate through this and for every iteration we're going to take the value at the right index and put it in the left position and don't forget to increment the left pointer every time we do that now regardless of how many times we do this we know the right pointer is going to end at the ending of the streak and we want to increment at least one more time to get to the beginning of the next streak on the next iteration of the outer loop after that's done we will have the left pointer will be in the position that we need to return for reasons that we talked about earlier so all we have to do is turn the left pointer now let's run this to make sure that it works and as you can see yes it does it's pretty efficient though leak code is random with the run times if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon