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

Explanation of the Floyd's Loop Detection Algorithm in a Linked List having cycle.
Watch my Courses for Free on Skilshare:
C++11 Move Semantics & rvalue reference: skl.sh/2Jpff2o
C++ Smart Pointers: skl.sh/2JqIlym
Type casting in C++: skl.sh/2G2wh5h
C++ Pointers: skl.sh/2LHW6eB
Discrete Maths: skl.sh/2G3Xbtw
Reinforcement Learning: skl.sh/2XQxEhx
***** Books For Data Structures & Algorithms for Interviews:**********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
**************************************************************************
Support me on Patreon: / knowledgecenter
#Floyd's #Algorithm #Loop

[@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.

[@user-ib3ev5pl2t]

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.

[@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.

[@takitazwarparthib3555]

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

[@KnowledgeCenter]

Thanks.

[@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.

[@prakulcool]

Well explained. Thank You Sir!

[@KnowledgeCenter]

Thanks.

[@rohith8269]

Such a great explanation!

[@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.

[@tongl7380]

nice video! helps me a lot, thank you

[@KnowledgeCenter]

Great.

[@happyhome422]

Thank you for nice explanation. 🙏upload more videos

[@KS0607]

extremely lucid
great
thanks

[@KnowledgeCenter]

Thanks.

[@lambar0]

Nice explanation

[@KnowledgeCenter]

Thanks for liking

[@zaabimahdi]

this is the best ever explanation !

[@KnowledgeCenter]

Thanks.

[@tsaoliam5422]

Best explanation

[@kartikeydixit3743]

Very clear explanation . Thankyou so much

[@KnowledgeCenter]

Glad it was helpful!

[@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!

[@mehrabhasan5773]

Great explanation. Thanks a lot.

[@KnowledgeCenter]

Welcome

[@Vibedecoded]

Best explanation hands down !

[@trivialnonsense]

Excellent. Thank you

[@KnowledgeCenter]

Glad it was helpful!

[@manishvohra1953]

Awesome explanation

[@KnowledgeCenter]

Thanks.

[@umangmalhotra1222]

very good explantion.

[@boladjivinou7295]

Thanks a lot, this is the most logic explanation

[@KnowledgeCenter]

Glad you think so!

[@joeys8832]

Thank you!

[@KnowledgeCenter]

Welcome!

[@urmanratneshwar]

thanks a lot for this explaination...

[@KnowledgeCenter]

Glad it was helpful!

[@user-sw3qg3cr6t]

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.

[@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.

[@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.

[@paragroy5359]

Nice explanation sir......

[@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.

[@SpaceExplorer]

thank you sir

[@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.

[@tareqmahmud7760]

nice, thanks

[@KnowledgeCenter]

Welcome 😊

[@alifrahman7099]

Nice proof. ❤❤

[@payalsagar1808]

wow short and crisp!🙆

[@KnowledgeCenter]

Thank you 😋

[@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.

[@kamaninikhil71]

I didnt get why we ignored numbers of loops as constant

[@nectarofcoding6233]

mujhe acha nhi lga

[@diptiprakashsinha]

Nice explanation

[@KnowledgeCenter]

Thanks.