Floyd's cycle detection algorithm (Tortoise and hare) - Inside code

NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent

[insidecode]

🔴
/ \
🔵—🔴
| |
🔴—🔵

[shivamsoam]

That graphics requires a lot of work, TYSM👌👌

[SauravC]

After meeting the hare, the rabit also slows down. Important point

[lolreach]

Awesome explanation! I believe another valid approach is to call the number of nodes from the head/start of the linked list till the node before the loop "x", but simplify and call the total number of nodes the slow pointer traversed inside the loop before encountering the fast pointer as "d", counting repeated ellements, so:

total_distance_traversed_slow == x + d
total_distance_traversed_fast == 2 * (x + d)

When they encounter each other, it can be said the number of elements they traversed inside the loop, the "total distances minus x", are congruent modulo "loop_len" (the "loop" is analogous to a cyclic group of order/length "loop_len"):

total_distance_traversed_slow - x === total_distance_traversed_fast - x (mod loop_len)
d === x + 2 * d (mod loop_len)
d + x === 0 (mod loop_len)

Obviously, the element inside the loop that we end up on after traversing a distance of 0 inside the loop is the "head_loop" we want, which can also be reached if we traverse a distance congruent to 0, i.e., any multiple of "loop_len". Now, from simple modular arithmetic, if the slow and/or fast pointer were to traverse a distance of "x" more inside the loop, they would arrive at this "head_loop", since d + x === 0 (mod loop_len) (formally, "d", "2 * d + x", and "-x" belong to the congruence class of d modulo loop_len).

So, a brilliant idea is to put either one of them at the start of the linked list and let them both progress one element at a time: once the pointer that we put at the start reaches "head_loop", they'll both have traversed the distance "x", which is also where they'll encounter each other, thanks to our previous reasoning, so we can check for that ("while(slow != fast) ...") without even needing to know the value of "x" beforehand (we can also rename the variables to make it very clear what is going on, say "pointer_inside_loop" and "pointer_from_start")! :D

[vocipy]

Giving the mathematical explanation for getting the entry point of cycle was the best part !

[ggsingla]

This is the best explanation that I have found after discussing the same question with atleast 3 friends, they knew the approach but were not able to explain as clearly as this one

[jonasbrooker]

You have a talent for clear and concise explanations. Thank you so much for this.

[rajkishor]

I've read numerous articles on this, but the algorithms always seemed confusing. However, your video provided a clear and concise explanation. Thank you so much for making it easy to understand

[praptib]

Best channel I've come across for understanding algos clearly 💯

[niccolotoccane]

Your approach of explaining algorithms is perfect, thank you very much for your videos

[expansivegymnast]

Doesn't get much better than this. If you're trying to understand this problem, go ahead and start here.

[sreenithisridharan]

Great video with clear animations and explanations to about the internal logic behind the tortoise-hare algorithm, as well as how it can be used in the find the duplicate problem . Appreciate the effort

[youssefhussein]

This is the only video that I found, which explains why it specifically work in a reasonable way not just using slow and fast and make them met
Thanks!❤

[joshuazhao]

Dude this is by far the best explanation for this I have ever seen. Hats off to you sir

[falxie_]

Thank you for actually explaining how this works. I'm solving LeetCode 142 and I swear every video wouldn't actually explain *why* it works.

[anishbhandari]

In duplicate number 9th node should point to 2nd node not to 7th node

[_sky]

After watching 10 videos, this was what made my day. Thanks

[Skryzer]

A few questions..
..1st: Since fast enters the cycle earlier it's clear to me, why we need c1*l for the fast pointer. But slow will never make a lap before slow and fast meet, hence c2 is 0, isn't it?
..2nd: It's still not clear to me why we have to slow down fast for this to work. Doesn't slowing down fast break the whole equation we just formulated? Since c1 is the amount of laps fast did under the circumstances of fast being twice as fast as slow.

[HimanshuTheHR]

Think of the relative speed of 2 nodes, one has speed of 2 nodes and other has speed of 1 node . The relative speed is always 1, meaning the distance between the slow pointer and the fast pointer will always keep reducing to 1 node after they have entered the cycle. That means they will eventually meet and never jump over because at one point the distance is reducing by 1 and not 2 or more to jump over.

[Rishi-hehs]

You can alsow think in terms of relative velocity

From the point of view of slow pointer, fast pointer is moving 1 node ahead at a time

So if finally fast pointer reaches the slow one, then definitely there is a cycle

I think, using the similar approach if you move slow pointer n times forward and the fast one (n+1) times forward, that should also work