Why Floyd's cycle detection algorithm works? Detecting loop in a linked list.
ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- 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 ...
This guy should be a youtube celebrity! People like him who share knowledge should be made famous.
can't agree more, very well explanation!
he is a celebrity already
Must be
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!
``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,
@@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)
You are absolutely right. Something was missing in that video but THAT"s the main point!
Honestly think THIS should be the main focus, thanks for pointing out
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*.
worth spending 24 minutes , good work.
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!
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!
Finally, there's a video that helps me understand this algorithm. Thanks a lot!
You really save me from struggling with the textbooks and any other recourses I could find, thanks !
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...
this man is unbelievable , the way he explains is just mind blowing
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.
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.
1. Best explanation I've found to describe this! No other explanation made sense.
2. I love the way you say "loop" XD.
after a couple rewinds, i finally got it. i doubt i could ever come up with this algorithm on my own. good vid
I didn't see such a clr explanation ever .... keep going sir
I am convinced that I understood the explanation. Thank you!
your teaching style is amazing ! i dont know why u dont have million subs
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. ;)
Thank you so much
kyaa bataya hain aaapne jo koi na samgha saka aapne samgha diya bohot sahi
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.
This man is gold. But I like watching it at 1.75x speed
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
Thanks, it is the best explanation I have seen so far
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.
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 :)
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
I like the way you explained this. Thank you a lot)
Thanks a lot! I was struggling to understand this at first!
Your explanation is so good that makes learning easy. Great work my friend!
Good to see you after a long time! Great work.
Good going!! :)
Indian professors are awesome!
WOW, very very VERY good explanations, thank u for these videos !!!!!!!!!!!!
Your Explanation is amazing Sir!! Keep making videos
Wonderful explanation - thank you very much.
Thanks so much. I wish we could derive floyd's cycle algorithm instead of assuming it's correct and making the assumptions from there.
Bestest explaination ever!
Best Explanation !
One question : How are we so sure that P and Q will meet after m steps on the loop. Suppose I remove one node from the cycle, it becomes m-1 steps for P. Or if we consider the whole scenario from the starting (taking one node less from cycle), its the behavior of the algorithm that they would both meet at a point at m distance?
I have the same question. Why are we sure that P and Q meet each other after m steps.
@@toancaro ever figure it out?
Thanks man, this is way more clear than the leetcode answer
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!
I found the latter half of the proof lacking. It should also have proven that m = l - k (plus some multiple of l), so that both p and q will meet at the start of the loop after travelling the same amount.
Photon7908 explained the missing part.
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.
Thanks for such a Nice Explanation.
Best explanation I've seen so far!
I am on my knees and have tears in my eyes :)
Excellent explanation!
Very nice explanation!
Thanks, mann! Finally understood this concept clearly!
This guy has just saved me from a sleepless night lol
Your videos are really helpful. Thanks a lot for making them :)
Thank you. i was struggling with this since long.
Very Nice Explanation
Really awesome explanations,thank you.........,If possible please makes a playlist on stacks and queue.
Sure.
Great simplified explanations.
Awesome explanation Sir : )
you are seriously amazing bro...i love your knowledge and teaching way, keep up the good work..
Awesome explanation! Thanks 🙏
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.
install video speed controller extension. it allows you to go beyond 2x speed.
@@blasttrash noted.
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
Such wonderful explanation.Very helpful.
#suggession: Complexity analysis would make the series complete. Please do another video to do complexity analysis!!! Great analysis! Thanks much!
Very well explained.
thanks for explaining it so well..
doing good job!! excellent work keep them coming !!!
Thanks Anand..!
Thanks Sir
You make it understand in very simple way
very well explained thank you..............................
This is very clear and detailed, thanks a lot.
heroic explanation
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.
Nice explanation but it would have been great if you would have considered hare step to be some a*times tortoise and position of hare = b starting position. This will show that the for a=2 and b= any whole number , they will always meet.
Thank you for wonderful explanation
Thanks. Nice explanation
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 :)
Thank You sir!
Really excellent explanation - thank you
Great explaination thank you
This video doesn't show up in top searches of the topic. It makes me think youtube algo is not working properly
my goat!
1) when p travels m + k , q meet p (via observation)
2) Because m + k = always start of loop (proof mathematically)
Therefore, when p meet q, also start of the loop, is it correct?
how is it gauranteed that both pointers will meet?
very well explanation!
This is awesome, this really helped me to finally understand it, thank you.
Thank you!
Great Job !!! Crystal clear explanation !!
Brilliant Explanation in simple words.....
Thanks Chakrapani.!
The second part's explanation was made unnecessarily complex. You have the math and all you need is m = l (p-2q) - k and instead of k you can say K = l - z then you will end up with m = l (p-2q) - l + z and then you can go for modulo l on both sides which would result in m = 0 - 0 + z (mod l), hence you have proven that if you move m steps from start you would also travel from the intersection point z steps (ignoring the cycles that you make)
Now, I know how it works. Thanks
What a explanation!!!
Nice explanation ...
thank you, sir, you explained such a confusing concept very well! :)
really helpful... Thanks a lot
Very clear and concise explanation. Nice work.
great explanation , thanks you saved me viveka !!! :-)
Very clear explanation!
Thanks! YOU make my day
you deserve more subs
this was great, thank you!
Thank you so much for this video.
Thanks for the explanation!
nice explannation.Thanks
Thanks sir
sir i dont even know your name but thanks a lot you made my day i loved it and a little suggestion have a intro it will help you grow.
Thanks.
Very interesting question
Why fldy works for ... ?