I've seen Floyd's Tortoise & Hare algorithm many times and have taken it for granted. This is by far the best explanation of why it works and why it's O(n) time. Many thanks to Neetcode!
Thanks, explaining the slow pointer increases the distance by 1 and the fast pointer decreases distance by 2 shows how the distance is always decreasing by 1 so fast will never overtake!
It's crazy. To undderstand Floyd's Tortoise and Hare, I watched a lot of videos on UA-cam but it couldn't work and I gave up. Today, I was solving Leetcode 141 problem and to find a solution with space O(1), I watched it and wow... There were already lots of times 'WOW' while watching neetcode' videos, but wow... 10-(2-1), n-1.. this guy got me understand this. just with two lines. Crazy. I learn a lot from your videos, not only algorithm...
Great solution! I found one that is simpler, although might be considered the "easy way out".... If you set each node's value to None/null/undefined (depending on the language), then you can just check for if the current node is undefined in the loop. This solution is slightly faster than the slow/fast pointer method: class Solution(object): def hasCycle(self, head): if not head: return False while head.next: if head.val == None: return True head.val = None head = head.next return False
Great solution: 1. Altering source linked list is not idael in a real time scenario, unless the arg passed is already a deep copy of the original linked list and not just a shallow copy. 2. If we had to create a deep copy ourselves, it'll add up to the memory utilised by our solution.
@@Jesseiceheart In C/cpp, by specifying const to the list passed, the function will return with an unaltered list. Is there a way to do this in python? bool hasCycle(const head){}
Always love your videos. I've been working hard on LC problems for the last 10 days and I always come to these videos when I get stuck or would love to learn a clean, concise solution.
to be technical, when you store an object like a Node in a dictionary in python we are storing the address in the dictionary/set. That is how we can be sure that we have not seen it before using the "hashset" approach. Felt it was worth commenting. BTW saw your video the other day about you working in Seattle at Google! well deserved. I love your content! You may look into becoming a CS teacher when you're burnt out working at major tech giants. haha keep them coming!
Thank you! I was wondering how the objects were being stored in the hashset since the node objects themselves are not hashable, but now I see that their memory addresses are.
when you are doing the comparison of fast == slow, what exactly is happening? Are the memory addresses being compared in that way as well? If so, what is the difference between the comparison x == 5 where x is 5 and fast == slow? How does Python know to compare memory addresses for fast and slow and actual values for x == 5?
chatgpt answer to my question, let me know if it's correct: In Python, the comparison x == 5 is different. It compares the value of the variable x (which is 5) with the value 5. Python knows that x is an integer, so it compares the integer value directly. However, when it comes to objects in Python, such as the ListNode instances in the linked list, the comparison slow == fast compares the memory addresses of the objects. It checks whether slow and fast are referring to the same object in memory, rather than comparing the contents of the objects.
@neetcode is goated! I was having a hard time with some of the previous linked list questions in neetcode 150 but with this one I was able to solve it first by using a hashSet and then did the follow up once I saw someone mention tortoise and hare's algo because i assumed it had to mean slow and fast pointers if memory complexity was O(1). I feel like with a lot of the leetcode questions you keep getting beat up until eventually some of the topics 'click' and then you finally start seeing the fruits of your labor! Thanks neetcode you're the man 🙏
Sigma solution - print function in python : # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if head is not None: # print(head.next) will automatically tell if it has # cycle or not. so use it to get answer... # it prints as Error - Linked list has cycle a = str(head.next) if a[0] == "E": return True return False
Wow that was great explanation you just did, I really appreciate it neetcode for what your doing I know you work also it can be hard making these sort of videos with great visual solution.
@NeetCode a more intuitive way to understand this by taking a real world example i.e., an analog clock. The seconds hand moves faster than the rest but because all hands move in a circle...they are bound to converge at certain point in time.
Those who know physics just imagine this in terms of relative velocity( i know this sounds wierd 😅 but trust me). So the fast pointer have a velocity of 2 and slow have a velocity of 1. Now imagine you are sitting on the slow pointer. Then the fast pointer is travelling at a relative speed 2-1 = 1. So if it is a cycle, the fast pointer will move at a speed 1 and eventually collides you. If it is not a cycle the fast pointer just moves away from you at a speed 1. Let me know if you find this usefull
Great explanation, I feel like the coding portion really avoided some odd edge cases and made it seem simpler than it is. For example, we started the pointers at the same point and then updated the pointers first instead of at the end of the loop.
The intuition for this algo is literally so simple. Imagine you're running on track with a friend who always runs faster than you. Eventually, you'll always find your friend catching up to you from behind if the track is a circle
I think its not that simple since most people get caught on the idea of “what if the fast one jumps over the slow one without hitting the slow node” but about 2 seconds of thinking should be enough to get past that so idk why he spent so long on the intuition part of this vid
perfectly articulated explanation. Thanks much ! I could only think of a hashMap solution - but the hare and tortoise pointer approach is much more efficient.
I used an in-place replacement method. I believe this passes the O(1) argument and seems more efficient, but this approach seems better if we have to maintain the original input list (which is probably desired in most applications anyway).
This is not Leetcode, this is "Neet" code. Excellent! Would have loved it if you could have also added how to find the node of the loop start which is what 142. Linked List Cycle II is asking us to find.
Great explanation! Although since the problem doesnt state that we are not allowed to manipulate the linked list, we can just change all the vals to None as we see them and check if the val is None to determine a cycle. This obviously wouldnt work if the input had nodes with vals of None though.
With the first approach you can simply edit node values to something unique, so if you encounter your unique value again it means you detected a cycle. O(n) time O(1) space.
Since there were no rules against modifying the original linked list, my approach was to actually move through the linked list and reverse the list as I traversed it. I only had to store a single node in a hash map (the original head) so the memory complexity was O(1). Once you move through a cycle all the nodes you encounter after the cycle are now reversed so the path will take you back to the original head and you can return true if you find a match against the single node in the hash map, otherwise false if you encounter NULL.
You mentioned at the beginning of the video that you already completed a problem already similar to this - which video/topic is that? The "Finding a duplicate number" video?
I’m not sure if my solution is best practice but instead of using hashing I just set the value of visited nodes to be a value outside of their specified range. Then, if node.next’s value was equal to this “visited” value, there was a cycle. If it doesn’t reach any visited nodes there is no cycle and it returns false. My submission was faster than 96% and better memory than 98% roughly
i just used a map to save the nodes address as a string, so if node.next's address is already in the map its a cycle, not as fast as this but its still O(n), just uses more memory
Why do we moved the fast pointer by 2 instead of another number? Does moving the slow pointer by 1 and the fast pointer by 2 always ensure that we can catch a cycle if there is one?
here's an O(1) runtime solution. Problem said there's a max of 10000 nodes, so... def hasCycle(self, head: Optional[ListNode]) -> bool: #edge case [] if not head: return False curr = head for i in range(10001): if not curr: return False curr = curr.next return True O(10001) = O(1)
I see that the solution uses a .next is anyone else having trouble getting the .next to work? I tried next(next(fast)) but that doesn't work because the first next converts the type from list to integer. I have also converted the input list: head = iter([3,2,0,-4)]
Hey....... you have great teaching skills... please create a separate array and string playlist....... also which s/w you use for drawing explanations.
if fast & slow start at different node, and the fast pointer move 3 or 4 or 5 times faster than the slow pointer. I found that in some cycle structure, the two pointers will never meet, why is that? Thanks in advance.
if slow pointer and fast pointer are closing its gaps by 1 due to fast pointer moving twice as fast as the slow pointer, then can't i just make the fast pointer three times as fast so that its closing the gaps by 2? or does this make the solution invalid somehow?
Good question. The reason why we're doing fast.next.next and slow.next is because we want the two variables to 'meet' with each other. If you do fast.next.next.next, then we are going to skip over slow pointer and conduct additional iteration until it later meets at a different location. Hope this makes sense.
No one on their own will ever think that the best way to do that is to presume the pointers collide, that's absolutely insane reasoning for an "Easy" problem. Couldn't you just have 2 pointers one ahead of the other, and if the ahead pointer is ever behind the behind pointer (by checking the `pos` which they claim is a node attribute index value) then it's a loop? That seems much more intuitive and sane use of two pointers, but I see how this insane theory-based one is the only solution for not having some comparable index value (but then I mean, could you not cast the nodes to an array and just make an index value anyways?)
hi,i have written a code for this where i'm calculating the address of the values in a list(these addresses should be unique if there is no loop and repeat if there is a loop in the linked list)but this code passed 16/20 test cases and i debugged the code but not able to find where the error is!can anyone help me out! def hasCycle(self, head: Optional[ListNode]) -> bool: while head: if id(head.val) in a: return True a.append(id(head.val)) head=head.next return False
This is it here def middleNode(self, head): """ :type head: ListNode :rtype: ListNode """ slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
💡 LINKED LIST PLAYLIST: ua-cam.com/video/G0_I-ZF0S38/v-deo.html
@NeetCode can you solve binary tree cameras a dp question next? TQ
This guy is insane, he is helping a whole bunch of people getting new jobs and understanding algo than anyone ever. He deserves the best.
I've seen Floyd's Tortoise & Hare algorithm many times and have taken it for granted. This is by far the best explanation of why it works and why it's O(n) time. Many thanks to Neetcode!
The explanation of the Floyd's Tortoise and Hare algorithm was amazing!
Thanks, explaining the slow pointer increases the distance by 1 and the fast pointer decreases distance by 2 shows how the distance is always decreasing by 1 so fast will never overtake!
Thank you so much!
unless it overtake by surpassing the slow pointer in this case it might take more than 1 cycle right?
Explaining how it always evaluates to O(n) is really helpful.
hands down best leetcode youtuber
It's crazy. To undderstand Floyd's Tortoise and Hare, I watched a lot of videos on UA-cam but it couldn't work and I gave up. Today, I was solving Leetcode 141 problem and to find a solution with space O(1), I watched it and wow... There were already lots of times 'WOW' while watching neetcode' videos, but wow... 10-(2-1), n-1.. this guy got me understand this. just with two lines. Crazy. I learn a lot from your videos, not only algorithm...
Please keep posting solutions like this, they are really helpful
Great solution!
I found one that is simpler, although might be considered the "easy way out".... If you set each node's value to None/null/undefined (depending on the language), then you can just check for if the current node is undefined in the loop. This solution is slightly faster than the slow/fast pointer method:
class Solution(object):
def hasCycle(self, head):
if not head: return False
while head.next:
if head.val == None: return True
head.val = None
head = head.next
return False
Great solution:
1. Altering source linked list is not idael in a real time scenario, unless the arg passed is already a deep copy of the original linked list and not just a shallow copy.
2. If we had to create a deep copy ourselves, it'll add up to the memory utilised by our solution.
@@Jesseiceheart In C/cpp, by specifying const to the list passed, the function will return with an unaltered list. Is there a way to do this in python?
bool hasCycle(const head){}
Always love your videos. I've been working hard on LC problems for the last 10 days and I always come to these videos when I get stuck or would love to learn a clean, concise solution.
to be technical, when you store an object like a Node in a dictionary in python we are storing the address in the dictionary/set. That is how we can be sure that we have not seen it before using the "hashset" approach.
Felt it was worth commenting.
BTW saw your video the other day about you working in Seattle at Google! well deserved. I love your content! You may look into becoming a CS teacher when you're burnt out working at major tech giants. haha keep them coming!
Thanks for telling us
Thank you! I was wondering how the objects were being stored in the hashset since the node objects themselves are not hashable, but now I see that their memory addresses are.
when you are doing the comparison of fast == slow, what exactly is happening? Are the memory addresses being compared in that way as well? If so, what is the difference between the comparison x == 5 where x is 5 and fast == slow? How does Python know to compare memory addresses for fast and slow and actual values for x == 5?
chatgpt answer to my question, let me know if it's correct:
In Python, the comparison x == 5 is different. It compares the value of the variable x (which is 5) with the value 5. Python knows that x is an integer, so it compares the integer value directly.
However, when it comes to objects in Python, such as the ListNode instances in the linked list, the comparison slow == fast compares the memory addresses of the objects. It checks whether slow and fast are referring to the same object in memory, rather than comparing the contents of the objects.
@@sujal1548 good question, I'd love to know how it works in JavaScript as well. Not sure if we should trust gpt on this one
"Given Head" lmao these leetcode prompts are juicy
That 10 + (1-2) example really did it. Thanks bro
Honestly, this is a technique anyone should not miss..it just makes the whole problem easy to solve.Thanks NeetCode
@neetcode is goated! I was having a hard time with some of the previous linked list questions in neetcode 150 but with this one I was able to solve it first by using a hashSet and then did the follow up once I saw someone mention tortoise and hare's algo because i assumed it had to mean slow and fast pointers if memory complexity was O(1). I feel like with a lot of the leetcode questions you keep getting beat up until eventually some of the topics 'click' and then you finally start seeing the fruits of your labor! Thanks neetcode you're the man 🙏
Thanks for explaining so well.. 😊
Thank you 🙏
best explanation for the Tortoise and hare algorithm i have seen so far, thanks
every time brings a whole new concept to learn. grateful for that
Thank god this is such an amazing explanation!!! AS ALWAYS!!!
I didnt understand this algorithm for legit a year until today. Thank you.
Amazing explanation on why it's linear time! Thank you!!
Those who have studied relative motion can easily understand it,taking slow to rest then the fast will meet the slow that is at rest
Here is another easy but O(1) memory solution with only one pointer.
We can take advantage of the fact that: (-10**5
Thank you for solving the problem with first brute force and then with the optimised solution.
Thanks!
respects to the insane creative brain that came up with this AND TO YOU for presenting it in such an awesome way!!
Thank you man, as soon as you mentioned two pointers it just clicked for me. Thank you!
hands down the best explanation/proof of the Floyd's Cycle Detection Algorithm
Sigma solution - print function in python :
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is not None:
# print(head.next) will automatically tell if it has
# cycle or not. so use it to get answer...
# it prints as Error - Linked list has cycle
a = str(head.next)
if a[0] == "E":
return True
return False
Wow that was great explanation you just did, I really appreciate it neetcode for what your doing I know you work also it can be hard making these sort of videos with great visual solution.
Brilliant solution! Thank you for creating this video!
@NeetCode a more intuitive way to understand this by taking a real world example i.e., an analog clock. The seconds hand moves faster than the rest but because all hands move in a circle...they are bound to converge at certain point in time.
Best explanation for why floyd algo works
Those who know physics just imagine this in terms of relative velocity( i know this sounds wierd 😅 but trust me). So the fast pointer have a velocity of 2 and slow have a velocity of 1. Now imagine you are sitting on the slow pointer. Then the fast pointer is travelling at a relative speed 2-1 = 1. So if it is a cycle, the fast pointer will move at a speed 1 and eventually collides you. If it is not a cycle the fast pointer just moves away from you at a speed 1. Let me know if you find this usefull
I loooove the way you explain things. Make them so much easier
Great explanation, I feel like the coding portion really avoided some odd edge cases and made it seem simpler than it is. For example, we started the pointers at the same point and then updated the pointers first instead of at the end of the loop.
An explanation I can actually understand 😅
Thanks!!
The intuition for this algo is literally so simple. Imagine you're running on track with a friend who always runs faster than you. Eventually, you'll always find your friend catching up to you from behind if the track is a circle
I think its not that simple since most people get caught on the idea of “what if the fast one jumps over the slow one without hitting the slow node” but about 2 seconds of thinking should be enough to get past that so idk why he spent so long on the intuition part of this vid
Fantastic visualization as to why the 2 offset pointers work
The most valuable part to me starts from 8:20.
Great explanation. I wasn't understanding the second method, but you explained it perfectly
perfectly articulated explanation. Thanks much !
I could only think of a hashMap solution - but the hare and tortoise pointer approach is much more efficient.
excellent explanation on why slow and fast eventually meet each other
Something about your pronounciation just makes me understand the topics;) Keep up the great work!
I used an in-place replacement method. I believe this passes the O(1) argument and seems more efficient, but this approach seems better if we have to maintain the original input list (which is probably desired in most applications anyway).
Very clear and detailed explanation, thanks a lot!
You blowed my mind with fast and slow pointer technique
Best explanation of why runner catches up with walker!
Nice video! The proof was super helpful.
Great Explanation, you are the best teacher for coding solutions🙏🙏
You’re the real MVP man!
Thanks
This is not Leetcode, this is "Neet" code. Excellent! Would have loved it if you could have also added how to find the node of the loop start which is what 142. Linked List Cycle II is asking us to find.
I have managed to solve it with a hash map but this is a much elegant solution. Thanks for the video.
Eureka effect on steroids. Thanks so much for posting these, they really help A LOT!
Hands down best youtube channel.
Thanks man just wanted to see how you coded it out, you the man! Liked
Oh thanks that really help a lot 8:06
I just pointed the "next" of all the visited nodes to my dummy node. As soon as I hit the one that has a "next" of my dummy, I know that's a cycle.
clever
i never really comment on ytb videos but this was so well explained
that I simply have to commend you for this
great explanation!!
amazing explanations sir, did not understand this algo before but you made it pretty easy
Awesome....I like the way you explain ...very clean and easy way...pls keep posting ..thank you!!
Great explanation! Although since the problem doesnt state that we are not allowed to manipulate the linked list, we can just change all the vals to None as we see them and check if the val is None to determine a cycle. This obviously wouldnt work if the input had nodes with vals of None though.
With the first approach you can simply edit node values to something unique, so if you encounter your unique value again it means you detected a cycle. O(n) time O(1) space.
NOW THAT IS WHAT IS AN INTUITIVE EXPLANATION ❤🙏🙏👍
Super helpful and amazing explanation! Thanks so much!
Since there were no rules against modifying the original linked list, my approach was to actually move through the linked list and reverse the list as I traversed it. I only had to store a single node in a hash map (the original head) so the memory complexity was O(1). Once you move through a cycle all the nodes you encounter after the cycle are now reversed so the path will take you back to the original head and you can return true if you find a match against the single node in the hash map, otherwise false if you encounter NULL.
Did the same, yet you don't need a hashmap to store the list's head, just save a pointer to it
@@evgeniyazarov4230 good point!
you shouldnt unless stated otherwise
Cystal clear explanation, thanks a lot!
You mentioned at the beginning of the video that you already completed a problem already similar to this - which video/topic is that? The "Finding a duplicate number" video?
I’m not sure if my solution is best practice but instead of using hashing I just set the value of visited nodes to be a value outside of their specified range. Then, if node.next’s value was equal to this “visited” value, there was a cycle. If it doesn’t reach any visited nodes there is no cycle and it returns false. My submission was faster than 96% and better memory than 98% roughly
i just used a map to save the nodes address as a string, so if node.next's address is already in the map its a cycle, not as fast as this but its still O(n), just uses more memory
Why do we moved the fast pointer by 2 instead of another number? Does moving the slow pointer by 1 and the fast pointer by 2 always ensure that we can catch a cycle if there is one?
Next level explanation Dude..!! Just loved it :D
omgg, Neetcode you're the legendary !!!!!
Great explanation! Thank you. Could you kindly do a similar awesome explanation for leetcode 142 Linked List Cycle II ?
Thanks for all the explanations!
here's an O(1) runtime solution. Problem said there's a max of 10000 nodes, so...
def hasCycle(self, head: Optional[ListNode]) -> bool:
#edge case []
if not head:
return False
curr = head
for i in range(10001):
if not curr:
return False
curr = curr.next
return True
O(10001) = O(1)
I see that the solution uses a .next is anyone else having trouble getting the .next to work? I tried next(next(fast)) but that doesn't work because the first next converts the type from list to integer. I have also converted the input list: head = iter([3,2,0,-4)]
i also would like to know
That was a great video tutorial about the topic, thank you!!!!
Hey....... you have great teaching skills... please create a separate array and string playlist....... also which s/w you use for drawing explanations.
There is a problem if you use hashset because, we will have to override the hashcode method for the ListNode custom class which is created.
if fast & slow start at different node, and the fast pointer move 3 or 4 or 5 times faster than the slow pointer. I found that in some cycle structure, the two pointers will never meet, why is that? Thanks in advance.
Can't we use Valid palindrome solution here? Like using Two pointers but in polar opposite nodes/ pointers? Then checking if l = r?
if slow pointer and fast pointer are closing its gaps by 1 due to fast pointer moving twice as fast as the slow pointer, then can't i just make the fast pointer three times as fast so that its closing the gaps by 2? or does this make the solution invalid somehow?
Good question. The reason why we're doing fast.next.next and slow.next is because we want the two variables to 'meet' with each other. If you do fast.next.next.next, then we are going to skip over slow pointer and conduct additional iteration until it later meets at a different location. Hope this makes sense.
Best explanation on the planet
man you are a fuckin' genius. Thanks for the videos. Really helpful🙏
If i dont want to use a different class, how can i incorporate the next function and also use the head? Otherwise, amazing explanation!!
this man is the GOAT
Thanks. Learn something new here.💌
This explanation is sooooooooooooooooooooooooooooooooo ammmmmmmmmmmmmmmmmmmmmaaaaaaaaaaaaazing. Thank you very much!!!
Thanks for your helpful explanation ! Could you explain Linked List Cycle II in the next video?
No one on their own will ever think that the best way to do that is to presume the pointers collide, that's absolutely insane reasoning for an "Easy" problem. Couldn't you just have 2 pointers one ahead of the other, and if the ahead pointer is ever behind the behind pointer (by checking the `pos` which they claim is a node attribute index value) then it's a loop? That seems much more intuitive and sane use of two pointers, but I see how this insane theory-based one is the only solution for not having some comparable index value (but then I mean, could you not cast the nodes to an array and just make an index value anyways?)
hi,i have written a code for this where i'm calculating the address of the values in a list(these addresses should be unique if there is no loop and repeat if there is a loop in the linked list)but this code passed 16/20 test cases and i debugged the code but not able to find where the error is!can anyone help me out!
def hasCycle(self, head: Optional[ListNode]) -> bool:
while head:
if id(head.val) in a:
return True
a.append(id(head.val))
head=head.next
return False
Hey thanks for the video it is helpful. Can you please do leetcode 142 as well? ideally use the same technique. Thanks a ton.
This is it here
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
@@jideabdqudus I kinda wanted the reasoning behind it but now I figured it all out :)
Thanks a lot.
I would appreciate if you can tell me the tool you are using for drawing.
Thank you so much! It helped a lot!
I did this and the second version of this where we have to return the node by using hash table
Any idea on cleaning up a looped linked list? I ended up double free'ing on the loop.
the explanation is really awesome
lol this was one of my exams and I blanked. Thanks