Why Floyd's Cycle Detection Algorithm Works | Cycle detection in Linked List

[@itsmeac101]

even after two years. this remains the best proof i could find. thank you!

[@KnowledgeCenter]

Glad to hear.

[@theawless]

Amazing! This is the most complete proof of the algorithm I've seen. I was tired looking at wikipedia and stack-overflow. Some people made the assumption that hare will make only one loop before reaching the meeting point, but no one explained why. It seems that's the wrong logic. In your proof you mentioned that hare and tortoise can both make some number of loops.

[@KnowledgeCenter]

Thanks. Glad it helped.

[@AndreiSokolov-k7j]

no it's wrong explanation, e.g why he thinks, that length of the loop it's 8? it's 7. and also tortoise can not do ANY number of loops

[@kaifk5889]

Sir the way you explained the problem was really amazing. Hoping to see more algorithm videos soon.

[@KnowledgeCenter]

Thanks. Check other playlists.

[@Vibedecoded]

Best explanation hands down !

[@abhijitdutta8458]

Great Explanation. Thank you!

[@svalyavasvalyava9867]

I'm so grateful for this explanation. Thanks a ton 😌

[@KnowledgeCenter]

Happy to help!

[@prabhupuredla8280]

the explanation is clean and precise. Thanks for the video

[@KnowledgeCenter]

Thanks.

[@rohith8269]

Such a great explanation!

[@takitazwarparthib3555]

GREAT EXPLANATION SIR! HELPED ALOT.. SPECIALLY THAT LAST EXPLANATION WAS EXCELLENT

[@KnowledgeCenter]

Thanks.

[@zaabimahdi]

this is the best ever explanation !

[@KnowledgeCenter]

Thanks.

[@boladjivinou7295]

Thanks a lot, this is the most logic explanation

[@KnowledgeCenter]

Glad you think so!

[@rohanprak]

thanks a lot for such a great explanation, this could not have been better.

[@KnowledgeCenter]

Thanks. Glad you learnt something useful from the video.

[@KS0607]

extremely lucid great thanks

[@KnowledgeCenter]

Thanks.

[@Amygdala57-c8c]

M = (s*C2-f*C1)*N/(f-s) - (f-s)*K So, if the slow pointer moves "s" step at a time, the first pointer will move (f-s) step to meer the beginning of the loop. Here, s=1, f=2. So slow moves 1 step and fast moves (f-s)=1 step at a time. Got it.

[@DeepakKumar-wh7bv]

Thank You Very Much Sir !. This video solved my doubt. Please Keep uploading videos on problems with mathematical base. Please make a "video series" on Time Complexity Finding (without using master theorem ) . I have subscribed your channel and waiting for another videos.

[@KnowledgeCenter]

Thanks Deepak. That's really encouraging. Will be creating more series on algorithms and problem solving soon.

[@tsaoliam5422]

Best explanation

[@kartikeydixit3743]

Very clear explanation . Thankyou so much

[@KnowledgeCenter]

Glad it was helpful!

[@trivialnonsense]

Excellent. Thank you

[@KnowledgeCenter]

Glad it was helpful!

[@diptiprakashsinha]

Nice explanation

[@KnowledgeCenter]

Thanks.

[@crisag.2698]

What I'm confused about is how the fast pointer could make more than 2 cycles around the loop before it meets the slow pointer. Intuitively, in my minds eye I see the fast pointer moving at 2x the speed, so I would think that the overlap would happen somewhere before the fast pointer begins its third cycle.

[@KnowledgeCenter]

That can depend on the size of the loop. Lets say There are 100 nodes before cycle, and 1st node of cycle is 101th node. The cycle has lets say 10 nodes. So, after time step 50, slow pointer will be at 50th node, fast pointer will be at 100th node and touching the beginning of Cycle. after 5 more time steps, fast pointer will complete 1 round of cycle, since it has just 10 nodes. Slow pointer will reach 55th node, still far from beginning of cycle. After next 5 time steps, fast pointer will complete another round of cycle, slow pointer will be at 60th node and still far from beginning of cycyle. At time step 101, slow pointer will enter Cycle. By that time fast pointer has already completed 10 rounds of cycle. Now, chase will start between rabbit and tortoise.

[@mehrabhasan5773]

Great explanation. Thanks a lot.

[@KnowledgeCenter]

Welcome

[@umangmalhotra1222]

very good explantion.

[@Its_Sunny-qe8ve]

In what case, the slow pointer will complete at least 1 loop because I am getting that in every case , fast pointer will catch slow one before the loop 1 complete. Can anyone provide example in which slow pointer completing at least 1 complete circle of loop

[@sunnykumarsingh7039]

Excatly bro!

[@prakulcool]

Well explained. Thank You Sir!

[@KnowledgeCenter]

Thanks.

[@manishvohra1953]

Awesome explanation

[@KnowledgeCenter]

Thanks.

[@happyhome422]

Thank you for nice explanation. 🙏upload more videos

[@urmanratneshwar]

thanks a lot for this explaination...

[@KnowledgeCenter]

Glad it was helpful!

[@joeys8832]

Thank you!

[@KnowledgeCenter]

Welcome!

[@shivam7304]

bro the explanation was on point but you need a media player to increase your speed though...

[@KnowledgeCenter]

Right. Speed has increased in later videos.

[@paragroy5359]

Nice explanation sir......

[@SpaceExplorer]

thank you sir

[@KnowledgeCenter]

Welcome.

[@MyJapaneseLife]

Hey @KnowledgeCenter, Should the symbol "=>" you draw in the video be ""? Also your video are a bit slow. I have to play it at 1.25x to save my time... Anyway thanks for the video, helped me understand the algorithm. Edit: This video deserves much more views and thumb ups because it explains the algorithm in mathematical way unlike many other videos.

[@KnowledgeCenter]

Thanks. My earlier videos were a bit slower as I was drawing using touch pad.. Newer videos are a bit faster. For older ones recommended speed is 1.25x at least.

[@chandrasharma1951]

Nice explanation. However I was searching for floyd cycle algorithm (behind the scene maths). And please speed up, I played it at 3x so that I don't get bored.

[@KnowledgeCenter]

In recent videos I have speeded up a bit.

[@chandrasharma1951]

​@@KnowledgeCenter Thank you. BTW I worked up on the maths, two pointers starting at position a and b inside loop with speed x and y respectively to meet at point t have to satisfy equation a + xt ≡ b + yt mod N, where N is loop length, but it shows that they will not meet if (x-y) is not co-prime with N. Please do add the explanation for this and whether I am wrong on this or right. Thanks in advance.

[@alifrahman7099]

Nice proof. ❤❤

[@tongl7380]

nice video! helps me a lot, thank you

[@KnowledgeCenter]

Great.

[@tareqmahmud7760]

nice, thanks

[@KnowledgeCenter]

Welcome 😊

[@bagasadifirdaus9278]

Sir can you tell me why the slow pointer is guaranteed not to go over the full loop before meeting the fast pointer?

[@udbhavvikramsingh3449]

same Q !!!! did you find the answer bro. if yes then share with us.

[@abhishekroy1028]

It is not guaranteed. If you watch the video, he mentioned 'in most cases' it'll be one.

[@payalsagar1808]

wow short and crisp!🙆

[@KnowledgeCenter]

Thank you 😋

[@kamaninikhil71]

I didnt get why we ignored numbers of loops as constant

[@nectarofcoding6233]

mujhe acha nhi lga

[@lambar0]

Nice explanation

[@KnowledgeCenter]

Thanks for liking