LeetCode 442. Find All Duplicates in an Array (Solution Explained)
ฝัง
- เผยแพร่เมื่อ 21 ก.ย. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - วิทยาศาสตร์และเทคโนโลยี
![[LIVE] : ONE ลุมพินี 71 วันนี้!! คู่เอก "ทรงชัยน้อย vs รักษ์"](http://i.ytimg.com/vi/_AGPnq2p6Js/mqdefault.jpg)
This is so simple yet it's so hard to see
Yeahhh fr
Not for everyone tho
The only video on the Internet that made me understood this Problem. Efforts are Appreciated 👏🏼
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
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.
If there was a solution that modified the method parameter (mums) itself and returned that, is that considered to be less space that declaring a separate vector variable as done here and returning that? Or is it the same?
Brilliant,Never Thought of this.Thanks Nick,Keep making videos like this.
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 ?
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 ?
Will the technique works for array contains negative numbers as well? say one of the duplicates is a negtive number. According to the logic, it doesn't seem to work.However the test run printed out has negative number array
Great Job! How did you generate this trace of the problem? Is there such option on leetcode?
Genius solution. Thanks for the explanation before the code.
I seriously Love your videos. You make explanation very clear. LOVE from India.❤
Well Explained Nick.The Tracing of the code is something that really helped.Very Helpful Video.
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
You have a coding fetish lolol
Appreciate your peculiar way of thinking, BUT... if we wanted to return ANY(only one) of the duplicate numbers then your approach would work. However, we are told to return EVERY duplicate number.
for example - nums = [4,3,2,7,8,2,3,1]
You might end up in infinite loop because you'd need some base condition to stop. But, according to your explanation you would calculate first duplicate number (say 3) and again do the same thing where you might again calculate the previous duplicate number(i.e. 3). If let's say on the second time you calculate different duplicate number (i.e 2), on the third iteration you'll again calculate 2 or 3 because there is no way for you to know how many duplicates numbers are there.
Correct me if I'm wrong.
@@saurabhdeshpande8450 cycle detection in graph implies using visited list, and it's not O(1) space solution, though it would work
@@saurabhdeshpande8450 ik I'm two years late, but, I was trying to apply floyd tortoise algorithm - which OP mentioned - the whole day and I found out eventually exactly what you said, you can't find a base condition (base case) to stop, so you can't apply it many times to find multiple duplicates(considering that you pop the duplicates each time you find one, so you won't be stuck in an infinite loop), if you wanted to iterate or to do it recursively you would need a base condition/case. which makes applying the algorithm hard/impossible with constant space.
P.S. sry if my writing is too messy. hope I delivered my idea correctly.
Hey, Someone help
if anyone is reading the comments and is good at this, (i know this would be a worse solution but it is one I managed to come up with quickly and wanted to check) would it work to just, run through the input array, and for each number seen, add onto the output array in the number's index (minus 1) the length + 1, and then, when finding a duplicate and checking the index minus one, if there was already a number there then it would be replaced with the duplicate. at the end, all cells equal to length + 1 would be removed. return.
any feedback?
What a amazing video 😲😲 please do more like that. It will help us to build our logics.
But what if the numbers were bigger than the arrays length? You'd have to assume each number in the array an access an index. Would you not?
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.
cheeky solution but it may not please the interviewer
the input gets passed as a parameter to the stack, meaning that it gets destroyed after the function ends,even if it is modified inside it. This happens in C,at least. In other languages,like python,js,php etc, it doesn't because arrays bevahe as pass by reference. You can easily overcome it though by passing a copy of the array as a parameter
@ghost mall actually i was kinda wrong in my comment. In all languages, everything that gets passed as an argument to the function, gets copied in the stack and is destroyed when the function terminates. In C's case, suppose you have an array and you pass it as an argument to the function. Passing it to the function, is like passing the address of the first element of the array(&array[0]). If you modify this pointer inside the function(say for example you make it point to a different address), this change will not depict in the main. If,however, you change the element the pointer refers to( *(arr+0) = 100 ), the change will depict in the main. So, it is a pass by value as far as the pointer is concerned, but a pass by reference as far as the values of the pointers(array) are concerned. The safest way,is to create a copy of the array(in C's case) or the list( in python's case(l=l[:]) ) before passing it to a function,even if it is void. It's the same with Java, when you pass an object to a method, if you change it's member variables,the changes will affect the caller even though the copy of the object will get destroyed after the method ends
@ghost mall can I pair program with you
really brilliant solution. Sounded like Floyd's tortoise and hare algorithm but pretty simple to understand.
How to solve a problem for natural numbers without zeros which never occurs.
can this question be done with binary XOR operation?
What should be the approach if the array elements cannot be modified
How would we solve this if the maximum integer in the array is greater than the size of the array
How do you find duplicate pairs and trips of numbers within an array?
What font is this ? Looks very pleasing.
I tried something but don't know if its a correct solution or not. The function below checks for any given count of occurance:
vector FindOccur(vector arr, int occur) {
vector ele;
Int l=0, r=0, arr_size=arr.size(), curr_occur=0;
While(l=arr_size) {
If(curr_occur == occur) {
ele.push_back(arr[l]);
}
l++; r=l; curr_occur=0;
}
If(arr[l] == arr[r]) {
curr_occur++;
}
r++;
}
return ele;
}
How do solutions like these come naturally? It’s very difficult to think in that direction unless I know the solution beforehand.
It's about practice and watching lots of clever solutions like this. You have to extract every little clue from the problem statement. For example the fact that the numbers are between 1 and the length of the array points to the direction that the solution perhaps has something to do with indices of the array, as subtracting 1 from any value in the array will give you a valid index. Also they ask you to do it in no extra space. That leads to the belief that maybe the given array has to be mutated. The solution still does not follow naturally but with some thought you could maybe get an idea of how it might be solved.
This is what I had in mind.
@@sangramjitchakraborty7845 yes exactly! it boils down to just SEEING, OBSERVING, many tricks - then when i encounter similar problem - i loop through all of my 'clever tricks' stored in my mind and find something similar.
Welcome to the stupid world of tech interviews. You need to know how to reverse a binary tree for a job where you're going to change csv's manually. Programming is made more unnecesary difficult with all the bullshit at tech interviews.
@@Auzep Do u think this is to filter the competition ?
Thank you so much @Nick White Your video is very much helpful for me.
What if it's an unsigned int that we cannot use nums[i] = -nums[i]? We can't do nums[i] = nums[i]+n because of the possible overflow at n >= 2^31
Perhaps you can ask your interviewer if you can make assumptions about the maximum size of the input array. An array with 2^31 elements would be enormous. I suppose if you do need to consider arrays of that size, this method wouldn't work.
if i could do it with a list or an array max size n i can basically allocate and array of n, go through the input array and update indexes with the counter with the amount of times i saw the number. then i can just go through the array and print the indexes with count greater than 1.
noob here, where is the main function and which part of the code stores the input array ?
This is a brilliant solution Nick!
Finally! I was able to solve one and then came here to look how that you did it. This is how I solved it:
function findDuplicates(nums: number[]): number[] {
let result = nums.reduce((prev, current) => {
if (prev[1].find(n => n === current)) {
prev[2].push(current);
} else {
prev[1].push(current);
}
return prev;
}, { 1: [], 2: []})
return result[2];
};
Runtime: 2024 ms, faster than 16.67% of TypeScript online submissions for Find All Duplicates in an Array.
Memory Usage: 47 MB, less than 100.00% of TypeScript online submissions for Find All Duplicates in an Array.
Then made it much faster, but still 16.67% hmm
function findDuplicates(nums: number[]): number[] {
let result = nums.reduce((prev, current) => {
if (prev[1][current]) {
prev[2].push(current);
} else {
prev[1][current] = true;
}
return prev;
}, { 1: {}, 2: []})
return result[2];
};
Runtime: 144 ms, faster than 16.67% of TypeScript online submissions for Find All Duplicates in an Array.
Memory Usage: 47.6 MB, less than 100.00% of TypeScript online submissions for Find All Duplicates in an Array.
I didn't get what he said at 3:09 who's videos?
Thats brilliant one. This made my day
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.
Damn....this guy is a genius!!!! Though he looks lazy all the time!!
😆😆
Hahahaha I do not know if this is a good comment or a bad comment
Actually this is kinda like floyd's tortoise and hare cycle problem..But yeah, dudes amazing
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?
Stanislav Fedosov 2 days dude haha nooo not even 2 hours
If I’m not coming up with a for sure optimal solution in an hour then I’m checking discussion
@@NickWhite thanks, i was in dilemma too.
Is there a way to do this in O(n) without having duplicates in the output array, whenever the number of duplicates of any number in the original array is even (Excluding 2)?
I guess you can use a HashSet and then convert it to an ArrayList at the end, but then it wouldn't be constant space anymore.
There'd be no point with such a modification since this specific scenario limits duplicates to 2 occurrences. If it were any number of occourences though,You could remove line 6 and then have a second loop outside of the first add only the negative numbers to the output array.
It becomes O(2n), but that just simplifies down to O(n).
The main idea is :
Since the array contains integers ranging from 1 to n (where n is the size of the array), we can use the values of the elements as indices. This allows us to associate each element with a specific position in the array. So if a position is referenced more than once it indicates that there is a duplication.
I am still stuck at the question, whats linear solution and extra space?
Genius!
Please, keep going solving more
Awesome nick but what if there is multiple duplicates(like 4) in these output arr also contains duplicates for this solution right???
as given in this question - it will have numbers occurring either once or twice.
Line 7 should be in Else, also for correctness there should be another final loop making all negative elements positive at the end
good solution, original array was correct [3,2] however
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.
Only if you had read the question properly, you would not have overthought. It clearly states a value can appear at most twice.
great explination in the end
What if input array is read only???
this code not working for [1,1] ?
Hi Nick,
How can we approach the same problem without modifying the array in 0(N) time and 0(1) space?
use Unordered_map !
@@GouravSingh thats not O(1) space.
who is Gail Walman with Alice? Nick mentions it at 3:10.
Where can I find those videos?
gayle laakmann mcdowell
I paused before the video started.. using javascript, I'd loop through the array: for each element, i'd subtract the ith element to all the other elements and look for zeros. If exactly 2 zeros are found, then that's one of the pairs. The operation takes (n-1)! time to complete, so approximately O(n!). Now to watch the video to see how to do it within time complexity of O(n).
What if any array element value minus 1 is bigger than length of array ?
Am I missing anything?
The problem statement has the condition that 1
Hi thanks for this video! I also solved this problem but I did not use an extra list, I just modified the original list and then returned it. To count the elements that were repeated I substracted N to the position represented by the value, so then if value + 2*n is lower than N then I found a repeated element.
Are you sure that using an output list is accepted as no extra space? Considering a solution that only uses the original list is also possible.
Hey Duilio what do you mean by 'subtracting N', so I assume N is the largest element in this case is 8. In this example the first element is 4, assuming that you mean the position representing by 4 is the 4th element which is 7, you subtract 8 from 7 -> 7 - 8 = -1, then when traversing you add back 8 if you are -9 + 2*8 = 7 < 8 therefore there is a repeat?
@@rajivnarayan5214 thanks for replying, yeah that's what I mean
I assume you only do the subtraction once right? If that is the case then isn't your solution exactly the same as the video's?
you are super genius bro!
Great explanation bro
I initially though of replacing the duplicates with 0 and realized I needed to remember the numbers... the only way to preserve the numbers while tracking duplicates is to negate them in O(1) space ...clever
HOw to paste the trace
Thanks brilliant, big ups Nick!
Hashmap and loop.
For loop with two pointers.
great explanation
Wow. That was awesome. Liked and subscribed 🙂
Who is the person that he mentioned about her videos in the beginning of the video 3:05 ?
Gayle Laakmann McDowell. She is the author of Cracking the coding interview.
how can we solve for list which has both negative and positive integers...? -n1 ≤ a[i] ≤ n2
vinay yelleti use abs to sort it out
What about array of booleans. Will check true if it is coming twice otherwise false by default. I think this is simpler than negative values
how would you compare?
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.
i did the same thing , his solution is pretty tricky
Initially i thought hashmap or frequency array would be good but then the array length could be as long as say 1000 and numbers could be like [1, 99, 999 ...] so hashmap is not good for given space complexity
Hey Nick this can also be done in a single line if count method is allowed I believe, otherwise another algo may be if we sort the given list and then fire a single loop and check the next element and if two are equal than we can enter it in new array if that element is not there in new array...and boom we get an array of all repeated elements in a simple elementary logic..🙌.what do u think..?
sorting would take an extra time complexity..!!
Thanks to people like you I will have a degree
I have no idea how this solution just came to u. Brilliant
it took me like 40 mins to understand but worth the time
Took me the first try to understand. I dont even know java script i just know C. Its pretty fun.
Thanks a lot.
great explanation.
Can we use the hashset for this scenario? What will be the difference... Love your videos ❤️
Hashset occupies space..and we are required to solve it in O(1) space complexity
if you use hashset in interview you will pass because it's a gotcha problem
thats bloody clever...awesome
You are using array lists to store the duplicate values. Array lists have access comlexity O(1) but adding items is very expensive because the underlying array has to be extended. Linked lists however have O(1) adding complexity. And since you don’t access specific indices in the output array it would make it faster to use a LinkedList for the output array
GaebRush the question gives us to fix the given method already
Or you can just allocate new list with nums.length/2 initial capacity
Awesome video!!
nice explanation
How come you couldn't just cycle through it and test if array element is equal to one of the ones in the array?
Aight, I may be completely wrong, and hey if I am someone can correct me, but since we have N elements in the array, then let's say we have a completely 'reversed' ( think 123....N/2N/2....321) sorted array in that we have 1 at the start at the array and 1 at the end of the array, then we have 2 at the 2nd position and 2 at the 2nd to last position and 3...3 ...N/2...N/2 you get the idea, SO if we look only at 1 we have to go through the entire array until we see our 'matching' number and we do that over and over again so since we start 1 we have to search all the way until the end then for 2 all the way to the size-1 3 size-2 so on so forth. If we use a little bit of calc or something along those lines (think Taylor series or something along those lines) it converges to around O(N^2) I believe?
man how do u got all these knowledge . where have you learned all these things
Same exact question
You need to return the input array. "What else am I supposed to return?". It is the input array, here you create additional space.
what if the element is greater than the size of the array..?
U use Floyd’s Hare and Toritoise algorithm ?
what happens if number is repeated thrice?
We can use Set to include this kind of test case also
We should definitely allocate output_arr list with initial capacity of nums.Length/2 to avoid excessive reallocation (log(n) of them)
you would need ceiling of length/2
Just negate the element corresponding to the element seen the first time. If the position is negative you seen it twice.
The problem is the short time to think and build the solution, these online tests were made to be copied from the internet. Which is a good skill too
what would be the solution if the array is immutable
use hash map
Thanks
Does sorting the array count as extra space?
Yes o(n) space
@@menaagina7242 sorting doesn't always allocate extra space. Most casual sorting algorithms alter the set itself and don't allocate new.
Though the main reason not to sort beforehand is that your time complexity goes up to like O(n log n) or worse, and the goal was O(n).
Nah library sorting algorithms will pretty much always be done in-place
O(n'2) .length is consuming n times each call -- you should have assigned it!??
.length is constant time
@@williambillemeyling5647 yep my bad, I blame c😂
bro i aspire to be this good at leetcode
What other array problems can be solved using this trick
Hey Nick is your real name also Nick White ?
I got this exact question asked in my coding interview
which company?
@@unknownman1 Accolite
What if the index 3 have the value 4
It won't work the algo is suitable by looking into the pattern as [4,3,2,7,8,2,3,1] so you can clearly see that index from left and right that is 3 from left and 3 from right 2 from left and 2 from right. I think you got the point..!!
I solved it by putting each value of its index, then checking if there were any duplication on index.
Brilliant
Damn! that was clever af.
Awesome 👏👌👌👌
why are making the num[index] = -num[index] again
means -3 -> +3
why again making it positive
we are never making it positive again because the total of each number can be at most 2
if we come across a duplicate, we just check if the value of the index is negative