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

Рет қаралды 113,258

Vivekanand Khyade - Algorithm Every Day

7 жыл бұрын

Why Floyd's cycle detection algorithm works? Detecting loop in a linked list. You have to check whether there is a cycle in a linked list and find out the starting node of the cycle or the loop. You can also find out the length of the loop. Also known as Tortoise and Hare algorithm.
Detect loop in linked list :- • Detect loop in linked ...

Пікірлер: 256

@bharaniakella7734 7 жыл бұрын

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

@jackzhu6482 4 жыл бұрын

can't agree more, very well explanation!

@kingdey9136 4 жыл бұрын

he is a celebrity already

@sarvodaykumar2723 3 жыл бұрын

Must be

@Photon7908 6 жыл бұрын

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 5 жыл бұрын

``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 5 жыл бұрын

@@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 4 жыл бұрын

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

@mhp3bozis 4 жыл бұрын

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

@kaustavgalacticos 4 жыл бұрын

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*.

@KM-star 5 жыл бұрын

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!

@ankitvishnoi8670 5 жыл бұрын

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. ;)

@ashwanigupta5412 3 жыл бұрын

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!

@lokeshjaliminche 4 жыл бұрын

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

@PankajSaini-pi9ko 6 жыл бұрын

worth spending 24 minutes , good work.

@akki4u 5 жыл бұрын

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

@columbiars 6 жыл бұрын

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!

@blackswordsman9745 6 жыл бұрын

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

@leolin5479 4 жыл бұрын

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

@robb1931 4 жыл бұрын

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

@ananyaarya2465 3 жыл бұрын

Thank you so much

@danielstatler954 Жыл бұрын

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

@kbhoyi 2 жыл бұрын

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.

@ShwetaNaganath 6 жыл бұрын

Thank you. i was struggling with this since long.

@anandkulkarni2111 7 жыл бұрын

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

@vivekanandkhyade 7 жыл бұрын

Thanks Anand..!

@DurgaShiva7574 4 жыл бұрын

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

@reyou7 5 жыл бұрын

Wow man this was just amazing, thanks a ton!

@glassanddiaphane 4 жыл бұрын

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

@elizkotadia9350 7 жыл бұрын

Great Job !!! Crystal clear explanation !!

@denys_kovpaka 2 жыл бұрын

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

@omkar.at.office Жыл бұрын

Awesome explanation! Thanks 🙏

@anubhavsinha8048 4 жыл бұрын

Very nice explanation!

@secretman1787 3 жыл бұрын

Excellent explanation !!!

@ankitvarmait 6 жыл бұрын

Thank you for wonderful explanation

@algorithmimplementer415 3 жыл бұрын

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

@DeepakGupta-pl6bc 2 жыл бұрын

Excellent explanation!

@LogEekumanAgination 5 жыл бұрын

That was beautiful and made me happy thank you so much

@iam_kundan 6 жыл бұрын

Excellent video !!

@chrisdanan2183 2 жыл бұрын

Wonderful explanation - thank you very much.

@tushargarg3765 3 жыл бұрын

Thanks for such a Nice Explanation.

@ayushsakure6098 Жыл бұрын

Very well explained.

@jamietherooster 7 жыл бұрын

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 5 жыл бұрын

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.

@___vandanagupta___ 3 жыл бұрын

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

@gugliamo 2 жыл бұрын

this was great, thank you!

@rehaanredkar1489 3 жыл бұрын

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

@saravanansarangan7035 4 жыл бұрын

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

@loba8924 2 жыл бұрын

Thanks. Nice explanation

@azam148 5 жыл бұрын

Very clear explanation!

@aterribleyoutuber9039 2 жыл бұрын

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

@shubhamjadhav2656 4 жыл бұрын

very well explanation!

@jaibhambri6853 3 жыл бұрын

Very Nice Explanation

@NarendraKolink 5 жыл бұрын

really helpful... Thanks a lot

@kirthanasingh635 3 жыл бұрын

Your Explanation is amazing Sir!! Keep making videos

@mangeshgupta5677 4 жыл бұрын

Great explaination thank you

@isaacc9487 3 жыл бұрын

This is very clear and detailed, thanks a lot.

@mariammohamed176 2 жыл бұрын

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

@farabikurmanshady8486 5 жыл бұрын

Clear explanation! Thanks!

@caio-jl6qw 3 жыл бұрын

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

@jamesclark1207 4 жыл бұрын

Really excellent explanation - thank you

@ashishdukare1313 3 жыл бұрын

Awesome explanation Sir : )

@amitvaghela1456 3 жыл бұрын

Great simplified explanations.

@arpitamandal6469 3 жыл бұрын

thanks for explaining it so well..

@shashankmehul02 4 жыл бұрын

Such wonderful explanation.Very helpful.

@pratikghorpade6853 6 жыл бұрын

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

@varungunda2177 7 жыл бұрын

Thank you very much Sir.. It was very helpful :)

@mahipalsingh-yo4jt 3 жыл бұрын

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

@truthprevails899 4 жыл бұрын

Thanks for the explanation!

@aynurmukhambetova1708 4 жыл бұрын

it finally became clear! thanks a lot!

@rohitkumarvarma4952 2 жыл бұрын

Thanks, mann! Finally understood this concept clearly!

@liangchen8238 4 жыл бұрын

Best explanation I've seen so far!

@himanshujhamb 7 жыл бұрын

Nice explanation

@neeraj33negi 4 жыл бұрын

Thanks, this is very detailed.

@asgheralishaik 3 жыл бұрын

nice explannation.Thanks

@adityasingh11156 5 жыл бұрын

Thanks Sir You make it understand in very simple way

@dragosc8202 3 жыл бұрын

Thanks! YOU make my day

@monisattili7642 7 жыл бұрын

Thank you , keep continue

@null-wp1le 4 жыл бұрын

Thank you so much for this video.

@adityaraghav8693 4 жыл бұрын

This was awesome 👍

@rahulchudasama9363 4 жыл бұрын

Nice explanation ...

@kbhargavi4400 4 жыл бұрын

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

@kishantiwari3221 3 жыл бұрын

Thank You sir!

@jeezz4128 3 жыл бұрын

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

@abhishekshrm100 6 жыл бұрын

very nice explanation

@chakrapanisudarshan3027 7 жыл бұрын

Brilliant Explanation in simple words.....

@vivekanandkhyade 7 жыл бұрын

Thanks Chakrapani.!

@ngc35ster 2 жыл бұрын

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

@availkrishmytube 3 жыл бұрын

Excellent!

@naseemahmad2167 6 жыл бұрын

Great explanation sir I salute you it's help me allot

@da_sci3839 3 жыл бұрын

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

@yogeshvaishnav7856 3 жыл бұрын

Bestest explaination ever!

@kingdey9136 4 жыл бұрын

Thank you!

@intechshala5929 3 жыл бұрын

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

@ShivamKendre-fc3su 4 жыл бұрын

What a explanation!!!

@pratiknaik261 2 жыл бұрын

Thanks sir ek no!!💯💯

@vadimtitko7087 4 жыл бұрын

Thanks a lot! It really helps ;)

@shwetasingh7906 7 жыл бұрын

Thanks sir

@karanb2067 4 жыл бұрын

heroic explanation

@SoumikNandi 4 жыл бұрын

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

@XXX-nd2zz 5 жыл бұрын

clear explanation :D!!

@winstonloke2860 4 жыл бұрын

Hi, I have no knowledge about algo, but i do have a question. in detecting the start of the loop, what happens if Q started at say, a different index than stated? P will not equal Q throughout the loop.

@swatisahu1073 2 жыл бұрын

Wow! Thanks.

@KhanSlayer 5 жыл бұрын

Very clear and concise explanation. Nice work.

@shamanthakrishnakg1978 5 жыл бұрын

Thank You very much.

@omarmneimneh983 5 жыл бұрын

THANK YOU!

@prabhat2342 3 жыл бұрын

Just awesome😊

@hailong5871 5 жыл бұрын

You are awesome!!!

@mp0157 5 жыл бұрын

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 :)

@RiteshKumar-hw7ps 5 жыл бұрын

Very nice collection of knowledge/contents you have and also brilliantly explained, only one thing where you can do some improvement is align your camera to cover complete board.