Floyd's cycle detection algorithm (Tortoise and hare) - Inside code
ฝัง
- เผยแพร่เมื่อ 30 ก.ค. 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) - วิทยาศาสตร์และเทคโนโลยี
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 !
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
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
Your approach of explaining algorithms is perfect, thank you very much for your videos
Best channel I've come across for understanding algos clearly 💯
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!❤
Brilliantly clear and visual explanation! Thank you very much!
You have a talent for clear and concise explanations. Thank you so much for this.
You're welcome!
Your hard work really reflects in this video!!! Highly appreciate your talent, thanks a bunch for sharing it
After watching 10 videos , this was what made my day. Thanks
these animations are bomb! Great job!
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
Amazing illustration to understand the solution
Awesome content! It's truly helpful to learn more about algorithms! :) Thank you for your contribution!
Great animation...very easy to understand....Thanks
Good explanation for the mathematical proof, Thank you.
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.
Finaly , what a great explanation , great job
Excellent explanation. Thank you so much for the video.
You're welcome!
Well explained! Thanks!
Again, interesting and super clear, thanks!
Thankd for your comment
great explanation man!
Thank you, this helped me further my understanding of how this works
You're welcome!
Well Explained
Absolutely incredible 😍
This is fantastic, thank you!!
You're welcome!
thx bro, your video is extremly beautiful and clean, excellent!!
Glad it helped!
This deserves more views!
Thanks! Help by sharing the video
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.
i finally get it. thank you!
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.
brilliant stuff sir
Amazing! Thank you!!
The math formula is straightforward but still, i'm like HOW DOES THEY JUST MEET when we do that starting point reset!
thank you so much for making such videos
Doesn't get much better than this. If you're trying to understand this problem, go ahead and start here.
Thank you!
This is literally the best explanation I came across while searching.. thanks a lot man
You're welcome
really helpful visualization! thank you.
You’re welcome
Thanks a lot , great explanation!
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
Best content.. thanks. New subscriber now
This is so helpful
very helpful .
thankyou
Amazing explanation!
Thanks!
absolutely genius.
Gold mine video was just lit❤🔥
Thanks for video buddy.... :)
keep up the good work
I think, In the end code slow and fast should point to arr[0] instead of just 0
Thanks!!
Floyd you genius
Awesome animations!
Thanks!
Great explanation. I solved using the first way. But I got a better one . Thanks 👍☺️
You're welcome!
Great animation!
Thanks!
masterpiece
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!
Thanks
wowww, I wonder what went into initially developing this algorithm
Thank you so much
You're welcome!
THANK YOUUUUUUUU!!!!!!!!!!!!!!!!!
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
ure a freaking god man
how can I use the floyd's algo to search for hashes collisions ? Thanks for your help !
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
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!
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!
Amazing. Just amazing! How do you do these animations?
Hello, I use PowerPoint
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
This is where you know that math can solve anything without any issue
Great video! **just curious** which country are you from? I've never heard this accent before
Thanks! I'm from Algeria
genius
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.
C1, C2, C3 all are integers
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
7:13 why you move the fast pointer only one step there?
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
i lazy to comment (but i click like btn), but you are best in explanation, hat off.
🔥🔥🔥🔥🔥
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.
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!
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.
any mathematical proof , why it works?
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
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
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
this is a math proof, i was expecting a more conceptual/intiuitive explanation before the proof.
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
Change your title to leetcode 287, I came here to understand that question.
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
gg bro
I don't really understand this approach 8:55
Floyd Mayweather wela George Floyd
Saha aimen
Gaweyyeh gaweyyeh 😂👍🏼
If u math videos you’ll get more views I bet
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?
a f