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

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[leonardbrkanac]

This is so simple yet it's so hard to see

[quibler]

The only video on the Internet that made me understood this Problem. Efforts are Appreciated 👏🏼

[arthurg]

Consider each element as a node with the value as a pointer to the index of the array
Then run a cycle detection algorithm.
Questions like this are so addictive and interesting, they fill excitement inside

[SB-btmm]

Hey Nick, that was a great technique and explanation. Do you have a git repo of all the Leetcode problems you've solved so far ?

[visheshmangla]

Maybe a fine enough explanation is that we needed some way to keep track that an element is visited. Whenever we hit an element, the indicator that an element has been visited is given by negating the value at its index like if you see a 4 you go to its index which is 4-1 and negate it but what if 4 is found again, you check that if you have already negated it and you can catch it to be a duplicate. But you have negated a value to demarcate "visited" which has spoiled the index therefore take absolute to get the correct index.

[JohnDlugosz]

In your solution, don't forget to put the input back the way it was. The caller is not expecting to have the input trashed when you call a function on it.
In C++, I would have the input declared `const` so you could not mutilate it in this manner. A tidy solution would be to use the _output_ array for scratchwork.

Resize the output to match the input. Scan the input and increment the output index based on the input number. Then scan the output and for every '2' you find, put that index at the front of the array. Resize the output to trim to the length of the results.

[ryzen]

Damn....this guy is a genius!!!! Though he looks lazy all the time!!

[iamnoob]

Brilliant, Never Thought of this.Thanks Nick, Keep making videos like this.

[halcyonhimanshu]

How do solutions like these come naturally? It’s very difficult to think in that direction unless I know the solution beforehand.

[rajeshseptember]

Hey Nick. Great solution, but what if the original array needs to remain un-mutated (not modified). In this solution, we are actually modifying the original array, isn't it ?

[peqghgk]

I think the biggest benefit of Leetcode is the conversation it can encourage. Yes, you can slug away and try to solve it, but to converse is to understand, and to prove understanding. This is surely its own benefit in the coding interview

[ShubhamKumar-fyfl]

I seriously Love your videos. You make explanation very clear. LOVE from India.❤

[JohnSmith-xfzu]

I was thinking of something else. If you use some clever swapping in addition to negatives, you can make sure you only list each duplicate once. With the current example, if there are five 2's, it will list it four times in the results.

Basically, loop over each index. For each index, while not duplicate or not in the correct index, continually swap the current number into it's correct index. If there is already the correct number in the correct index, then we have a duplicate, so flag the number in the correct index as negative. If already negative, then don't add it to the output list. In any of those cases, move to the next index, skipping indexes that already have the correct number. This algorithm would also be O(n) and only list each duplicate once.



I made a trace out of the example in the video, but replacing 8 with a 2 for an extra duplicate: [4, 3, 2, 7, 2, 2, 3, 1]

Using 1 based indexing for simplicity.
index: 1, output: []
[4, 3, 2, 7, 2, 2, 3, 1]
[7!, 3, 2, 4!, 2, 2, 3, 1] 4 detected. swaped index 1 and 4
[3!, 3, 2, 4, 2, 2, 7!, 1] 7 detected. swaped index 1 and 7
[2!, 3, 3!, 4, 2, 2, 7, 1] 3 detected. swaped index 1 and 3
[3!, 2!, 3, 4, 2, 2, 7, 1] 2 detected. swaped index 1 and 2
[3, 2, -3, 4, 2, 2, 7, 1] duplicate of 3 detected at index 1 and 3. Mark negative, add output, and continue.

index: 2, output: [3]
[3, 2, -3, 4, 2, 2, 7, 1] 2 is at correct index. Continue

index: 3, output: [3]
[3, 2, -3, 4, 2, 2, 7, 1] 3 is at correct index. Continue

index: 4, output: [3]
[3, 2, -3, 4, 2, 2, 7, 1] 4 is at correct index. Continue

index: 5, output: [3]
[3, 2, -3, 4, 2, 2, 7, 1]
[3, -2, -3, 4, 2, 2, 7, 1] duplicate of 2 detected at index 2 and 5. Mark negative, add output, and continue.

index: 6, output: [3, 2]
[3, -2, -3, 4, 2, 2, 7, 1] duplicate of 2 detected at index 2 and 6. Already marked negative, so continue.

index: 7, output: [3, 2]
[3, -2, -3, 4, 2, 2, 7, 1] 7 is at correct index. Continue

index: 8, output: [3, 2]
[3, -2, -3, 4, 2, 2, 7, 1]
[1!, -2, -3, 4, 2, 2, 7, 3!] 1 detected. swaped index 8 and 1
[1, -2, -3, 4, 2, 2, 7, 3] duplicate of 3 detected at index 8 and 3. Already marked negative, so continue.
Note: It doesn't matter that we already counted this 3 as a duplicate, since we are only counting duplicates once anyway.

And done. We have our output list, containing 2 and 3 exactly once, even though '2' had 2 duplicates.
Since every check moves a number to the correct index, we only need to do N swaps at most for the whole array. We also guarantee that all numbers to the left of the current index are either in the correct index or are duplicates. So this algorithm ends up being O(2n) at most if no duplicates and O(n) at best if all duplicates.

[BadriBlitz]

Well Explained Nick.The Tracing of the code is something that really helped.Very Helpful Video.

[djfedor]

Hey Nick, great video, thanks for sharing!

How much time do you spend usually on solving a problem by your own before you realize that you’re stuck and have to check discussions?

Is it worth to try harder and solve something on your own for another two days before going through discussions?

[MechanicalThoughts]

Genius solution. Thanks for the explanation before the code.

[iMagUdspEllr]

Record the fact that you have seen a value x by making the value y located at index x - 1 negative. If the value stored at an index is already negative, this means you have already seen that value and you can append current_index + 1 to your list of duplicates.

[dayvie]

How to solve a problem for natural numbers without zeros which never occurs.

[tundeadebanjo]

I solved this using two pointers to check where there is equal values. One counting from the left and the other counting from the right.

[damodaranm]

it took me like 40 mins to understand but worth the time