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

Discover the new graph theory algorithms course: inscod.com/graphalgo 🔴 / \ 🔵-🔴 | | 🔴-🔵

That graphics requires a lot of work, TYSM👌👌

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

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

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

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

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

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

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

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

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

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

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!❤

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

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.

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

Brilliantly clear and visual explanation! Thank you very much!

Your hard work really reflects in this video!!! Highly appreciate your talent, thanks a bunch for sharing it

This is the best explanation of why the second part of the algorithm works. I was confused why that was being assumed. It's a great trick to add to the mental toolbox! However, if processing is the bottleneck, hash tables may be preferred. This way the list is only scanned n times at most.

Amazing illustration to understand the solution

Well Explained

these animations are bomb! Great job!

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

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.

Amazing stuff. Helped me really understand the algorithm. Though I hope the rest of your videos are a bit clearer in audio.

Good explanation for the mathematical proof, Thank you.

This is literally the best explanation I came across while searching.. thanks a lot man

Excellent explanation. Thank you so much for the video.

Floyd you genius

Thank you, this helped me further my understanding of how this works

Again, interesting and super clear, thanks!

thx bro, your video is extremly beautiful and clean, excellent!!

The math formula is straightforward but still, i'm like HOW DOES THEY JUST MEET when we do that starting point reset!

Well explained! Thanks!

Great animation...very easy to understand....Thanks

This is fantastic, thank you!!

Awesome content! It's truly helpful to learn more about algorithms! :) Thank you for your contribution!

Finaly , what a great explanation , great job

This deserves more views!

Gold mine video was just lit❤‍🔥

Great explanation. I solved using the first way. But I got a better one . Thanks 👍☺️

I think, In the end code slow and fast should point to arr[0] instead of just 0

Thanks a lot , great explanation!

wowww, I wonder what went into initially developing this algorithm

This is where you know that math can solve anything without any issue

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

really helpful visualization! thank you.

This is amazing ! I can’t believe the details you put into this :o Also I think off an easier algo called cycle sort if we were to solve the find duplicate algo. I think that if the question was represented as a linked list then theres more merit to us rabbit vs turtle algo here. Thoughts ?

Great animation!

Great visuals and a very interesting algorithm. Subbed! But I want to join these asking about "x = ( c1 - 2c2 - 1) l + l - y" equation. I understand that (-1 * l) and +l will cancel each other out, so we're just using properties of math in here. But how one comes up with this idea? Is this just something that you learn to intuit?

absolutely genius.

Thank you!

i finally get it. thank you!

thank you so much for making such videos

great explanation man!

Best content.. thanks. New subscriber now

This is the best explanation I've seen so far! But why is it implied that the fast pointer will always make c₃l loops before we slow it down? You showed that this is correct for yet another example of a linked list but isn't it the same as trying to prove a generalized case by proving more specific ones? I mean that two examples does not prove it yet. Probably one can find a really big loop with a really small tail. Will it still hold up? I guess yes, but why? And why do we even bother ourselves with slowing down the fast pointer? Couldn't it make it to the start of the loop with the previous step size (which is equal to 2 nodes at a time). I mean there's nothing in the formula that tells us to use a certain step size and c₃l + z distance can be passed with the same pace as well. Or not? To me c₃ is just some constant value which we introduced to replace the longer one: c₁ - 2c₂ -1

Absolutely incredible 😍

very helpful . thankyou

The degree of explanation is amazing!! but i have a couple of questions: 1 How did you decide to re-arrange the values in a linked list like this? why is 6(4) second for example and not 3? 2. .head isnt a method part of the list datatype though. What is llist here? When i do [1,3,4,4,5 ].head -- this is invalid. Would love if someone can explain! Thanks x

This is so helpful

ure a freaking god man

Thanks for video buddy.... :)

brilliant stuff sir

Amazing! Thank you!!

Amazing explanation!

Can someone explain to me how " x = (c_1 - 2c_2)l - y" became "x = (c_1 - 2c_2 - 1)l + l - y"? Where did " - 1)l + l" were derived from?

Thanks, man. This is incredible. My question is, what if one of the elements of the array was large, say, 200, but we know that this index doesn't exist because maybe n = 5. Now, let's say fast = 200; then array[ array[fast] ] = will be array[ array[200] ], which index is not present in the array. How is it dealing with this cause it works but I don't understand why

i lazy to comment (but i click like btn), but you are best in explanation, hat off.

very clear thanks you are number one, you are special from others

Thanks

Why does fast and slower pointer eventually meets up in the cycle, I understand they traverse at different paces, but is there no situations where the fast pointer somehow always misses the slow pointer?

Dude you are good!💯🔥

keep up the good work

C1, C2, C3 all are integers

@7:03 isn't it like this? slow traverses c3l+z and fast traverses x?

Awesome animations!

Great video! **just curious** which country are you from? I've never heard this accent before

Really great video sir. Was trying to understand the proof for a while, and the more read material on it, the more I got confused. So tried to watch many other videos, they helped a little but not fully, but after watching your video, it came intuitively to me. Thanks a lot. Amazing way of teaching.

Thank you so much

any mathematical proof , why it works?

how can I use the floyd's algo to search for hashes collisions ? Thanks for your help !

Can anyone explain how traversing and saving nodes in a set will identify cycle in a link list when there are multiple nodes with same value in linklist with out having any cycle? 00:40

THANK YOUUUUUUUU!!!!!!!!!!!!!!!!!

masterpiece

Amazing. Just amazing! How do you do these animations?

7:13 why you move the fast pointer only one step there?

My brain is enthusiastically rejecting this whole idea 😞 I shall have to revisit this video next time I need to find a loop

Thanks!!

genius

if we take fast = arr[arr[slow]] instead of the fast = arr[arr[fast]]; if is way more faster

this is a math proof, i was expecting a more conceptual/intiuitive explanation before the proof.

5:48 x,=(c1-2c2-1)l+l-y pls explain this step

I don't really understand this approach 8:55

🔥🔥🔥🔥🔥

Can someone explain 5:35? I do not understand how he got -1 and +l

what is happening here , x = ( c1 - 2c2 - 1) l + l - y ?

Change your title to leetcode 287, I came here to understand that question.

gg bro

If u math videos you’ll get more views I bet