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
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
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 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?
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?
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.
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
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.
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).
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.
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.
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
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?
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.
@@dailyinspirationwithmenaagina 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).
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; }
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?
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..?
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).
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?
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
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
Hey Nick. Where's your Discord link. I just got into high school. Did a bunch of LeetCode and Amazon has given me an offer. Thanks for your videos. I am going to be making more than both my parents combined.
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
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..!!
What it does has been said already so maybe I could add to the name. First of all, it used the Math namespace, which has functions assigned for mathematical operations. The abs stands for absolute, which has been explained by Tsoodol Tse already. (Sorry if that was too obvious. Just trying to clear things up for newcomers)
The only video on the Internet that made me understood this Problem. Efforts are Appreciated 👏🏼
This is so simple yet it's so hard to see
Yeahhh fr
Not for everyone tho
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.
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.
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
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 ?
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
Brilliant,Never Thought of this.Thanks Nick,Keep making videos like this.
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
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 ?
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 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.
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.
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.
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?
who is Gail Walman with Alice? Nick mentions it at 3:10.
Where can I find those videos?
gayle laakmann mcdowell
Genius solution. Thanks for the explanation before the code.
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.
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?
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
can this question be done with binary XOR operation?
What font is this ? Looks very pleasing.
How to solve a problem for natural numbers without zeros which never occurs.
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
What a amazing video 😲😲 please do more like that. It will help us to build our logics.
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.
Great Job! How did you generate this trace of the problem? Is there such option on leetcode?
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).
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.
What should be the approach if the array elements cannot be modified
I have no idea how this solution just came to u. Brilliant
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.
really brilliant solution. Sounded like Floyd's tortoise and hare algorithm but pretty simple to understand.
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.
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.
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?
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
How would we solve this if the maximum integer in the array is greater than the size of the array
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?
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?
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.
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
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.
Does sorting the array count as extra space?
Yes o(n) space
@@dailyinspirationwithmenaagina 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
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;
}
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?
good solution, original array was correct [3,2] however
This should be done in-place to avoid extra memory allocation
It is done in place.
man how do u got all these knowledge . where have you learned all these things
Same exact question
How do you find duplicate pairs and trips of numbers within an 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..?
sorting would take an extra time complexity..!!
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).
Thats brilliant one. This made my day
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?
mark the numbers -ve once (if they are already marked leave them), Then return the list like return [id+1 for id, num in enumerate(nums) if num > 0]
Line 7 should be in Else, also for correctness there should be another final loop making all negative elements positive at the end
Thanks to people like you I will have a degree
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
You need to return the input array. "What else am I supposed to return?". It is the input array, here you create additional space.
This is a brilliant solution Nick!
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
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
@@denifelixe why does index 3 check index 1? how does index 3 know index 1 has the same value?
Because index 3 has value 2 and the formula is value-1, so 1
Why we do minus 1? Because if we have integer 4, we dont have index 4 since it out of bounds
This solution can be applied for the specifically to this the problem only..!!
Hashmap and loop.
For loop with two pointers.
ArrayList list = new ArrayList();
Arrays.sort(nums);
for(int i=0;i
sorting is not O(n) anymore
@@MinhTran-jg2bx Yep that is true, n(log(n)) now.
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
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
you are super genius bro!
Wow. That was awesome. Liked and subscribed 🙂
Hey Nick. Where's your Discord link. I just got into high school. Did a bunch of LeetCode and Amazon has given me an offer. Thanks for your videos. I am going to be making more than both my parents combined.
great explination in the end
noob here, where is the main function and which part of the code stores the input array ?
I am still stuck at the question, whats linear solution and extra space?
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
what would be the solution if the array is immutable
use hash map
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
Thanks brilliant, big ups Nick!
why not using HashMap?
because it takes extra space 🤷♂
Genius!
Please, keep going solving more
2:15 is the greatest lifehack ever
this code not working for [1,1] ?
what if the element is greater than the size of the array..?
U use Floyd’s Hare and Toritoise algorithm ?
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😂
great explanation
Excuse me, can someone explain to me what extra space is?
Extra space in memory.
@@brandonkirincich8181 i see, the extra space by creating a new instance of arraylist?
@@thatonedude4926 Yes. Whatever space you require to store the another array or variable other than output array.
HOw to paste the trace
what happens if number is repeated thrice?
We can use Set to include this kind of test case also
Great explanation bro
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..!!
great explanation.
Thanks a lot.
Awesome video!!
Why am I not clever enough lmao
Just negate the element corresponding to the element seen the first time. If the position is negative you seen it twice.
Nick White: "It's easy, guys. Just pay 5 bucks to get 'Solution' and code this shit"
nums = "----->-->"; k =3
result = "-->----->";
reverse "----->-->" we can get "
nice explanation
thats bloody clever...awesome
What is Math.abs ?
it converts negative number to positive one. For instance, Math.abs(-1) is 1.
What it does has been said already so maybe I could add to the name.
First of all, it used the Math namespace, which has functions assigned for mathematical operations.
The abs stands for absolute, which has been explained by Tsoodol Tse already.
(Sorry if that was too obvious. Just trying to clear things up for newcomers)