Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - Python

[@NeetCode]

💡 LINKED LIST PLAYLIST: kzbin.info/www/bejne/fWHCemCQe5WGaZo

[@algorithmo134]

@NeetCode can you solve binary tree cameras a dp question next? TQ

[@joelbisponegrao9932]

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.

[@misterimpulsism]

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!

[@gayan1742]

Explaining how it always evaluates to O(n) is really helpful.

[@licokr]

It's crazy. To undderstand Floyd's Tortoise and Hare, I watched a lot of videos on KZbin 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...

[@juliuscecilia6005]

hands down best leetcode youtuber

[@sanjanar9198]

Please keep posting solutions like this, they are really helpful

[@seanmcelroy4074]

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!

[@NeetCode]

Thank you so much!

[@moewiseman1557]

unless it overtake by surpassing the slow pointer in this case it might take more than 1 cycle right?

[@ruzaikr]

The explanation of the Floyd's Tortoise and Hare algorithm was amazing!

[@rioredwards]

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

[@Jesseiceheart]

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.

[@louisuchihatm2556]

@@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){}

[@abhisekdash2864]

That 10 + (1-2) example really did it. Thanks bro

[@stormarrow2120]

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!

[@osmanmusse9432]

Thanks for telling us

[@cadenc.7368]

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.

[@sujal1548]

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?

[@sujal1548]

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.

[@BudetSvobodnoy]

@@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

[@Andres-dn8ze]

@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 🙏

[@adewumisunkanmi5593]

Honestly, this is a technique anyone should not miss..it just makes the whole problem easy to solve.Thanks NeetCode

[@TenzDelek]

every time brings a whole new concept to learn. grateful for that

[@McBritish]

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.

[@omarllama]

Here is another easy but O(1) memory solution with only one pointer. We can take advantage of the fact that: (-10**5

[@gwtuts4061]

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

[@SiddharthRanjan6197]

@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.

[@_ipsissimus_]

"Given Head" lmao these leetcode prompts are juicy

[@tomonkysinatree]

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.

[@taco564]

Amazing explanation on why it's linear time! Thank you!!

[@emmanueltemiede6197]

best explanation for the Tortoise and hare algorithm i have seen so far, thanks

[@bandhammanikanta]

Thank you for solving the problem with first brute force and then with the optimised solution.

[@devin3944]

Fantastic visualization as to why the 2 offset pointers work

[@ankitdubey5045]

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

[@daniyalkhawaja1913]

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).

[@pedroalonsoms]

excellent explanation on why slow and fast eventually meet each other

[@juliramoos]

I loooove the way you explain things. Make them so much easier

[@rajeshseptember09]

perfectly articulated explanation. Thanks much ! I could only think of a hashMap solution - but the hare and tortoise pointer approach is much more efficient.

[@adarshsasidharan254]

hands down the best explanation/proof of the Floyd's Cycle Detection Algorithm

[@nirupamsuraj1634]

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

[@sabba2_]

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.

[@altusszawlowski4209]

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.

[@wlcheng]

Brilliant solution! Thank you for creating this video!

[@bianchialex]

I didnt understand this algorithm for legit a year until today. Thank you.

[@CodingWithPrakash_]

Best explanation for why floyd algo works

[@JustinK0]

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

[@osmanmusse9432]

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.

[@ashkan.arabim]

respects to the insane creative brain that came up with this AND TO YOU for presenting it in such an awesome way!!

[@nghiavo6263]

You blowed my mind with fast and slow pointer technique

[@The6thProgrammer]

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.

[@evgeniyazarov4230]

Did the same, yet you don't need a hashmap to store the list's head, just save a pointer to it

[@The6thProgrammer]

@@evgeniyazarov4230 good point!

[@chrischika7026]

you shouldnt unless stated otherwise

[@sahilkassanjee802]

Great explanation. I wasn't understanding the second method, but you explained it perfectly

[@80kg]

Thank god this is such an amazing explanation!!! AS ALWAYS!!!

[@alpyldrm8448]

I have managed to solve it with a hash map but this is a much elegant solution. Thanks for the video.

[@natekrall2015]

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)

[@yinglll7411]

Thank you man, as soon as you mentioned two pointers it just clicked for me. Thank you!

[@saurabhkathar2374]

Great Explanation, you are the best teacher for coding solutions🙏🙏

[@vimalalwaysrocks]

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.

[@pranjalnama2420]

amazing explanations sir, did not understand this algo before but you made it pretty easy

[@musicgotmelike9668]

Something about your pronounciation just makes me understand the topics;) Keep up the great work!

[@UKMatt32]

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

[@gradientO]

Best explanation of why runner catches up with walker!

[@itstheguy17]

Very clear and detailed explanation, thanks a lot!

[@noobletify869]

An explanation I can actually understand 😅 Thanks!!

[@Emorinken]

You’re the real MVP man! Thanks

[@chaiben275]

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

[@Skadongle]

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

[@regnam503]

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.

[@NeilSharma-u5n]

clever

[@akermiyu]

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?

[@MacAndSwiss]

Nice video! The proof was super helpful.

[@wilsonwang8641]

The most valuable part to me starts from 8:20.

[@TransparentWorld1275]

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?

[@EduarteBDO]

if slow is increasing by 1 and fast by 2 that means the gap between the two is decreasing by 1, so it's guarantee that the gap will reach in n time because the biggest possible gap is n the length of the list

[@pjchen8605]

Super helpful and amazing explanation! Thanks so much!

[@效应多普勒]

Cystal clear explanation, thanks a lot!

[@alextech4881]

Eureka effect on steroids. Thanks so much for posting these, they really help A LOT!

[@Relqeds]

Awesome....I like the way you explain ...very clean and easy way...pls keep posting ..thank you!!

[@hemesh5663]

Hands down best youtube channel.

[@divyam1175]

Oh thanks that really help a lot 8:06

[@symbol767]

Thanks man just wanted to see how you coded it out, you the man! Liked

[@adityachache]

I did this and the second version of this where we have to return the node by using hash table

[@ianokay]

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?)

[@ManojKumar-if1jh]

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.

[@mfaani]

If slow goes 1 Fast goes 2 And slow goes first… And the whole cycle is n steps, then once fast gets ahead i.e. after its first step, then think of more as slow is already on its next lap. How many iterations does fast have to take? To match slow? n - delta Delta is 2 - 1 So if it was 10 steps it would be 10 - ( 2 - 1) If you actually think of fast getting ahead then fast well is always ahead. He purposely didn’t use ahead but said gap. But depending on how you think of it, it can be vague a bit…

[@chunkwanchan5503]

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.

[@Bhaskar5890]

Hey....... you have great teaching skills... please create a separate array and string playlist....... also which s/w you use for drawing explanations.

[@mohamedantar1249]

Best explanation on the planet

[@kaydeeinmy]

omgg, Neetcode you're the legendary !!!!!

[@NivAwesome]

I have a very easy solution, O(1) space complexity without slow and fast pointers: var hasCycle = function(head) { while (head) { if (head.val === (10 ** 5) + 1) { return true; } head.val = (10 ** 5) + 1; head = head.next; } return false; };

[@Ahmad_Al-Deeb]

Thanks a lot. I would appreciate if you can tell me the tool you are using for drawing.

[@sriramkrishnamurthy4473]

NOW THAT IS WHAT IS AN INTUITIVE EXPLANATION ❤🙏🙏👍

[@binup28]

Great explanation! Thank you. Could you kindly do a similar awesome explanation for leetcode 142 Linked List Cycle II ?

[@kirillzlobin7135]

This explanation is sooooooooooooooooooooooooooooooooo ammmmmmmmmmmmmmmmmmmmmaaaaaaaaaaaaazing. Thank you very much!!!

[@ikthedarchowdhury8947]

Can't we use Valid palindrome solution here? Like using Two pointers but in polar opposite nodes/ pointers? Then checking if l = r?

[@joeljerry1494]

Would there ever be a situation where the fast pointer always overshoot the short pointer so that they will never meet?

[@akshaibaruah1720]

i never really comment on ytb videos but this was so well explained that I simply have to commend you for this great explanation!!

[@BradleyWeston92]

Any idea on cleaning up a looped linked list? I ended up double free'ing on the loop.

[@jackchen5288]

Thanks for all the explanations!

[@samwilson4597]

this man is the GOAT

[@kmeenakshi2679]

Next level explanation Dude..!! Just loved it :D

[@RutvikPatel2611]

line 12, in hasCycle while fast and fast.next: AttributeError: 'list' object has no attribute 'next'

[@flatmapper]

Amazing explanations

[@furkan486]

Clean explanation

[@AliHassan-ec9nu]

thansk for such an awesome explanation.

[@samrobinson-isaiah-53v5]

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)]

[@helikopter1231]

i also would like to know

[@azatnurzhanuly7290]

That was a great video tutorial about the topic, thank you!!!!

[@Kazeys]

lol this was one of my exams and I blanked. Thanks

[@jamesmee7201]

The while loop executes if fast.next is not None. Why doesnt an error get throwing when we assigned fast to fast.next.next assuming fast.next.next is eventually going to hit None in a non Cycle list

[@mohamadilhamramadhan6354]

Thanks. Learn something new here.💌

[@akx_edits3374]

this floyd algorith is genius man