LeetCode 442. Find All Duplicates in an Array (Solution Explained)

hey what's up guys think white here I do Tecna coding stuff on twitch and YouTube check the description for all my information I do the Premium Lee code problem solutions on my patreon and if you want to reach out to me you can hit me up on discord I try to get back to everyone this problem is called find all duplicates in a ray got a lot of likes given an array of integers so we got you know rave integers looks like this may be where each element of the array is between the value 1 and length of the array inclusive some elements appear twice and others appear once so each element can either appear once or twice so each integer and the array can appear once or twice and each value in the array is between the value of 1 and the length of the array inclusive so there's nothing below 1 and there's nothing greater than the length so in this case the length is you know 1 2 3 4 5 6 7 8 so there's nothing 8 8 is the maximum number an element can be in the array and 1 is the minimum number so in each element can either appear once or twice so you could see four appears once 3 appears twice there's two threes 2 appears twice there's two twos 7 appears once 8 appears once 1 appears once ok find all the elements in the array that appear twice ok how would you do this with no extra space in linear runtime alright so that's a little bit of a challenge here so if you wanted to check there's a few ways to do this you know maybe if you didn't have the extra space constraint maybe you did like a hashmap just count how many will occur twice or just extra loops or something like that but doing it with no extra space and linear runtime is a little bit tricky and when we say no extra space people get confused if you whatever you're returning that doesn't count as space so we're gonna have an output array like list of integer because we have to return a list of integer there's no other way so we have to return some form of space and people are like hey dude that's not constant space it's like how would you return a list of integer without some space like you need to you need to do what the method returns you know so this doesn't count as space so we make a list of integer output array this is what we're gonna return but this doesn't count as extra space now to solve this problem in linear time with just this output array just putting what we need to output in for example 2 3 because there's two 2s and two threes and those are the only numbers with duplicates how are we gonna do this so this is a trick problem you guys might want to memorize this a little bit once you do it you'll remember it but it really is a prime example of when you really need of the reason why during a technical interview you have to pay attention to the instructions and if you read cracking the coding interview or you watch Gail Walkman with Alice videos on algorithms you'll understand that she explains every single part of a problem description is essential to understanding how to solve it every part is usually important they don't include things that don't matter Lee code might sometimes because they have like some kind of bad they have some bad problems I mean out of thousand over a thousand they're gonna have a few bad ones but generally in industry when you're getting a real technical interview they don't include stuff that doesn't matter so what matters most is this piece of detail here right and this you know this should kind of catch your eye because this is kind of a weird scenario you know this isn't usually it's usually like given a sorted array or given an array with you know numbers given an array with positive integers given an array with you know lowercase letters or something like that but it's not usually this specific you know this is very specific like between one why would not 0 and n like that's kind of you know it's a little bit peculiar so that's why it catches our eyes and to solve this problem here's the trick the trick is you want to loop through to do this in linear time we're gonna modify this input array and what we're going to do is we're and live through and make the index of what what you'll notice is the the value of each element can also be an index within the array they are all valid indexes well if you subtract one so if you subtract one from any value it's a valid index within this array so one minus one is zero that's a valid index eight minus one is seven that's a valid index everything in between those definitely valid indexes because those are the max and mins so you know in three minus one is two zero one two you can reference any index now here's how you do it when we loop through we're gonna reference the index of the current element value minus one so for example in for 4 minus 1 is 3 so we'd reference 0 1 2 3 we're gonna go to that index that the value references and we're gonna make it negative so here's the trick when you see a duplicate so when we see 3 we're gonna go to the value minus 1 to index to 0 1 to make this value negative and that's going to be negative 2 and when we see another 3 we're gonna check if the value at the index if the value minus 1 so index 2 that we changed if it's negative that means we already saw a 3 because the value if we see a duplicate value they're gonna reference the same index if you know 3 minus 1 is 2 0 1 2 makes this negative if we check 3 minus 1 is 2 0 1 2 if it's already negative then we already changed it and that means we saw 3 before so that's the whole idea here I also have traced this problem out so we'll go over it a little more in depth at the end if you don't understand but essentially you're making values negative and checking for negative values so your it's a linear loop through the array I 0 I less than um stop length I plus plus it's really a simple simple problem but the hard part is just the trick of under you know thinking of this and I think just doing this problem in having this in your mind if you ever see this is really helpful like tricks like these you know so we're gonna take the absolute value of the current number and then we're gonna subtract one and then we're gonna say okay if nums of index is less than zero if it's a negative value we're gonna add it to the output array so we're gonna say output array dot add index plus one which is the value and then what we're gonna do is we're gonna say nums of index is equal to negative numbers of index and this is the whole problem so let's submit this I'll show you that it works and then we can nums dot length always making mistakes here nomes dog whines boom there you go it's a working solution linear solution constant space because we don't count this output array now what what about what I want to do is paste this trace in here I traced the input example and what we're doing is we're gonna take the index this is the current value right we're looping through the array value but value we're gonna go four three two it's just a linear loop through every value we're gonna say okay index is equal to num shevai the value math.abs of numbers of i which is just a positive version of the value so four minus one to get the appropriate index to reference we're doing minus one because the numbers are from one to the length of the array and if you referenced nums of eight that's out of bounds because it only goes up to numbers of seven so we do minus one because every possible value can access an index so even one that the minimum value is 1 so 1 minus 1 is 0 that's a valid index the maximum value is 8 in this case 8 minus 1 is 7 that's a just the length minus 1 so that is a valid index as well we're gonna every loop we're gonna say ok nums of that current element minus ones index so for for example numbers of eyes for index is 4 minus 1 we calculate then index is 3 and we say okay is numbers of 3 less than 0 is number 3 lesson 0 0 1 2 3 7 less than zero no so we make 7 negative 7 and this is the next version of the array and we keep repeating this process ok we're on the next number 3 3 minus 1 is 2 nums of 2 is 2 0 1 2 2 is not less so we make it negative 2 and you keep going and what you'll notice like I said is that the if you see a duplicate it's gonna access the same index because the formula is exactly the same we're doing math dot abs and we're just doing the value minus 1 so 3 minus 1 here is gonna give us index 2 and 3 minus 1 when we see another 3 down here is gonna give us index 2 but when we do it here we change the 2 to a negative 2 and when we see it here we're going to be checking each time if it's already negative we found a duplicate so we just add this 3 into our output array so you keep going you know you're on you know you see numbers of I is 3 then you see numbers of I is negative 2 because we modified it but we do math dot ABS because we're gonna be making values negative that's why we use the math dot abs for the index so you're on negative 2 you to Matt 2 minus 1 is 1 0 1 you make the 3 negative 3 because it's not negative yet you can see negative 7 7 minus 1 is 6 numbers of 6 here 1 2 3 4 5 6 that 3 you make that negative 3 now because it wasn't negative now you do you're on what did we see negative 7 we're on 8 8 minus 1 is 7 we check index 7 it's a 1 that's not less than 0 you make it negative 1 now we're on two we have seen a 2 already and since we saw that two we're gonna be referencing the same index than when we saw it the other time so we're gonna say 2 minus 1 is 1 0 1 oh look it's a negative value so we're going to add this 2 into our output array and yeah I mean that's pretty much it that was just how it works let me know if you have any questions it is a little bit tricky to understand I think I had this backwards down here it's actually two and then two and then three sorry I accidentally put that backwards but yeah you just trace through the whole thing and then you the duplicates will go to the same index and the first time you go to a number you make that index a negative so the second time you go if it's already negative you just add the values to the the current value to the output array so that's it that's all you got to know for this it's a trick problem very tricky very you know I don't even know if I were to you got to sit and think about it for a while and you got to understand why why is this important and then once you figure that out you're good to go but it just you know sometimes it's not essential to understand every part of the problem but in this case it's like you know really important so just be alert if you can't solve a problem I would suggest really I think that's one of the tips that a lot of people give if you are having trouble solving something really read the instructions over again and try and find you know valuable information like this so that's it for this video thank you guys for watching let me know if you have any questions about this process I think it's pretty straightforward after I explained it yeah that's it so thanks you thank you guys for watching thank you I love you guys and I will see you in the next video alright see ya

Channel: Nick White

Views: 99,697

Rating: 4.9377871 out of 5

Keywords: leetcode, hacker rank, cracking the coding interview, coding, programming, computer science, technology, math, science, education, tutorial, how to, python, java, web development, software engineering, algorithms, data structures, interview, technical interview, coding questions, array duplicates, find all duplicates in an array, duplicates, array, arrays

Id: aMsSF1Il3IY

Length: 12min 36sec (756 seconds)

Published: Sun Sep 22 2019