Find All Duplicates in an Array - Leetcode 442 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so to Let's solve the problem find all duplicates in an array I want to quickly mention I haven't uploaded for the last several days like the daily Le code problem and that's because I had already solved those problems in the past and had already uploaded a video for them so in case in the future you don't see me upload a video it's probably because I already have one so we're given an integer array nums of length n and they give us an interesting guarantee that every single number in the input is going to be in the range from 1 to n where n is the size of the array so that's interesting why is that even relevant to the problem well let's continue reading every single integer in the input either appears exactly once or exactly twice so think about it already like let's say n is equal to four we're given an array of size four where we have four slots here it's possible every single number only appears once and the numbers have to be in that range so one possibility would be something like this 1 2 3 4 now they also say sometimes a number might appear twice so think of it like this 1 2 3 3 so in this example not every single number in that range is actually present in the input array so that's another observation to make all we want to do is return an array of all of the integers that appear twice if there even are any in the first place okay that's not too difficult I can think of two pretty easy solutions to do that but there is a constraint over here our solution has to run in linear time and constant space my two solutions don't satisfy that the two solutions though might help you arrive at the more optimal solution so let's quickly go through them the first is since we're only looking for duplicates right we can have kind of a two-pointer method we can do nested for Loops right so we can compare every single pair of elements so check this is a one is there any other one that shows up in the input array no okay this is a two is there any other two that shows up in the input right nope and here there's a three is there any other three that shows up yes there is so this is an N squared solution but it does work constant space that's the good thing it's constant space but not efficient enough the other solution is to detect duplicates in an array you can imagine a useful data structure would be a hash set so this way we iterate once over the input and we check okay one has one already been added to the hash set nope so let's add it to the hash set next check two is it already in the hash set if it is then we found the duplicate but right now it's not so let's go ahead and add it and next three it's not added yet so we add it and then three again oh finally we found it the duplicate is already present in the hashset therefore this is a duplicate so then in terms of our result which is an array we would go ahead and append three to that array and we reached the end of the input so this would be our result so the problem with this is that clearly the memory like even though we're iterating once which is probably what we want to do for the uh optimal solution we have extra space and what's the size of that extra space going to be o of n so that's a problem but but but think about this this is the problem solving aspect our hashset we need o of n extra space and coincidentally the input array is exactly size o of n here's where a little bit of intuition comes in from the fact that I've seen similar problems as this before if you remember any problems like this definitely mention them in the comments I think that will be helpful for people CU I don't remember them off the top of my head we need oent extra space is there any way we can kind of augment this solution instead of using the hashset can we use the input array as extra memory it's theoretically possible not only that but can we use this constraint that was given to us that doesn't really seem relevant to the rest of the problem can we use this constraint to arrive at the optimal solution yes we can because every number is guaranteed to be in the range uh in this example from 1 to 4 so what we can say is that for each number 1 2 3 4 if we have seen one we want a market visited how can we do that well we can map one to index zero we can map two to to index one 3 to index 2 and four to index 3 so now we have a one toone mapping with the input array as well as each possible number that could show up so now we have that how do we use that to our advantage because of course like if we try to overwrite values in the input array like for example if the first value here was a three and I want to say okay three is marked visited we know three maps to index two how do I mark it visited over here do I put some special character there cuz we don't want to overwrite the array if we are iterating over this array from left to right we don't want to overwrite this position so what do we do well we do something pretty clever instead of changing the value we just change the sign we preserve the value we mark this as negative so let me show you what I mean it'll make complete sense after I quickly run through it but I'm going to quickly change this example to make it more interesting now we actually have two duplicates in the input what we're going to do is iterate over this from left to right we see a three we want to somehow Mark that this three has been visited so we're going to go to our mapping we're going to go three maps to two and by the way this mapping is pretty simple like I'm not going to create a data structure for this because you can see that the pattern is that every value is just going to be decremented by one to get where that value would be marked as visited so for three if we want to mark Mark 3 as visited we will go to index 2 in the input array we're going to put a little negative sign over here now we're pretty much done with this position by the way so now we're going to move to the next value but knowing that values now in the input could be negative even though all values originally were positive what can we do well every time we look at a value we can take the absolute value of it just in case this time we don't need to it's positive three but just in case because next time it's going to be NE to we will need to take the absolute value in that case so we're going to always take the absolute value it doesn't hurt us to do that now once again I'm going to see three before I Market visited this time we're going to follow kind of the same idea we did with the hash set solution I see it's already been marked visited I can mark it visited again and I guess that's what I'll do in my solution it doesn't really matter but before I even do that I'm going to see it's already negative it's already been visited and this is the second time I'm seeing it so in our result let's go ahead and add three to the result okay great next position we're at this whether it's positive or negative it doesn't really matter we'll take the absolute value regardless we'll have a two we want to map this to index one right 2 - 1 is equal to 1 so that's where it's going to be mapped and now we're going to say this is positive so we haven't seen a two yet but now we have so let's go ahead and Mark it negative next value is two once again we're going to look over here it's already negative therefore we've seen a two before so let's go ahead and add it to the result so this is going to be the result for this example if you're still not convinced that the solution works I highly recommend you go through a few more examples you'll quickly find that it does for pretty much all possible edge cases so now I'm going to go ahead and code it up you can see that we iterated over at once that's o n time and since we're using the input memory as extra space it's technically con space uh extra at least okay let's code it up first I'm going to do declare the result and then we're going to return it it's going to be an array but before we return it we of course have to fill it in with all of the duplicate elements so what I'm going to do is iterate over every number in the input array we know that theoretically some of them could be negative so let's go ahead and just take the absolute value of it before we try to do anything fancy we want to Mark n as visited the way I'm doing that is by taking n and mapping it to some index uh in the input array not the result the input array we're doing that like this so for nums n will go at the index nus1 and to mark it visited mark it such that we've seen this before let's just in Python you can just kind of take the negative of it like this or in other languages I think you can multiply it by ne1 there we go but before we Market visited let's try to ask our elves has this already been visited how do we know if it's been visited if it's already negative so if nums of nus one is negative or even equal to zero well I guess it's not possible for it to be equal to zero so let's stick with the negative idea so if it's less than zero and that's because we're guaranteed that every value in the input is positive so making it negative will definitely make it less than zero if it's this then we've seen n before so let's go ahead and say result. append n there you go that's the solution let's run it to make sure that it works and as you can see on the left yes it does and it's pretty efficient if you're preparing for coding interviews check out ncode doio thanks for watching and I'll see you soon