Does anybody understand how to solve this in linear O(n) time and constant O(1) storage? Question: Find duplicate element in an array of size n + 1 containing numbers only from 1, ..., n. (The duplicate number may repeat more than once.) Solution: https://youtu.be/pKO9UjSeLew TC: [redacted to prevent distraction]
How tf did u get into google 👀
Keep in mind what “work at Google” means for L3/L4. It means they got 3 leetcode questions correct. If they got 3 questions that they’ve seen before, or if they were otherwise lucky, it’s still an offer.
The hiring bar was lowered for me!
Iterate through the array and mark the idx of the number value as negative. Iterate again. If any index is non negative, you know you have duplicate. You could even catch it in one pass if you try to mark an already negative number as negative again.
Elegant solution. Will only work for even number of duplicates.
Why do you think that?
Swap every element with the first one, if it is the same as the element on the first position it means we have seen this number before
This is LC 287. Why not just look there?
Use bit manipulation to detect collisions
dupe = sum(arr) - (n^2+n) / 2 sum(arr) is O(n) time (n^2 + n)/2 is the sequence 1+2+3+4+...n just noticed you can have multiple duplicates so this doesn't work. my bad.
I think you can do selection sort. I saw this question in grokking coding
count sort
That uses linear space. Problem requires constant space
sorry meant cycle sort. would this not work as well