Find the Duplicate Number - Floyd's Cycle Detection - Leetcode 287 - Python

What if we have a value equal to the index? Edit: nvm

Glad I'm not the only one that thought this problem was absurd! Thank you for the explanation! 🙂

plot twist the expected solution was O(n2) with two loops

im just confused as to why we are treating the array as a linked list? shouldnt we get an index out of bounds? why are the pointers looping?

edit: okay now i understand that the pointers are non-linear, but im still having trouble understanding the problem at all since this is an array not a linked list

You can solve this with binary search using pidgeonhole principle with solution found on leetcode from vanAmsen:
I think its possible to come up with this but still difficult, time complexity is also worse at nlogn

class Solution:
def findDuplicate(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1

while l < r:
m = l + (r-l)//2

count = 0
for num in nums:
if num <= m:
count += 1
if count > m:
r = m
else:
l = m + 1
return l

Hi @NeetCode, thanks a lot for making amazing videos.

The explanation is very clear here but I am not fully convinced by the idea that "fast pointer is at least 1 cycle faster then the slow one" so that we can write the fast distance as p + C - x + "1"C.

So I tried another approach:
I use the same setting as yours, so we have "p" previous nodes, and a cycle of "C" nodes and we assume the two nodes met at point "C - x" from the start of the cycle. So there are p + C = L nodes in total.
We know that the fast pointer is faster than the slow ones and have run more cycles in the loop. So I think we can say:
Fast pointer: d_f = p + mC + C - x
Slow pointer: d_s = p + nC + C - x

and m > n.

Now, if the fast pointer is k times faster than the slow ones, we have:
d_f = kd_s
p + (m + 1)C - x = k(p + (n + 1)C - x)

rearranging, gives:
p = x + [((m + 1) - k(n + 1))/(k - 1)]C

Now, we want to find the start of the cycle isn't it, but we do not know where it is and what we know are the start of the "linked list" and the meeting point only, so can we relate the distance between the start point to the start of the cycle, and the meeting point to the start of the cycle based on the fact that we have a cycle? If [((m + 1) - k(n + 1))/(k - 1)] is an integer, we can try to take mod(C) on both side, and that will give us an identity. If we have a very big cycle (C >= p), then we will have:
p = x

If we have a very small cycle (C < p), we can first express p in terms of the cycle size by p = y + rC, where y < C and r > 0, then taking mod on both side gives:
y = x

If we add rC back to both sides, then we will get:
p = x + rC

Looking the above, that actually means the distance of "p" actually equals the distance between the meeting point to the cycle starting point "x" (plus an arbitrary numbers of cycle if we have a very small cycle), which means we can move p steps the meeting point to find the start of the cycle.

This is why we can move one pointer back to the start point and then move both points at the same time until they meet to find the start of the cycle.

By the way, since I am using an arbitrary number "k" for the magnitude in speed differences, looks like Floyd's algo also works if the fast pointer is more than 2 times faster than the slow ones.

WOW, really loved that proof. Never studied this in uni thanks for your help

Can't you just add the numbers up and determine the difference between the sequence of the sum(1 to N) = n*(n+1)/2 and the sum of the array?

ie
Duplicate = sum(array) - n*(n+1)/2

this is such a bullshit problem

The fast pointer is not guarranteed to loop twice
if p is really long and c is short, it will loop more than 2
so the distance fast pointer travelled becomes P + nC - X, at which im lost

github?

There's an another way you can do it in O(n) time and O(1) space which is more intuitive
This was my approach
for(int i=0;i<nums.size();i++)
{
int index = abs(nums[i]);
if(nums[index]<0)
{
return index;
}
nums[index] = -nums[index];
}

Thank you very much, its a nice explanation. Thanks again for all the efforts you put into it.

That's right. Even Floyd wouldn't have resolved this problem in 30 minutes. It goes on to say that given the nature of such requirements in an interview, certain solutions are best memorized so that you could use them in a different situation or if the same problem comes up again.

A slightly better implementation.😊

def findDuplicate(self, nums: List[int]) -> int:
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break

slow2 = 0
while slow != slow2:
slow = nums[slow]
slow2 = nums[slow2]

return slow

I will cry if I got this question in intervew

I like the fact that you disliked this problem

You're right, I don't know why would anyone ask this question, nobody will know it unless they have super memory and saw it already and this doesn't let you learn anything about the interviewee.

Indexes are nodes and values in those indexes are next pointers ( to indexes). That how it is linked list

In example through logic once we reached to the 3

in first while loop we reached 3 so why can't we directly return nums[3]

which is answer 2.

Please answer anybody.

Thk from Egypt ❤

I really love u thk for all u do bro

I believe there's a slight inaccuracy in the drawing explanation node diagram. I think it should be 0 -> 1 -> 3 -> 2 -> 4 -> 2. (Basically, what I mean is node 1 is omitted).

Thank you so much for the wonderful explanation! Really liked it

Beautiful Explanation

Thank You for this video

Amazing explanation as always. Thank you so very much !!!

Ah yes the "trivial" cycle linked list for a seemingly easy problem, this is why I suck so badly at LC style interview :(

Currently the problem has aroung 20 K likes. People really love this problem

you know its a beautiful algorithm when the code for it is so simple

Actually this problem an be solved by using binary search when applying the pigeonhole principle. But your solution is also really interesting. Thanks for your helpful explanation !!

great explanation

sum of array - n*(n+1)/2

could we calculate the sum of elements then subtract sum 1-n from it.
in current example it fill 12-10=2

All this time I read the solutions on LeetCode and could not wrap my head around it. Then I read ALL INTEGERS IN THE RANGE (1-N) and I still could not understand how it worked.

Can be done this way? (taking a vector of 1e5 making it constant space right?)
class Solution {
public:
int findDuplicate(vector<int>& nums) {
vector<int> a(1e5+2,0);
for(auto t: nums)
{if(a[t])
return t;
a[t]++;}
return 0;
}
};

It should be plus nC there.

Why is the beginning node 0 and not 1?

You are really talanted in explaning complicated things, even I got it) Thank you <3

Help: do the numbers 0->3->-2->4-> ... represent the index or value of index? cause if it represents the value of each index, i thought it would be this
1->3>2>4>2->4-. and if it represents the index, i thought that it would be like this: 0->1->3>2>4>2->4-.

I think this problem could be solved by binary search too.
Here is my code:
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();

int lo = 1;
int hi = n - 1;

while (lo < hi) {
int mid = lo + (hi - lo) / 2;

int count = 0;
for (int i = 0; i < n; i++) {
if (nums[i] <= mid) {
count++;
}
}

if (count > mid) {
hi = mid;
}
else {
lo = mid + 1;
}
}

return lo;

}
};

This problem amazed me

so good, much appreciate for your effort

head node as 0 is correct but the node after it should be 1 not 3

I don't understand why p must equal x. If there is a linked list of 10 elements where each element points only to the next element (1->2->3->4...), and only the 10th element points to the 9th element, then the meeting point must be inside the loop at either the 9th or the 10th element and the start of the loop is at 9. The distance between the meeting point and the beginning of the loop is now either 1 or 0 and the distance from the beginning of the loop to the head of the list is 8 which is not equal to 0 or 1. Where am I going wrong?

understood

How can making a sum of array - sum of set of array returns the duplicate