hey i have an alternate solution for finding head. after hare and tortoise meet. we will make hare pointer stop at that point and make tortoise pointer move till it reaches hare pointer again and count number on nodes. this will give us length of cycle. ( how many nodes are in cycle). lets denote dis with c. then just take 2 pointers p1 and p2 at c distance apart.. and move both at SAME speed till p1 and p2 meets. that point will be head.
@@DheerajKumar-hr8bf They can point anywhere. Make p1 point to start of list for example and p2 c distance apart. github.com/BismeetSingh/linkedlistoperations Let me know if any mistakes found.
in the end, he meant we get to the Starting point in the cycle since, Moving a Pointer from Head 'D' times = moving the pointer from the meeting point in cycle some constants times - K node Hence the solution works. Thanks, Gaurav this was really helpful.
Best Explanation. Thanks Gaurav for this. 1) At the meeting point one pointer that starts from start covers D. 2) Now at the same point when the next pointer start from meeting point trying to travel D, It will cover N*(circle Length) - k. so from the point it started at will be k steps before. And k steps before is actually the meeting point. So they both will meet at the meeting point.
If you get asked this question in an interview and instantly respond with Tortoise and Hare you’ll likely get another question. I think some people forget the goal of interviews questions is often to see how you solve a problem you don’t already know... that being said, this is one of the better explanations I’ve seen for this algo
Bro, I searched the whole internet to get the proof which I could understand. I wasted my two days in that search and couldn't find one which made sense to me or which I can sink the proof in. I watched your video twice. And I could finally sink it in. Thank you so much man! you saved me. Especially the last proof of how to make the pointers point to the starting node.
You're not only good at the CS part of things, you're also an amazing teacher! I kept asking a question in my head only to have you answer it right after. Thank you for this amazing lesson!
Coming here after going through two different sources , now I don't need to go any where because solution make sense to me now :) . Thanks for your efforts!!
start with fast and slow pointers. When slow meets fast, stop. Take a pointer p1, now assign head to p1. Move p1 by one position and slow by one position till p1 and slow meet. By the way, slow and p1 will meet exactly at the start of the loop.
Hi Gaurav ,You nicely explained the explained the existance of solution for the equation but it can also be explained by the fact that if loop exist ,then when tortoise enter into the loop there are two particle in loop moving with different angular speed. So they have to meet at point. Relative angular speed is non zero constant so they must collide.
...15 years ago it took me couple of hours to find this solution, though after some fiddling with analytical approach which was hard to interpret, finished with much easier graphical...
At around 3:45 why does n need the c and i variables? Doesn't the tortoise never make it through a full cycle since the hair would intersect it before that happens?
+TrollkimNoah That might be true. But in the worst case, the tortoise and hare will meet at the start of the circle. Assume the whole graph to be a circular list. Then the tortoise makes 1 revolution and the hare makes 2.
No need to add maths equations too. Consider a very large cycle so that the first pointer when it reaches the starting node of the cycle is t distance behind the fast pointer. That means that fast pointer is (c-t) distance behind the first to catch up with it. So, we have (c-t) + y = 2y assuming at y nodes far away the both will meet. so y = (c-t) or in other words, the meeting point is at distance c from the head pointer. So now just take head and slow pointer(at the meeting point) and keep doing ->next until they both coincide. That will be the answer.
If space complexity is not an issue, we can iterate the loop till it reaches null and keep checking each node in HashSet. If a node doesn't exist then add it to HashSet and if it exists then break the loop and return that node which is the start of loop. To find length of the loop, we can keep extra Stack where we push the node while iterating until we discover the starting node of the loop as mentioned above. Then keep popping the nodes from the stack until we get the starting node and keep a counter while popping which is the length of the loop.
If we start the pointer at the start and one at the meeting point and move them by D+K then both end up at the same place? Can you be more specific around 8:05 to 8:12
We end up at the same place, which is the meeting point, if we move the pointers from the start and meeting point respectively. The reason for this is D+K is where the meeting point is. Also, we see that D+K is a multiple of C, so any pointer inside the circle when moved by D+K nodes will revolve to the same place. Thats because moving a distance divisible by C is like taking a few cycles around the loop.
the equation that you figured out at 4:36 th sec that is N=C*(j-i). Does it mean that walking for some value of N (where n is D+K+C(i)) steps is same as making few complete cyclic loops ?
We can explain it even simpler if we set the starting of loop at the head node( the starting node). And then make it complex by adding the nodes at the starting point.
When ever we are choosing the slow pointer and fast pointer how fast they should move(can slow pointer move twice and fast pointer move three times .How we should decide.)
How do you compare nodes in a cyclic graph though? In the final solution it seems like you need to start a pointer at the head (hptr) and at the meeting point (mptr), move forward by 1 and then check if hptr == mptr. how would the linked list implementation handle that? memory location or following the nodes?
Your explanation proves that from the meeting point i.e. c(j - 2i) it falls 'k' short to reach the intersection point, but it doesn't prove that from the meeting point it will take 'D' to reach the intersection point. I think what is missing over here is you will have to prove 'j-2i' is always equal to 1.
I got a very weak solution to this problem and somehow passed the challenge. So, what I did was : I changed the data value of each visited node to a particular number (say -25 for my case) and then checked the data of the next node that my loop encounters. If that is equal to -25, I conclude that there is a loop, else not. So, I remembered which nodes I had visited. I know that no number can fit as a "sentinel" value, but yes I tried and got results. HOWEVER, THIS IS NOT A REAL SOLUTION, JUST A BYPASS!
Alternative soln. Insert a unique key(say $) as you traverse the list. i.e. 0 - $ - 1 - $ - 2 - $ - 3 - $ - 4 - $ - 5 - $ until you find the next link of a node to point to $ which will also mark the beginning of the cycle.
Hey Gaurav, let's say that if the question asked was to find out start point of the loop. How is this algorithm efficient than hashing? hashing would always take O(N) space and run time is O(N). but this algorithm runtime can be more than O(N).. but I agree that this will always take a constant space O(1). Just trying to understanding which one is better?
This algorithm has a run time of O(N) actually. The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2. This question is usually asked to test a candidate's resourcefulness. Hashing is the practical approach, but this works better in interviews 😊
Hey man, could you please explain the reasoning behind the GCD concept " The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2". Or could you post a link where I can learn about it?
it could be explained much easily: 1. the meeting point is at kth distance from loop entry(say 0th node) 2. basically if we go back (-k) from meeting point(k) we will get to the loop entry 0th node (k+(-k) = 0) 3. But the reality is that the meeting point k was met by doing 'c' cycles in loop which could be 1 cycle, 2 cycle.....c cycles 4. so if the meeting point was achieved after 1 cycle (assume for simplification) then 1*n-k will give us the loop entry(0th node) which is at a distance 'D' from the head 5 using the idea from step4, we move 'D' from meeting point(k) which will lead to loop entry(0th node) Note: if we move further +k from loop entry after doing step-4 then we would have made a complete cycle +1n and will be again at meeting point
If you're going to move D nodes in cycles you're going to fall short of K nodes->Starting point of cycle in LL. If you're going to move D nodes from head->Starting point of cycle in LL.
For those who are finding it little difficult to understand. Think of it this way: From the equation, it is already known that if you move the hare pointer(after meeting) d times, you will end up falling short behind k pointers and hare pointer is already at a k distance from the meeting point. So, falling down short a distance of k means that it will be at meeting point when it moves a distance d We don't know d. But we know the condition that hare pointer(after meeting) and head pointer will be equal only after moving d times. So, if they are equal we can conclude that they moved a distance d which is the meeting point
Hi Gaurav Thanks for the explanation. Food for thought: Will this work ... 1. If Hare moves at 3x the speed and Tortoise moved 1x, for all the cases? 2. If the Hare runs at 3x and Tortoise moved at 2x the rate?
Thanks for the mathematical proof but test case which includes a whole circular linked list requires slight change in finding the start of the loop ie. head
Hi Gaurav, Nice explanation. But you needed to say that k=(j-2i)x-D, so the slow pointer is at D iterations short of a cycle. So just by iterating it D number of time, we can get to the beginning
Don't you think the distance k should represent distance from 2 to 4 instead of 3 to 4? Otherwise, the equation itself will not be right. Moreover, when you say, in the end, that we would be 'k' short that means from the meeting point we would go back to 3 not 2, correct?
Can we find the starting point of the loop by using map in which we store the addresses of visited nodes until we find a node whose address has already been in the map.
hey one thing that i dont understand is if we find out the node to which the last node of the linked list(here its 5) is pointing then also we can find the start of the loop. so can you help me with this.
Can't we store reference/pointer of each node we have visited and check with the current node for similarity? If they are similar then there is loop and also it's start.
Imagine when there is no loop actually. You'll be storing infinite pointers and the program will never end. But in this method, the fast pointer reaches the NULL and breaks.
@@RandomlyKabhiKabhi if there is no loop then we'll only be storing n pointers and not infinite pointers. If there is no loop then there would be an end of the list
@@anmolagarwal5952 Oh sorry sorry. got it. Then this cycle detection method(Floyd cycle detection) is just to save space. Time is O(n) in both algos. Just that space is O(n) by your method. The video one uses O(1) space
hey i have an alternate solution for finding head.
after hare and tortoise meet. we will make hare pointer stop at that point and make tortoise pointer move till it reaches hare pointer again and count number on nodes.
this will give us length of cycle. ( how many nodes are in cycle). lets denote dis with c.
then just take 2 pointers p1 and p2 at c distance apart.. and move both at SAME speed till p1 and p2 meets. that point will be head.
Hey Shlok, this will also work. Nice alternative :-)
Nice alternative. IMHO, that would increase the constant of the algorithm and also the code complexity. If you don't care about these, then it works.
simple solution sir great
@@DheerajKumar-hr8bf They can point anywhere. Make p1 point to start of list for example and p2 c distance apart.
github.com/BismeetSingh/linkedlistoperations
Let me know if any mistakes found.
Hey, shlok . Thanks Man. Great Imagination!
in the end, he meant we get to the Starting point in the cycle since,
Moving a Pointer from Head 'D' times = moving the pointer from the meeting point in cycle some constants times - K node
Hence the solution works.
Thanks, Gaurav this was really helpful.
Best Explanation. Thanks Gaurav for this.
1) At the meeting point one pointer that starts from start covers D.
2) Now at the same point when the next pointer start from meeting point trying to travel D, It will cover N*(circle Length) - k. so from the point it started at will be k steps before. And k steps before is actually the meeting point. So they both will meet at the meeting point.
If you get asked this question in an interview and instantly respond with Tortoise and Hare you’ll likely get another question. I think some people forget the goal of interviews questions is often to see how you solve a problem you don’t already know... that being said, this is one of the better explanations I’ve seen for this algo
Best to brush up on those acting skills then (Oh, find a loop in a linked list?! Gee, I wonder how....)
@@gkcs nice thought...
@@gkcs haha
can you really end up figuring out haze and turtle by yourself for the first time you see this exercice ? I mean under pressure ?
@@splendidbeaver2027 definitely not, lol!
Bro, I searched the whole internet to get the proof which I could understand. I wasted my two days in that search and couldn't find one which made sense to me or which I can sink the proof in. I watched your video twice. And I could finally sink it in. Thank you so much man! you saved me. Especially the last proof of how to make the pointers point to the starting node.
You're not only good at the CS part of things, you're also an amazing teacher! I kept asking a question in my head only to have you answer it right after. Thank you for this amazing lesson!
Thank you 😁
it is evident that he kept trying to understand why it works for a long time and then finally when he understood he was so happy❤
Thank god, finally someone explained the intuition behind this..
You're just amazing 🙌
Coming here after going through two different sources , now I don't need to go any where because solution
make sense to me now :) . Thanks for your efforts!!
It was hard wrap my head around this concept. Thank you for making this video and providing with a detailed explanation.
oh man, you are something else, fantastic explanation!!!
Man this is wonderful, I was so stuck in this problem, went through multiple videos but finally found the perfect explanation. Thanks a ton, Gaurav.
You're welcome!
Love the energy of your teaching style!
Gaurav maaaan! I saw this question a few years back And couldn't understand the solution. This video helped! 😄. Thanks
9:00 this was the missing link I was looking for!
Thanks Gaurav bhai for this explanation!!!
So,this was a interesting questions. I found a solution after couple of years.😁
At last excellent explaination.
atlast someone explained the algorithm with proof. amazing work.
start with fast and slow pointers.
When slow meets fast, stop.
Take a pointer p1, now assign head to p1.
Move p1 by one position and slow by one position till p1 and slow meet.
By the way, slow and p1 will meet exactly at the start of the loop.
Was stuck at this problem over a month, now i finally understand it, thanks a lot!!!
most important thing is how to act like you have seen this question for first time in an interview :))
Hi Gaurav ,You nicely explained the explained the existance of solution for the equation but it can also be explained by the fact that if loop exist ,then when tortoise enter into the loop there are two particle in loop moving with different angular speed. So they have to meet at point.
Relative angular speed is non zero constant so they must collide.
+Shiwang Awasthi Ah, yes that is true. A really good and intuitive observation. Thanks!
...15 years ago it took me couple of hours to find this solution, though after some fiddling with analytical approach which was hard to interpret, finished with much easier graphical...
Thanks a lot. This video help me understand the logic behind this.
Finally someone explaining the math, thanks!
At around 3:45 why does n need the c and i variables? Doesn't the tortoise never make it through a full cycle since the hair would intersect it before that happens?
+TrollkimNoah That might be true. But in the worst case, the tortoise and hare will meet at the start of the circle. Assume the whole graph to be a circular list.
Then the tortoise makes 1 revolution and the hare makes 2.
Beautiful Explanation Brother !!!
No need to add maths equations too. Consider a very large cycle so that the first pointer when it reaches the starting node of the cycle is t distance behind the fast pointer. That means that fast pointer is (c-t) distance behind the first to catch up with it. So, we have (c-t) + y = 2y assuming at y nodes far away the both will meet. so y = (c-t) or in other words, the meeting point is at distance c from the head pointer. So now just take head and slow pointer(at the meeting point) and keep doing ->next until they both coincide. That will be the answer.
If space complexity is not an issue, we can iterate the loop till it reaches null and keep checking each node in HashSet. If a node doesn't exist then add it to HashSet and if it exists then break the loop and return that node which is the start of loop.
To find length of the loop, we can keep extra Stack where we push the node while iterating until we discover the starting node of the loop as mentioned above. Then keep popping the nodes from the stack until we get the starting node and keep a counter while popping which is the length of the loop.
Your explanation deserves an extra like! Great video bro
Thanks!
If we start the pointer at the start and one at the meeting point and move them by D+K then both end up at the same place? Can you be more specific around 8:05 to 8:12
We end up at the same place, which is the meeting point, if we move the pointers from the start and meeting point respectively.
The reason for this is D+K is where the meeting point is. Also, we see that D+K is a multiple of C, so any pointer inside the circle when moved by D+K nodes will revolve to the same place.
Thats because moving a distance divisible by C is like taking a few cycles around the loop.
thankyou for this much needed explanation.
Watch it twice to get the intuition :')
after watching it 3 times finally got it, now i can also explain it someone
the equation that you figured out at 4:36 th sec that is N=C*(j-i). Does it mean that walking for some value of N
(where n is D+K+C(i)) steps is same as making few complete cyclic loops ?
Awesome Explanation !!
The -K part really hits the point! Nice work!
Excellent Explanation. Keep up the good work man...!
Very good explanation. Thanks!
Thank you!
"loor" dekhe amio hese more gelam. ki khilli. Btw really great video! Keep it up. :)
We can explain it even simpler if we set the starting of loop at the head node( the starting node). And then make it complex by adding the nodes at the starting point.
Great Explanation Sir
Great video. Thanks for sharing!
Thanks 😊
When ever we are choosing the slow pointer and fast pointer how fast they should move(can slow pointer move twice and fast pointer move three times .How we should decide.)
Loved this explanation, finally I fully understand how it works💡
How do you compare nodes in a cyclic graph though? In the final solution it seems like you need to start a pointer at the head (hptr) and at the meeting point (mptr), move forward by 1 and then check if hptr == mptr.
how would the linked list implementation handle that? memory location or following the nodes?
Hi Gaurav,
Alternative code for finding the starting node of linked list cycle. Please let me know if there are any issues.
if (loopExist) {
slwPtr = slwPtr.next;
List list = new ArrayList();
while (slwPtr != fstPtr) {
list.add(slwPtr);
slwPtr = slwPtr.next;
}
slwPtr = head;
while (slwPtr != fstPtr) {
if (list.contains(slwPtr)) {
return slwPtr;
}
slwPtr = slwPtr.next;
}
}
start = slwPtr;
return start;
Nice try but no.
No auxiliary space. That extra list used won't be allowed 🥺
Such a nice explanation
D+K part was explained so nicely, thanks bhaiya
finally understood the logic thanks
Nice explanation and logic deduction Gaurav_Sen..!!
Awesome explanation Gaurav!
Your explanation proves that from the meeting point i.e. c(j - 2i) it falls 'k' short to reach the intersection point, but it doesn't prove that from the meeting point it will take 'D' to reach the intersection point. I think what is missing over here is you will have to prove 'j-2i' is always equal to 1.
I think if it is not equal to 1 then it will end up in a never-ending loop as they are moving at the same speed. Any thoughts? @Gaurav Sen
I got a very weak solution to this problem and somehow passed the challenge. So, what I did was : I changed the data value of each visited node to a particular number (say -25 for my case) and then checked the data of the next node that my loop encounters. If that is equal to -25, I conclude that there is a loop, else not. So, I remembered which nodes I had visited. I know that no number can fit as a "sentinel" value, but yes I tried and got results. HOWEVER, THIS IS NOT A REAL SOLUTION, JUST A BYPASS!
very nice explanation tank you
I got it! Very clear. Thank you!
watching it in 2020... deeply explained. thanks !
Alternative soln. Insert a unique key(say $) as you traverse the list. i.e. 0 - $ - 1 - $ - 2 - $ - 3 - $ - 4 - $ - 5 - $ until you find the next link of a node to point to $ which will also mark the beginning of the cycle.
Its a good idea if you can modify the list. Most of the interviewers don't allow that. :)
is there any playlist of Interview Questions?
awesome explanation !!
Thanks a lot Gaurav Bhai
Hey Gaurav, let's say that if the question asked was to find out start point of the loop.
How is this algorithm efficient than hashing?
hashing would always take O(N) space and run time is O(N).
but this algorithm runtime can be more than O(N).. but I agree that this will always take a constant space O(1).
Just trying to understanding which one is better?
This algorithm has a run time of O(N) actually. The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2.
This question is usually asked to test a candidate's resourcefulness. Hashing is the practical approach, but this works better in interviews 😊
thanks Gaurav - This GCD info helps..
Hey man, could you please explain the reasoning behind the GCD concept " The loop will have both pointers touching inside within 2 rounds. Thats because the gcd of (loop length and 2) is atmost 2". Or could you post a link where I can learn about it?
It's not mentioned anywhere I think...here is another video which might help with the intuition: ua-cam.com/video/D-DYtUmRMa4/v-deo.html
great explanation. Written explanations out there are hard to understand. nice job!
Great explanation, love the intuition you give !!!
Amazing content, love your channel. I will share this video with my Junior college-mates :)
it could be explained much easily:
1. the meeting point is at kth distance from loop entry(say 0th node)
2. basically if we go back (-k) from meeting point(k) we will get to the loop entry 0th node (k+(-k) = 0)
3. But the reality is that the meeting point k was met by doing 'c' cycles in loop which could be 1 cycle, 2 cycle.....c cycles
4. so if the meeting point was achieved after 1 cycle (assume for simplification) then 1*n-k will give us the loop entry(0th node) which is at a distance 'D' from the head
5 using the idea from step4, we move 'D' from meeting point(k) which will lead to loop entry(0th node)
Note: if we move further +k from loop entry after doing step-4 then we would have made a complete cycle +1n and will be again at meeting point
thnx buddy reall yhelpful
Well explained! I didn't understand even though I read the solution but I totally got it with your video. Thank you :)
Glad to hear that 😁
thanks for explanation 😃
If you're going to move D nodes in cycles you're going to fall short of K nodes->Starting point of cycle in LL.
If you're going to move D nodes from head->Starting point of cycle in LL.
I have a question. How are we going to compute the length D? Because if we dont we cannot stop the pointer P1.
For those who are finding it little difficult to understand. Think of it this way:
From the equation, it is already known that if you move the hare pointer(after meeting) d times, you will end up falling short behind k pointers and hare pointer is already at a k distance from the meeting point. So, falling down short a distance of k means that it will be at meeting point when it moves a distance d
We don't know d. But we know the condition that hare pointer(after meeting) and head pointer will be equal only after moving d times. So, if they are equal we can conclude that they moved a distance d which is the meeting point
Exactly the explanation I wanted to know.
Thank you!
Nice explanation
4 years old vedio. Still clear explanation omong all vedios available in youtube.
Gotcha! I had to re-watch, but got it finally.
Awesome!
@@gkcs Hi Gaurav, can you make videos on the problem www.interviewbit.com/problems/matrix-median/ and system design of a voting system?
same here bro
really nice bro ,keep teaching :)
Keep up the stellar work! This is some really useful stuff!!
Hi Gaurav
Thanks for the explanation.
Food for thought: Will this work ...
1. If Hare moves at 3x the speed and Tortoise moved 1x, for all the cases?
2. If the Hare runs at 3x and Tortoise moved at 2x the rate?
Food for thought: The gcd of the speeds must be 1 for a guaranteed meet :)
U are really good at explaining things :)
Thanks!
Hey sir, can u please clarify why we move hare by two nodes always why not 3 4 or any random number ? Why always 2?
The GCD of the hare and tortoise have to be 1 for them to converge in the loop. Try proving this :)
Thank you for this video
Awesome video! Thank you for explaining so clearly
Thanks for the mathematical proof but test case which includes a whole circular linked list requires slight change in finding the start of the loop ie. head
The first question they ask in any damn interview.
can we detect by moving fast ptr say by 3,4,5 and slow ptr by 1? Is there any mathematical proof of meeting slow and fast ptr inside the loop
Yes they will. It has to do with the HCF of the circle size and speed of the fast pointer. You can try some combinations out.
Thanks Gaurav
nice explaination
Hi Gaurav, Nice explanation. But you needed to say that k=(j-2i)x-D, so the slow pointer is at D iterations short of a cycle. So just by iterating it D number of time, we can get to the beginning
You are wrong.
great work man. Keep doing. 👍👍👍👍👍👍👍
I would have known the solution posted by @shlok singh
But your solution is smarter and shorter. I will keep this in mind.
Don't you think the distance k should represent distance from 2 to 4 instead of 3 to 4? Otherwise, the equation itself will not be right. Moreover, when you say, in the end, that we would be 'k' short that means from the meeting point we would go back to 3 not 2, correct?
Thanks a lot, this video was really helpful!!
Thank u gaurav ...👍
That was a great explanation. Thx so much for the help! :-)
FINALLY GOT IT! THANKS
Excellent explanation
Can we find the starting point of the loop by using map in which we store the addresses of visited nodes until we find a node whose address has already been in the map.
No auxiliary space allowed.
Could someone please point me to the link of an implementation for this
hey one thing that i dont understand is if we find out the node to which the last node of the linked list(here its 5) is pointing then also we can find the start of the loop. so can you help me with this.
How?
very well explained!
Thanks!
Can't we store reference/pointer of each node we have visited and check with the current node for similarity?
If they are similar then there is loop and also it's start.
Imagine when there is no loop actually. You'll be storing infinite pointers and the program will never end.
But in this method, the fast pointer reaches the NULL and breaks.
@@RandomlyKabhiKabhi if there is no loop then we'll only be storing n pointers and not infinite pointers.
If there is no loop then there would be an end of the list
@@anmolagarwal5952 Oh sorry sorry. got it.
Then this cycle detection method(Floyd cycle detection) is just to save space.
Time is O(n) in both algos.
Just that space is O(n) by your method. The video one uses O(1) space
Thanks buddy!
great explanation
Thank You Sir.