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
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 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.
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.
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.
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
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.
@@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.
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 ?
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
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.
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?
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.
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.
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.
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?
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; }
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
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
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.
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).
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
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..?
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
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)?
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 only thing that doesn't make sense is why an element at a specific index will point to another index with the same value? for example: [1, 2, 3, 2]; how does index 3 know index 1 has the same value?
Index 1 will mark the value (in this case 2) to negative on its turn (loop i), so when the turn comes to index 3, the index 3 checking if index 1 is negative, if negative then the value (in this case 2) is duplicate
Let's say, we were asked to find the missing numbers instead of the duplicate. Can we use this approach to come up with a similar approach to solve that? If you know of this or have done this, could you post a video for that as well?
@@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).
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.
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?
code is great but you made a mistake in the explanation . On line 61 - output_arr=[3] ; which is wrong , its suppose to be 2. Why - because output = index + 1 (1+1=2) . same with line 69 as well .
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?
Nobody can think of it in an interview. This is a trick puzzle, where you have either seen it before (then it is "obvious") or haven't (then it would take a long time to think up).
