Floyd's cycle detection algorithm (Tortoise and hare) - Inside code
Vložit
- čas přidán 30. 07. 2021
- Source code: gist.github.com/syphh/0c9286d...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram) - Věda a technologie
Discover the new graph theory algorithms course: inscod.com/graphalgo
🔴
/ \
🔵-🔴
| |
🔴-🔵
That graphics requires a lot of work, TYSM👌👌
You're welcome!
Where did you do the graphs and animation? @@insidecode
After meeting the hare, the rabit also slows down. Important point
Giving the mathematical explanation for getting the entry point of cycle was the best part !
Great video with clear animations and explanations to about the internal logic behind the tortoise-hare algorithm, as well as how it can be used in the find the duplicate problem . Appreciate the effort
This is the best explanation that I have found after discussing the same question with atleast 3 friends, they knew the approach but were not able to explain as clearly as this one
Your approach of explaining algorithms is perfect, thank you very much for your videos
Best channel I've come across for understanding algos clearly 💯
I've read numerous articles on this, but the algorithms always seemed confusing. However, your video provided a clear and concise explanation. Thank you so much for making it easy to understand
This is the only video that I found, which explains why it specifically work in a reasonable way not just using slow and fast and make them met
Thanks!❤
Your hard work really reflects in this video!!! Highly appreciate your talent, thanks a bunch for sharing it
Brilliantly clear and visual explanation! Thank you very much!
After watching 10 videos , this was what made my day. Thanks
You have a talent for clear and concise explanations. Thank you so much for this.
You're welcome!
Amazing illustration to understand the solution
these animations are bomb! Great job!
Awesome content! It's truly helpful to learn more about algorithms! :) Thank you for your contribution!
Thank you for actually explaining how this works. I'm solving LeetCode 142 and I swear every video wouldn't actually explain *why* it works.
A few questions..
..1st: Since fast enters the cycle earlier it's clear to me, why we need c1*l for the fast pointer. But slow will never make a lap before slow and fast meet, hence c2 is 0, isn't it?
..2nd: It's still not clear to me why we have to slow down fast for this to work. Doesn't slowing down fast break the whole equation we just formulated? Since c1 is the amount of laps fast did under the circumstances of fast being twice as fast as slow.
Good explanation for the mathematical proof, Thank you.
Finaly , what a great explanation , great job
Well explained! Thanks!
Great animation...very easy to understand....Thanks
Absolutely incredible 😍
This is the best explanation of why the second part of the algorithm works. I was confused why that was being assumed.
It's a great trick to add to the mental toolbox! However, if processing is the bottleneck, hash tables may be preferred. This way the list is only scanned n times at most.
great explanation man!
Thank you, this helped me further my understanding of how this works
You're welcome!
Excellent explanation. Thank you so much for the video.
You're welcome!
You can alsow think in terms of relative velocity
From the point of view of slow pointer, fast pointer is moving 1 node ahead at a time
So if finally fast pointer reaches the slow one, then definitely there is a cycle
I think, using the similar approach if you move slow pointer n times forward and the fast one (n+1) times forward, that should also work
Well Explained
brilliant stuff sir
Doesn't get much better than this. If you're trying to understand this problem, go ahead and start here.
i finally get it. thank you!
The math formula is straightforward but still, i'm like HOW DOES THEY JUST MEET when we do that starting point reset!
Amazing! Thank you!!
thank you so much for making such videos
Again, interesting and super clear, thanks!
Thankd for your comment
Thank you!
This is literally the best explanation I came across while searching.. thanks a lot man
You're welcome
This deserves more views!
Thanks! Help by sharing the video
thx bro, your video is extremly beautiful and clean, excellent!!
Glad it helped!
This is fantastic, thank you!!
You're welcome!
Gold mine video was just lit❤🔥
absolutely genius.
really helpful visualization! thank you.
You’re welcome
This is so helpful
very helpful .
thankyou
Floyd you genius
I think, In the end code slow and fast should point to arr[0] instead of just 0
how can I use the floyd's algo to search for hashes collisions ? Thanks for your help !
keep up the good work
Thanks!!
Best content.. thanks. New subscriber now
Thanks a lot , great explanation!
You're welcome!
Thanks
Amazing explanation!
Thanks!
Thanks for video buddy.... :)
Really great video sir. Was trying to understand the proof for a while, and the more read material on it, the more I got confused. So tried to watch many other videos, they helped a little but not fully, but after watching your video, it came intuitively to me. Thanks a lot. Amazing way of teaching.
You're welcome!
Amazing stuff. Helped me really understand the algorithm.
Though I hope the rest of your videos are a bit clearer in audio.
Thanks, I'm working on it!
masterpiece
7:13 why you move the fast pointer only one step there?
Awesome animations!
Thanks!
Amazing. Just amazing! How do you do these animations?
Hello, I use PowerPoint
wowww, I wonder what went into initially developing this algorithm
Great explanation. I solved using the first way. But I got a better one . Thanks 👍☺️
You're welcome!
Great animation!
Thanks!
THANK YOUUUUUUUU!!!!!!!!!!!!!!!!!
ure a freaking god man
very clear thanks you are number one, you are special from others
Thanks a lot!
@@insidecode however, you speak too fast, I'm not a native speaker I can't grasp it, I hope you speak more slowly
Ok thanks for telling me
Great visuals and a very interesting algorithm. Subbed! But I want to join these asking about "x = ( c1 - 2c2 - 1) l + l - y" equation. I understand that (-1 * l) and +l will cancel each other out, so we're just using properties of math in here. But how one comes up with this idea? Is this just something that you learn to intuit?
I think yes, it's the sort of algebra "acrobatics" (or tricks) that you learn from others.
I believe Floyd himself didn't come up with this algorithm in a 30 minutes interview session 😀. It takes time to invent a brand new solution to a complex problem
Thank you so much
You're welcome!
This is amazing ! I can’t believe the details you put into this :o
Also I think off an easier algo called cycle sort if we were to solve the find duplicate algo. I think that if the question was represented as a linked list then theres more merit to us rabbit vs turtle algo here. Thoughts ?
@@insidecode that is true! But thanks to the range from 1 to n it can be done in O(n), i dmed u on insta!
Great video! **just curious** which country are you from? I've never heard this accent before
Thanks! I'm from Algeria
Why does fast and slower pointer eventually meets up in the cycle, I understand they traverse at different paces, but is there no situations where the fast pointer somehow always misses the slow pointer?
imagine this like spinning planets, the faster a planet completes its revolution, the more often it can be spotted from the slower planet
Can anyone explain how traversing and saving nodes in a set will identify cycle in a link list when there are multiple nodes with same value in linklist with out having any cycle? 00:40
Because linked list nodes are identified by their reference, which is unique, not by their value. You can for example in Python create an object and call id function on it like this id(object), you'll get as a result the id of that object
@@insidecode Thanks for quick reply.
I got it now. At 00:40 set is containing only references and at 08:40 set is containing values.
The degree of explanation is amazing!! but i have a couple of questions:
1 How did you decide to re-arrange the values in a linked list like this? why is 6(4) second for example and not 3?
2. .head isnt a method part of the list datatype though. What is llist here? When i do [1,3,4,4,5 ].head -- this is invalid. Would love if someone can explain! Thanks x
llist is of type LinkedList, check the code in description to see LinkedList definition
This is the best explanation I've seen so far! But why is it implied that the fast pointer will always make c₃l loops before we slow it down? You showed that this is correct for yet another example of a linked list but isn't it the same as trying to prove a generalized case by proving more specific ones? I mean that two examples does not prove it yet. Probably one can find a really big loop with a really small tail. Will it still hold up? I guess yes, but why? And why do we even bother ourselves with slowing down the fast pointer? Couldn't it make it to the start of the loop with the previous step size (which is equal to 2 nodes at a time). I mean there's nothing in the formula that tells us to use a certain step size and c₃l + z distance can be passed with the same pace as well. Or not? To me c₃ is just some constant value which we introduced to replace the longer one: c₁ - 2c₂ -1
Hello, c3 is just another constant yes, c3 times l just means that fast will perform a certain amount of loops to kind of wait for slow, c3 can be 0, 1, 5, 1000... whatever, it depends on the length of the tail and the cycle. And examples were there just to show you what happens, the proof was done with the equations, we proved that x = c3l + z.
And for slowing down fast, it's because they must have the same speed, let me give you an example. We have two people walking towards a same position, and we know that they're at a same distance from that position, this is not enough to say that they will meet at that position, another condition is that they walk at the same speed. Same logic here, slow is at a distance x from the entry point of the cycle (what we're searching for), and fast is at a distance of c3l+z. And we proved that x = c3l+z, but it's not enough to know that they will meet at the entry point, they should also keep the same speed.
Dude you are good!💯🔥
Thanks 🔥
@@insidecode make more videos 💯
I'm posting one every week, you can also follow me on Instagram where I also post content: @inside.code
genius
any mathematical proof , why it works?
This is where you know that math can solve anything without any issue
🔥🔥🔥🔥🔥
Can someone explain to me how " x = (c_1 - 2c_2)l - y" became "x = (c_1 - 2c_2 - 1)l + l - y"? Where did " - 1)l + l" were derived from?
Adding l and subtracting l doesn't change the equation, so by doing it we get x = (c1-2c2)l +l -l -y, and by taking the -l inside the parentheses it becomes -1 (because what's inside the parentheses is multiplied by l), so we get x = (c1-2c2-1)l +l -y
i lazy to comment (but i click like btn), but you are best in explanation, hat off.
C1, C2, C3 all are integers
Thanks, man. This is incredible. My question is, what if one of the elements of the array was large, say, 200, but we know that this index doesn't exist because maybe n = 5. Now, let's say fast = 200; then array[ array[fast] ] = will be array[ array[200] ], which index is not present in the array. How is it dealing with this cause it works but I don't understand why
Having an element being equal to 200 while n is equal 5 means that the input is wrong, because the problem says that the array contains n+1 numbers all between 1 and n
@@insidecode Thanks for the reply, makes sense now!
@@yonahgraphics You're welcome!
Can someone explain 5:35? I do not understand how he got -1 and +l
We start by adding l and subtracting l, it doesn't change the expression, then we entered the -l inside parenthesis, it becomes -1 because what's inside the parenthesis will be multiplied by l
@@insidecode Took me a while but I got it. I remember one of the my smartest math professor do this now and it just felt like he was Doctor Strange. Thank for the video and the visuals are on point
5:48 x,=(c1-2c2-1)l+l-y pls explain this step
he added a - 1 inside the brackets multiplying l and then added l outside such that when you evaluate the brackets the - l cancels out the + l
if we take fast = arr[arr[slow]] instead of the fast = arr[arr[fast]]; if is way more faster
fast = arr[arr[slow]] would be wrong because fast would depend on the position of slow, which shouldn't be the case
gg bro
what is happening here , x = ( c1 - 2c2 - 1) l + l - y ?
5:48 x,=(c1-2c2-1)l+l-y pls explain this step
we just re-write c1*L - 2*c2*L as :
= c1 * L - 2 * c2 * L + 0
= c1 * L - 2 * c2 * L - L + L essentially we are writing + 0 as -L + L
that way we can condense all the constants into a new constant c3
= (c1 - 2* c2 - 1 ) L + L - y
= c3 L + y + z - y
which becomes :
= c3 * L + z
My brain is enthusiastically rejecting this whole idea 😞 I shall have to revisit this video next time I need to find a loop
haha, we're here if you didn't understand something
@@insidecode I guess I just need to understand a specific proof of why exactly there will never be a list with a loop where the two pointers can skip each other for eternity.
I don't really understand this approach 8:55
this is a math proof, i was expecting a more conceptual/intiuitive explanation before the proof.
Change your title to leetcode 287, I came here to understand that question.
last example is useless other than in this toy example, almost never values translate to indices in a array(in bound).
What is the proof they will meet im loop?
Floyd Mayweather wela George Floyd
Saha aimen
Gaweyyeh gaweyyeh 😂👍🏼
If u math videos you’ll get more views I bet
a f