Minimum Increment to Make Array Unique - Leetcode 945 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve a problem minimum increment to make array unique suppose we're given an array like this one we want to make every single value in the array unique so we want to eliminate duplicates but we can only do that by taking an individual element for example we have two occurrences of this value so to remove duplicates we can only increment one of these so suppose I take this one and I increment it now to be two okay well we solved the problem there's only a single one now but it looks like we have three occurrences of the value two so this is going to be an interesting problem to solve I'm going to show you two ways one is going to involve sorting and that is going to be an N log n solution and I'm going to show you a second one which is kind of similar to Counting sort I guess it more or less is counting sort we're going to be implementing that but that pretty much solves the problem for us as well and that is going to be a bit more interesting in terms of time complexity it's going to be n plus whatever the max element in the input is and that's going to be a fun one to explain so let's start with the first one as you can see the problem isn't that we have to find the duplicates and then increment some values to eliminate duplicates but then we might end up with even more duplicates so let's try to do this in an organized way the reason I'm going to take the input and sort it as you can see we're running into a problem but sorting will fix that problem and I want to show you why that is so if I take the original input and sort it we're going to get something like this I want to do a two-pointer technique I want to compare adjacent values because given that we've sorted this now it's very easy to identify duplicate values because duplicates are going to be right next to each other okay now we found some these are the exact same value we're going to increment one of them I'm going to choose to increment the one on the right and the reason for that is going to become clear because when I take this one and now I increment it to two now when we shift we want to compare these two values so we want to be done with this one that's why I'm leaving it as is because the one that we increment now could potentially be the same as the next one that we're looking at now when we look at these two values I'm going to see that they're the same and I'm going to choose to increment the one on the right so now this one is going to be three but this is actually even more interesting because now when you look at the remaining values we have a three here we have a two here and we have another three here they're not all the same like now we ran into a situation where duplicate values are actually not adjacent to each other but that's okay because this actually is solvable for us because we kind of know that every value up until here is going to be in ascending order and we also know that the values here are in ascending order now it could have been a situation like this this is the simple situation imagine if these three remaining numbers were something like 7 8 9 we would look at these two values and we'd see okay this value is obviously greater than the value on the left that's fine I mean they're in sorted order we expect some of the values to be greater than the others so this is fine we would just skip this and then move to the next position and then just continue now the other situation might be what if all of these were threes well obviously when they're equal we got to increment one of them we're choosing to increment the one on the right now the other case is this the case that we currently have where actually this value is less than the value on the left this would only have occurred if we took this element and incremented it right so the fact that this element is larger than this one implies that this one was incremented in the past and the only only reason we would have incremented this one is if it had a duplicate with the value over there so the fact that this value here like our pointer is here is less than the value over here implies that this one is actually a duplicate of some value that we've already seen in the past therefore we're going to increment this value but as you can see we're not just going to increment it once we want it to be at least one greater than this value so what we're actually going to do is take this value to subtract the value on the left which is going to give us a Delta of one so actually I guess the better way to do it would be to take this value and subtract the value on the right because we're finding the difference between these two values that's going to give us a one so we're going to take this and add it to this so that they're the same so this will be a three but then we want to increment it one more after that so not just the difference between them but also a plus one so that this is actually different from the value to the left of it so this will end up being a four now we're going to do the same thing over here we're going to look at these two values they're not the same but this one is smaller than the one on the left therefore we take the difference between them that's one and add that here and then also add a plus one so this will be five now now we compare the last two and there's nothing for us to do this one is already greater than the value over here so if you were keeping track of how many times we had to increment so not just the number of times we increment but uh this one obviously was incremented once this one was incremented once this one was incremented twice and this one was incremented twice the total was six so this is just the Classic sorting solution for this problem n log n time so let's code it up I'm going to take the input and sort it in ascending order I'm going to have a variable to keep track of how many times we increment that's going to be my result and that's what I'm going to return and then I'm going to do the two-pointer technique but I'm actually not going to have two separate variables because we know the two pointers are always just going to be comparing adjacent values so let's do something like this for I in the range starting at one and the length of nums because I'm going to compare the value on the left which is IUS one with the value to the right which is at pointer I so remember if the value on the right is actually less than or equal to the value on the left that's when the a problem in that case we want to increment we want to update our result not just by one but also the difference between these two values if you're scared if you want to be defensive you can take the absolute value difference between them something like this but remember with this comparison if one of them is greater we know which one is going to be greater it's going to be this one so if we want to get rid of the absolute value let's take this value and subtract from it the other value and then we can get rid of this absolute value so this is just us updating the result like this is how many times we have to increment the value here so that it's different from the value to the left of it now what is that value going to be now that's the easier calculation we're now going to replace nums of I with the value to the left of it + one so I -1 + 1 and that's pretty much the entire solution I have technically one variable but it's obviously a two-pointer solution we're comparing to adjacent values so let me just run this as you can see it works and it's pretty efficient now let's look at the other one so we can apply this idea this concept of sorting and actually do something a bit more clever so the interesting thing about the solution I'm going to show you now is actually that it's a little bit easier to understand it might actually be more into for you consider us using a hashmap or you could consider like an array but the key is going to be the value on the left and here it's going to be the count of that particular value so initially we're just going to take this input array we're actually not going to have the sorted version so consider just the original but I have it drawn here just for readability so we're going to take every value and get the count of it so one has a count of two two has a count of two three has has a count of one and seven has a count of one so the idea now is same as before but we're going to do it sort of in groups in buckets or whatever you want to call it so we start at the smallest key but we might not necessarily know what that is so we know that the smallest value we could have I think in the input is the values are going to be somewhere in the range from zero to 10,000 or 100,000 something like that so we're going to do that that we're going to iterate over all the possible values here so starting at one we're going to look at the count okay the problem is the count is greater than one we have duplicates so what do we do well we're going to take that duplicate just the extra one so how many duplicates do we have well we have two elements we subtract one and then we have one extra element is what we're calling it we have one extra copy of this value so we're going to just move it to the next bucket in this case that's two the next group so this will be one now CU we don't want duplicates but we're going to move that duplicate here so there's actually going to be three copies of two now what did it take for us to do that it just took one operation because we only had one extra element so we just had to increment that extra element by one so now we have the value two and we have three copies of that value so we have two extra elements so we're going to take those two extra elements and move them to the next group they're going to be here now so I'm adding two to this group and I'm subtracting two from this group how many total operations did it take for us to move those two extras to the next group it took two however many extras we have That's How many operations it's going to take for us now once again we're here and we have extras we have two extras so we're going to move those two we're going to have one copy of three remaining and those two extras are actually not going to be moved to seven they're going to be moved to four so maybe I should have left more space here but hopefully you get the idea that four now originally it had zero we didn't have any fours but now we're going to have two of them we have two copies of the value four and I'm actually going to redraw this so we had zero fours now we're going to have two of them okay now we go to the next group how many extra fours do we have well it looks like we have one extra four so we only want one to be here so we're going to move that extra to be a five now so there's going to be one five and now we're going to go down here five actually doesn't have any extras like we have exactly one five that's good we don't want extras we only want at most a single one so this is good we don't have to do anything here and then we're going to go to six six actually there aren't any of those so that's fine as well we don't need to have a copy of every single element and then we're going to go to seven seven there's just a single one that's good as well nothing for us to do here at this point we're pretty much done how many operations did you count well we moved one copy of one here so that was a plus one we moved two of these to here and then we took two of these and moved them down here and then we took one of these and moved them here so if you add all those up we get six and that is the result now you might recognize that there is kind of an issue with how we do this in memory like when I originally said that the values in the input they are going to be somewhere in the range from zero to 100,000 so does that mean we could just iterate over all possible Keys here from0 to 100,000 actually no because consider this input like this is the max value in like the array that's the max possible value imagine we have let's say two copies of these or maybe even three copies of 100,000 that's the entire array we have three copies of 100,000 well what we're going to end up doing doing here is iterating from 0 to 100,000 we're going to see okay we have three copies of 100,000 right so 100K is going to be here we have three of them and then we're going to move two of them to the next one so 100K + 1 I know this is getting kind of messy but we're going to have two of them here now well if we only iterate from 0 to 100,000 we're going to miss the next one and then that one should technically go down to 100K + 2 so the concept here is that what whatever the max value happens to be we could have n duplicates of it where n is the size of the array so if we really want to go through every possible key what we should do is go from zero up until 100K plus n where n is the size of the array this way we won't miss anything and also if you want to be even more clever you recognize that we don't always have to use 100K we could just find whatever the max value in the input happens to be in this case it's seven and use that instead so technically we will iterate from n plus whatever the max value is so from zero up until n plus the max value in the input cuz that max value in this case seven maybe it showed up six times cuz that's the size of the array so in that case we would want to go from n which is 6 plus the max value which is 13 cu to eliminate duplicates from here we're going to need something like that right we're going to need this to be an eight this to be a 9 and then this to be a 10 11 12 so that's the math behind what I'm showing you it's kind of a minor optimization but this is the best way to do it and I know you guys like to see that solution there are many ways to code this up we could take like an array and call it count and then just use that to store the counts of every single element in Python though we can use something called a counter which is going to do exactly that except it's going to use like a hash map under the hook I could write out the you know few lines of code it takes to do this but all we're doing is just counting the occurrence of every element in the input I'm going to have a variable for result once again and that's what we're going to be returning but now to actually compute that we're going to go for I in range this is what I was talking about we're going to go from zero up until the length of nums plus the max value in Num so it's going to be this length plus Max now we don't have to specifically say we're starting at zero so I'm just going to get rid of this implicitly it'll start at zero anyway we're good here now if the count is greater than one that's when we have a problem so let's just check is the count of this greater than one okay it is that means we have some extras how many extras we'll take the count and subtract one we have this many extra so we're going to take those extras and move them to the next group we're going to go to count I + 1 and add those extra copies there now for us to do that it's going to take some operations some incrementing operations how many values are we going to increment this many and we're only going to increment each by one so this is what we're going to do we're going to take the result add to it extra whatever extra happens to be that's how many times we had to increment that's the entire code let's run it as you can see on the left it works it's technically less efficient and that's because in most cases when the input size is small this is actually going to be less efficient because the max number could be big even on a small input array so we're going to iterate unnecessarily so that's kind of how it usually is with counting sort but we've had a lot of counting sort problems lately so I wanted to show you this solution anyway if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon