Why Floyd's cycle detection algorithm works? Detecting loop in a linked list.

[@bharaniakella7734]

This guy should be a youtube celebrity! People like him who share knowledge should be made famous.

[@jackzhu6482]

can't agree more, very well explanation!

[@kingdey9136]

he is a celebrity already

[@sarvodaykumar2723]

Must be

[@Photon7908]

I guess one minor point that I couldn't find in his video is this: (m+k) = integer*l -> this means, if you have p at the kth node and q at the start, by the time q travels m+k nodes from the start, p will finish one complete revolution on that loop. i.e., p and q will coincide at the kth node again. But if q only travels m nodes, p has travelled only (integer*l)- k nodes as well. So if p started at the kth node, and q at the start, they will meet at the start of the loop. (I hope this makes sense as it does in my head lol) Thanks for the video Vivek!

[@vaibhavrbs]

``But if q only travels m nodes, p has travelled only (integer*l)- k nodes as well. So if p started at the kth node, and q at the start, they will meet at the start of the loop.`` can you explain this part again please, this is not clear to me,

[@untwaddle]

@@vaibhavrbs p has already made k steps from the start of loop so to reach the start point again, it should travel (int * l) - k. it equals that q will make only m steps to reach the start point. other words, we had equation: m + k = int * l and then we subtract k from both sides. equation is still correct, now q will make m steps to reach the start point and at this place it will meet p. (p made (int*l)-k steps)

[@sadmansakib007]

You are absolutely right. Something was missing in that video but THAT"s the main point!

[@mhp3bozis]

Honestly think THIS should be the main focus, thanks for pointing out

[@kaustavgalacticos]

You missed one minor key point as well, ASSUMING q is equal to p after q starts from 0 and p starts from k, and *your rest of the logic*.

[@pankaj_2024]

worth spending 24 minutes , good work.

[@ashwanigupta5412]

Hi Vivekanand sir, can't thank you enough for making this video. I have seen almost half a dozen videos on this online and after this I can understand the logic behind it fully. Worth spending 24 minutes. Kudos to you!

[@robb1931]

Finally, there's a video that helps me understand this algorithm. Thanks a lot!

[@rehaanredkar1489]

this man is unbelievable , the way he explains is just mind blowing

[@leolin5479]

You really save me from struggling with the textbooks and any other recourses I could find, thanks !

[@KM-star]

OMG! This is the 1st video I am watching of this person and I am in love with his way of explaining things! I hope the rest of his videos are equally good. I can now recollect some friend recommending this person's videos. @Vivekanand ...You definitely have a fan base!

[@Dontpushyour_luck]

best video. I never understood this algorithm's proof properly but this was an excellent explanation

[@da_sci3839]

1. Best explanation I've found to describe this! No other explanation made sense. 2. I love the way you say "loop" XD.

[@algorithmimplementer415]

I am convinced that I understood the explanation. Thank you!

[@intechshala5929]

kyaa bataya hain aaapne jo koi na samgha saka aapne samgha diya bohot sahi

[@___vandanagupta___]

your teaching style is amazing ! i dont know why u dont have million subs

[@danielstatler954]

after a couple rewinds, i finally got it. i doubt i could ever come up with this algorithm on my own. good vid

[@jeezz4128]

I didn't see such a clr explanation ever .... keep going sir

[@ananyaarya2465]

Thank you so much

[@saravanansarangan7035]

I got same confusion after seen the solution on leetcode. How they meet eachother at the beginning of the cycle but now it is clear. Thanks Viveka you are great...

[@kirthanasingh635]

Your Explanation is amazing Sir!! Keep making videos

[@ngc35ster]

Thanks man, this is way more clear than the leetcode answer

[@mariammohamed176]

Thanks, it is the best explanation I have seen so far

[@caio-jl6qw]

WOW, very very VERY good explanations, thank u for these videos !!!!!!!!!!!!

[@kbhoyi]

OMG - Such a beautiful explanation! I'm listening to Vivek Sir's video first time. I'm sure, I'm in for a treat when I will search for other videos of his teaching. Stay blessed Sir.

[@rohitkumarvarma4952]

Thanks, mann! Finally understood this concept clearly!

[@ankitvishnoi8670]

I really enjoy your videos and your videos are helping a lot of people as we. I recommended your channel to many of my colleague and college friends. Keep up the good work. ;)

[@amitvaghela1456]

Great simplified explanations.

[@aterribleyoutuber9039]

Thanks a lot! I was struggling to understand this at first!

[@chrisdanan2183]

Wonderful explanation - thank you very much.

[@denys_kovpaka]

I like the way you explained this. Thank you a lot)

[@SoumikNandi]

One Point to mention.!! Rather than saying that Distance of P traveled would be Double the Distance of Q because "P's speed is twice than that of Q" kind of makes it incorrect statement. What we can explain is Let's say they start their journey at time T = 0. Now when they meet the time elapsed would be equal (Why? Because the time frame is absolute. Doesn't matter how they move they will meet only when they are in the same position at the SAME TIME) So, we know S = D/T (Speed = Distance/Time which also means T = D/S), from the equation we can say Tp (Time taken for P to reach the meeting point) = Tq ( Time taken for Q to reach the meeting point) or (m + pl + k)/2 = (m+ql+k)/1 Now work up to get, ---> (m+k) = l * (p-2q) NOTE: Another thing worth noting is that (2q-p) is also an integer but it'll never take the form of (2q-p) (Why? Because the left-hand side has a dimension of length (scalar) and hence cannot be negative).. Now, why is that (2q-p) is likely to be negative? Because P's speed is greater than Q. So its likely that P would travel the loop more number of times than Q will Hence, p > q/2 --> (Why q/2 ? follows from the above discussion) Or, (p - 2q) > 0 but (q-2p) < 0 It was just a suggestion!. The explanation is wonderful. It's just a part where I felt needed a little bit more clarification

[@shashankmehul02]

Such wonderful explanation.Very helpful.

[@lokeshjaliminche]

Good to see you after a long time! Great work. Good going!! :)

[@remmargorpp]

Bestest explaination ever!

[@liangchen8238]

Best explanation I've seen so far!

[@tushargarg3765]

Thanks for such a Nice Explanation.

[@konstantinrebrov675]

Indian professors are awesome!

[@anubhavsinha8048]

Very nice explanation!

[@akki4u]

Your explanation is so good that makes learning easy. Great work my friend!

[@jaibhambri6853]

Very Nice Explanation

[@omkar.at.office]

Awesome explanation! Thanks 🙏

[@KhanSlayer]

Very clear and concise explanation. Nice work.

[@secretman1787]

Excellent explanation !!!

[@columbiars]

Wow, excellent explanation dude! I was trying to figure out why this algorithm worked, and finally I found the right answer. Keep going this videos!

[@moghalsalwar6803]

I feel bore even for 10mins video ..but I didn't feel bore this tym when I am seeing this particular video...Thank U Sir

[@mp0157]

This is the best video dealing with Floyd's Cycle Detection Algorithm out there! Vivekanand, hats off to you for making this explanation so simple and straightforward! Thank you :)

[@robertr6054]

Just a minor point. When you’re doing the difference step you can just look at (m+k)=L*P. 2q will always be 0, as for any sized loop q will never be able to complete a full rotation before p catches up to it. P will also never be able to skip over Q in a loop. You can look at the most favorable example, if q enter the loop as p has just skipped over it. Before q will be able to traverse the rest of the loop to make a full rotation p will already have done so and be equal to q.

[@learningpool5918]

This man is gold. But I like watching it at 1.75x speed

[@ashishdukare1313]

Awesome explanation Sir : )

[@ayushsakure6098]

Very well explained.

[@loba8924]

Thanks. Nice explanation

[@arpitamandal6469]

thanks for explaining it so well..

[@jamesclark1207]

Really excellent explanation - thank you

[@mahipalsingh-yo4jt]

very well explained thank you..............................

[@isaacc9487]

This is very clear and detailed, thanks a lot.

[@karanb2067]

heroic explanation

[@mangeshgupta5677]

Great explaination thank you

[@blackswordsman9745]

Your videos are really helpful. Thanks a lot for making them :)

[@DurgaShiva7574]

you are seriously amazing bro...i love your knowledge and teaching way, keep up the good work..

[@shubhamjadhav2656]

very well explanation!

[@adityasingh11156]

Thanks Sir You make it understand in very simple way

[@devtorch]

I am on my knees and have tears in my eyes :)

[@jamietherooster]

You are very good, I am english but find your videos far clearer than any native english speaker's video's. How do you gain the knowledge of these algorithms ? do you have a book ? I purchased 'introduction to algorithms' but find it very technical and hard to understand.

[@sharansrivatsa210]

Honestly, I think its just going through this book called CLRS and preparing by just looking at more and more problems and how to solve them If you go to leetcode.com and start solving I'm sure you will start to get an intuition Also, these are algorithms that are used and proved. Its a lot about just learning these. geeksforgeeks is a good resource too.

[@rahulchudasama9363]

Nice explanation ...

[@mahesh23343]

Boy is son of mother. Mother is mother of boy. Man is husband of mother. Mother is wife of man. You can go to Delhi from Punjab. You can also go to Punjab from Delhi!! This video could be easily completed 5-6 minutes earlier if he wasn't repeating everything so many times! But got the concept clear, so thanks. But please try to be a little faster than this. God bless youtube developers for creating speed control.

[@blasttrash]

install video speed controller extension. it allows you to go beyond 2x speed.

[@mahesh23343]

@@blasttrash noted.

[@davidtheprogrammer]

Thanks so much. I wish we could derive floyd's cycle algorithm instead of assuming it's correct and making the assumptions from there.

[@vedvish3916]

Really awesome explanations,thank you.........,If possible please makes a playlist on stacks and queue.

[@vivekanandkhyade]

Sure.

[@kishantiwari3221]

Thank You sir!

[@codestorywithMIK]

Let us suppose the length of the list which does not contain the loop be s, length of the loop be t and the ratio of fast_pointer_speed to slow_pointer_speed be k. Let the two pointers meet at a distance j from the start of the loop. So, the distance slow pointer travels = s + j. Distance the fast pointer travels = s + j + m * t (where m is the number of times the fast pointer has completed the loop). But, the fast pointer would also have traveled a distance k * (s + j) (k times the distance of the slow pointer). Therefore, we get k * (s + j) = s + j + m * t. s + j = (m / k-1)t. Hence, from the above equation, length the slow pointer travels is an integer multiple of the loop length. For greatest efficiency , (m / k-1) = 1 (the slow pointer shouldn't have traveled the loop more than once.) therefore , m = k - 1 => k = m + 1 Since m is the no.of times the fast pointer has completed the loop , m >= 1 . For greatest efficiency , m = 1. therefore k = 2. if we take a value of k > 2 , more the distance the two pointers would have to travel.

[@bittuxoxo]

sir yur vvideos are the best..i really get to understand how yu teach good one sir .i will be hoping for a recursion video explain it in depth

[@null-wp1le]

Thank you so much for this video.

[@najimahmed8923]

#suggession: Complexity analysis would make the series complete. Please do another video to do complexity analysis!!! Great analysis! Thanks much!

[@truthprevails899]

Thanks for the explanation!

[@chakrapanisudarshan3027]

Brilliant Explanation in simple words.....

[@vivekanandkhyade]

Thanks Chakrapani.!

[@asgheralishaik]

nice explannation.Thanks

[@AMARSINGH-lj4rd]

great explanation , thanks you saved me viveka !!! :-)

[@ShwetaNaganath]

Thank you. i was struggling with this since long.

[@krisnadiputra93]

This guy has just saved me from a sleepless night lol

[@ankitvarmait]

Thank you for wonderful explanation

[@azam148]

Very clear explanation!

[@yys3082]

Now, I know how it works. Thanks

[@elizkotadia9350]

Great Job !!! Crystal clear explanation !!

[@kbhargavi4400]

thank you, sir, you explained such a confusing concept very well! :)

[@neeraj33negi]

Thanks, this is very detailed.

[@glassanddiaphane]

This is awesome, this really helped me to finally understand it, thank you.

[@ShivamKendre-fc3su]

What a explanation!!!

[@anandkulkarni2111]

doing good job!! excellent work keep them coming !!!

[@vivekanandkhyade]

Thanks Anand..!

[@apiltamang2767]

props for setting up the video. I think it'd help your videos tremendously if you prepared your speech in advance on the idea you're talking about, and especially so for a convolved topic like this, rather than just give an impromptu performance. I think that would help the video be more concise, and perhaps even better explained. Regardless, first time learning this material and I think I understand it just fine. So you must have done it right, albeit with some effort :)

[@yuhaodai5795]

Nice explanation!

[@gugliamo]

this was great, thank you!

[@chienhsiang-hung]

you deserve more subs

[@surendrapandey4660]

This video doesn't show up in top searches of the topic. It makes me think youtube algo is not working properly

[@dragosc8202]

Thanks! YOU make my day

[@pratiknaik261]

Thanks sir ek no!!💯💯

[@abhishekshrm100]

very nice explanation

[@farabikurmanshady8486]

Clear explanation! Thanks!

[@aynurmukhambetova1708]

it finally became clear! thanks a lot!

[@pratikghorpade6853]

Thank you sir ..... Great explanation ....

[@mohan-ri6ze]

Understood well

[@LogEekumanAgination]

That was beautiful and made me happy thank you so much

[@praveenchouhan6388]

awesome work thanks a lot!!!!!!!!!!!

[@NarendraKolink]

really helpful... Thanks a lot