Find the Duplicate Number - Floyd's Cycle Detection - Leetcode 287 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@nithishthomas1514]

Can't you just use sum of arithmetic progression to find the ans quicker? 1,2,3,4,2 If there were n numbers in range 1 to n their sum would be n×(n+1)/2 = 10. Actual sum = 12 12- 10 = 2 1,2,3,3 =9 n*(n+1)/2 = 6 9-6 = 3

[@hhcdghjjgsdrt235]

@@nithishthomas1514 ha ha ha ha

[@onkarsingh-vu1ds]

@@nithishthomas1514 was my 1st intuition too. I even submitted the code with this solution. Maybe the language in the question is ambiguous. The input can be [2,2,2,2,2] or [1,2,3,2,2]

[@leventoz9530]

@@onkarsingh-vu1ds It says there are n+1 numbers from 1-n and only one repeated number, so all numbers from 1 - n must be present, plus the extra. @nithishthomas1514 appears correct.

[@leungcheng4086]

@@leventoz9530 This problem now actually have a testcase that the input is [2,2,2,2,2] although this is contradict to the problem description. I know that because I tried to submit with this solution lol

[@rajeshseptember09]

That's right. Even Floyd wouldn't have resolved this problem in 30 minutes. It goes on to say that given the nature of such requirements in an interview, certain solutions are best memorized so that you could use them in a different situation or if the same problem comes up again.

[@JihChiLee]

This is the best video of explanation of Floyd’s algorithm I have seen so far…

[@MichaelButlerC]

This guy is seriously awesome 😎

[@shelllu6888]

Your 1min introduction on this problem literally cracked up me :D Never think of saltiness can turn into such a fun intro. Will probably remember this problem and how to solve it for a long time :D Thanks for making this video!

[@DanielRodrigues-bx6lr]

I'll also always remember it because JomaTech made a meme video on it, and I tried learning it after that but failed miserably. Then NeetCode explains it flawlessly in one video. xD A great teacher can make all the difference.

[@epsilonator]

I absolutely love the fact that you code the solution right in front of us while explaining it, whereas other coding KZbinrs just show their already written code which sometimes becomes difficult to understand. Thanks a ton for your awesome videos

[@alganyagiz8301]

agreed, it's way easier to understand code as its being written, even though it's entirely psychological lol

[@dpsingh_287]

@@alganyagiz8301 yeah it's like we see it step by step how the logic is built and code is written

[@leungcheng4086]

Thank you so much for the video of clear explaination! For the graph starting from 2:32, I think the outgoing pointer from node 0 should point at node 1 first. And then node 1 will point to node 3. Skipping the node that is pointed by 0 will struggle at the situation that element in 0 index is already the anwser. At last, really thank you for creating great website needcode with good videos of the explaination of solution!!

[@allenlam5210]

Was thinking the same thing!

[@shir35303]

My exact thoughts

[@alpha_gator360]

+ 1 to this, i got confused for a bit because of this, glad to get confirmation.

[@akankshasharma7498]

GOAT explanation. Everyone advised me to just memorize the algorithm, you're the only person to explain it to me.

[@joeycopperson]

That proof explanation was very good.. Even other big channels have failed to do it so smooth. thanks

[@apyyymnmn3442]

The proof isn't 100% right as he takes for granted that fast and slow will intersect though. But apart from that, everything was great

[@joeycopperson]

@@apyyymnmn3442 I guess he demoed it at 7:27 but maybe you're looking for mathematical proof?

[@birukabza]

@@apyyymnmn3442 He did prove it in linked list cycle video

[@asdfasyakitori8514]

I like the fact that you disliked this problem

[@interviewprep6827]

This is the only explanation of Floyd's algorithm that I could understand... Thanks for this video...

[@IshithaN]

This code s not working

[@MohitKumar-dy3ep]

​@@IshithaNhe wrote fast[nums[fast]] just change it into nums[nums[fast]] then the code will work fine

[@ajskjub5171]

man you saved my day.. everyone was talking about how there should be slow and slow2 pointers in phase 2 but no one actually explained what is background story for this.. thanks a lot you are my hero :)

[@Alzmerch]

I believe the head node at 2:35 should be 1 and not 0. 1 --> 3 --> 2 4. This may cause confusion for others, thought I'd point it out.

[@guosun8090]

I agree with you. The head node is confusing

[@osamaahmad8113]

I was losing my mind tryna understand why the headnode was 0. LOL thanks

[@shellyyang1916]

Actually, it should be 0 --> 1 --> 3 --> 2 4, so Neetcode forgot to draw the node "0", which is never reached. Because notice now slow and fast are starting from 0, rather than nums[0]. Hence, in the first step, slow will become 1, and fast will become 3. If they both starts from "1", then at the first step, slow will goes to 3, and fast will goes to 2, which would not work.

[@shdnas6695]

@@shellyyang1916 why 0 1 3 2 4. Why this sequence? i mean the initial give was 1 3 4 2 2, so how it became 0 --> 1 --> 3 --> 2 4 :)

[@vroomerlifts]

Yes, I had been staring at the screen for quite some time and was searching for this.

[@RM-bg5cd]

These are the kind of questions that piss me the fuck off. if you get this question in an interview and missed out on class it's GG Thank you for your explanation as always though, this channel is a gold standard

[@tesuji-go]

If someone submitted Floyd's algorithm in a PR I'd ask for them to be removed from the project. There is clever and there's batshit and Floyd's is batshit. Asking questions to test how people deal with graph theory is very different from asking for solutions only a crazy person would use. Are you telling me you guys are crazy and I should thank you for your time and leave? Stop hazing people. It's illegal in college it should be illegal in software interviews.

[@RohanRambhiya]

You know what when you said that it is very difficult to solve this in 30 mins even for the person who invented the algorithm made me relief. Thanks

[@funkyphyllo7150]

Another way to think about Floyd's: (1) by the time "slow" enters the cycle ( slow=p), "fast" is p-many steps into the cycle. (2) in order to intersect, fast needs to catch up by (c-p) steps, so now both are (c-p) many steps into the cycle, and therefore p-many steps away from beginning of cycle ** let c be the length of the cycle (3) Therefore, iterating once each from the head and the point of fast-slow intersection, will guarantee that the two meet, and that they meet at the entry point to the cycle

[@unmeshchougule5666]

Kudos! No one explained the algorithm better than this, thank you so much

[@bharathithal8299]

Great solution and explanation but there's a small mistake in the linked list diagram. The first element is actually 1 and not 0. Great work, thanks a lot!

[@The6thProgrammer]

Yes and no. While you are correct that 1 should appear in the linked list visual, I think it should be (0)->(1) at the beginning because the 0 node is technically our head (always) that no other node will ever point to. When we are setting slow and fast to 0 we are basically starting at the head. This makes it clearer to think about conceptually since we can consider fast and slow as starting together on node 0. Otherwise it is unclear in the linked list visual where fast and slow begin.

[@surajthapa5808]

@@The6thProgrammer please can you also explain how fast =num[num[fast] is increasing by 2 position at a time.

[@AbdulAziz-fp3hz]

Hands down, this is the best explanation I’ve found regarding Floyd’s algorithm.

[@anshaneja804]

Your explanation was very clear, easily understandable. Thank you

[@sulinPL]

Thanks for breaking this down! I managed to crack it in time and space O(n) by myself, but space O(1) was a head-scratcher. Gayle McDowell’s "2.8 Loop Detection" in Cracking the Coding Interview had me thinking I needed a secret decoder ring. Found it here, and now I can finally put away the flashcards!

[@tanoybhowmick8715]

Difficult problem, hard to solve without prior experience on it. Thank you so much.

[@kevinwang8632]

11:30 In the proof, the fast pointer was equal to P + 2c - x, but isn't that assuming the fast pointer only loops over the cycle once?

[@Abc-lr4bf]

wow bro you are so brutally honest and feels so nice to watch your tutorial

[@AnonYmous-yu6hv]

You're right, I don't know why would anyone ask this question, nobody will know it unless they have super memory and saw it already and this doesn't let you learn anything about the interviewee.

[@andreacucchietti1772]

To understand better Floyd's algorithm I came up with an example that I think is cool and I wanted to share. Think as the slow and fast pointers as two runners and each step of the slower as a meter. The second runner B is twice as fast as the first runner A. They start from the same point and they reach the zero of a circular track running. We can count the meters in the circular track in positive meters clockwise and negative anticlockwise. The distance between the starting point and the track is X. So, when A reaches the track, B is already X meters in. They keep running and B is going to complete 2 cycles when A completes the first. When A has X left, then B is going to have 2X left because he is twice as fast. Since B started at X, when he has 2X left, he is in -X, so he is at the same point as A when A misses X meters! To get to the start we have just to move of X steps at A pace.

[@Kuma117]

Honestly, blows my mind how companies expect anyone to derive this relation without having seen it before.

[@harpercfc_]

Very clean and understandable explanation. I would rewatch it for more times. Thank you for your great work!

[@johnpaul4301]

Football fans are code monkeys too now. Hazard is finished btw

[@yskida5]

Up the blues

[@vijayschadalavada]

This is one hell of a tricky problem. I did it with hashset and thought I'm done but I'm not. Appreciate your explanation. Very intuitive. I had re-watch to understand better.

[@astik2002]

hey can you explain me how fast = nums[nums[fast]] is moving two times? its clearly just one step ahead of slow pointer which is slow = nums[slow]]

[@洪子軒北科大]

@@astik2002 the default value of slow, fast is 0, which is a default pointer point to the first element in the nums array. each value in the nums array is a pointer to next position (value 3 means point to index 3, value 2 means point to index 2), not the adjacent position. the next position may be adjacent position, may not. so nums[fast] moves fast pointer to the next position, nums[nums[fast]] move fast pointer to the next position again. compared with slow = nums[slow], which just move slow pointer to the next position one time.

[@finemechanic]

Great explanation of everything starting with why it is a linked list and why it has to have a cycle and ending with the Floyd's algorithm.

[@faiqito6987]

you know its a beautiful algorithm when the code for it is so simple

[@clintondannolfo714]

Had to re-watch this to get the mathematical proof, thanks for the great explanation!

[@ajitham5975]

Its safe to say, subscribing to neetcode is kinda the best decision I've ever taken in my life.

[@jkyu2701]

I don’t like this type of interview problems either but have no choice but to solve it to get prepared. Big Thanks for your great video, it helped a lot❤

[@AnshViswanathan]

Never understood this problem until I watched this. Thank you!

[@chetansingh2901]

whenever i fall in a frenzy over a leetcode problem....i just google it's neetcode solution. Great explanations man.

[@aadityakiran_s]

Very well explained. Thank you. It's pretty simple if you've already seen it. You're right. I also learnt a lot form the other solutions posted on LeetCode.

[@krishankantray]

I got this problem in my interview and the interviewer asked me to explain why this algo works, basically prove it

[@johnpaul4301]

What company? Google?

[@shrayesraman5192]

I mean if you have seen this before then it's not too bad but if you haven't they don't want you.

[@Emorinken]

This question looks so complex only for the code to be so easy, thanks man

[@parulagrawal635]

Loved the explanation:) Perhaps the cleanest explanation I've seen so far

[@bigbigdog]

I was asked this question during a tech screen. Was not able to figure it out on my own and I ended up doing the sorting solution.

[@il5083]

Wonderful explanation. Minor correction, if the cycle is small the fast pointer might have go though more than two cycles. So the more general equation is p = nc + x where c >= 0 They will still meet at the start of the cycle. The case in the video is easier to understand, though. I wouldn't figure this out with out the simpler case.

[@asdfasyakitori8514]

He did mention it at 13:30

[@il5083]

@@asdfasyakitori8514I may skipped to the coding part, thanks.

[@prakharkapisway8834]

Thanks@@asdfasyakitori8514 , I was also having the same doubt .

[@JamesGourley-u7p]

Such an excellent explanation of Floyd's algorithm - thank you NeetCode!

[@damandeepdhillon4592]

Best explanation for A solution. Respect.

[@smilejayden-553]

In [1,3,4,2,2] example, the digram omitted the node “1”. Except that, it is very good explaining! Thank you very much 🙂

[@shenbomo]

I think it is correct as is, there should be no node "1", since he has mentioned that to use the value as the index position for the pointer, and nums[0] is 1, and nums[1] indeed has the value of 3. He also has mentioned that because the integers start from 1 to n, and using any value of 1...n (non-zero) as index position will never give you nums[0] as a node in the graph.

[@brian4084]

Great video. In the Drawing Explanation, is there a mistake? Shouldn't it be 0 -> 1 -> 3?

[@fdk9913]

No, think about the first element(0) in the drawing explanation as the consistent point because the numbers in the list can only go from 1 to nth-index value. So, no way will any of the values point to 0 since it doesn't fall in with the requirements of the problem.

[@PauloTheDev]

I drew this multiple times and the only way this makes sense is if it is 0 -> 1 -> 3

[@tdx_1138]

About as good an explanation as possible for such a problem. Great job and subscribed!

[@tinymurky7329]

I will cry if I got this question in intervew

[@SaiyaraLBS]

i would've cried if i didn't know it before.. but after knowing it's easy. it's not a fair question though... but if it comes now it will be easy if you already know it

[@user-tk7sc4gz2v]

Great Explanation, modified to avoiding while True slow, fast = nums[0], nums[nums[0]] while fast != slow: slow = nums[slow] fast = nums[nums[fast]] slow2 = nums[0] slow = nums[slow] while slow != slow2: slow2 = nums[slow2] slow = nums[slow] return slow

[@mahletlulsegedyifru3465]

Thank you so much ! This is the best explanation of Floyd's algorithm

[@emtikucz1553]

for numbers it can be made much easier I think. 1) sum all 2) sum of 1÷n is: n*(n+1)/2 3) result = (sum all) - (sum 1÷n)

[@JonahDienye]

🤦🏾‍♂️

[@nikhil199029]

@@JonahDienye why fcaepalm? This seems correct

[@JonahDienye]

@@nikhil199029 oh yes! The facepalm was for myself, for not figuring this approach out. However, this approach does not work if a number is repeated more than once.

[@shubhammaurya3671]

but it will only work if number is repeated only once

[@juanmoscoso0]

numbers from 1-n aren't guaranteed to repeat

[@fcoatis]

Best Floyd´s explanation ever. I´ve been trying to get it since I´ve watched Joma´s video 'If Programming Was An Anime'

[@sensiblegobis]

Awesome video and explanation! Question regarding the original example diagram - should the first node be 1 and not 0 since you are using the array elements as node values rather than the indices of the elements?

[@kishoremohanavelu2968]

great explanation. Especially the maths explanation was really good!!

man, this is such a golden explanation

[@mr6462]

If the company I am interviewing for asks me to solve it in constant space, I would leave the interview right away.

[@stylisgames]

``` slow = nums[slow]; fast = nums[nums[fast]]; ``` This is absolutely wild. Took me so long to even figure out that each value is pointing to the value at that index which is how the linked list representation is built. This could've used more explanation.

[@vdyb745]

The best and clear explanation I have found on this algorithm so far ! Thank you !!!!!

[@IN-krude]

There is an easy way to do all this. Calculate the sum of N natural number as n(n+1)/2. Then, subtract this value from the sum of the array to get a duplicate number. This is O(n) with constant space.

[@HimanshuTradesForex]

Wont work ,as there are more than 1 duplicates

[@reqzonegaming7157]

In example through logic once we reached to the 3 in first while loop we reached 3 so why can't we directly return nums[3] which is answer 2. Please answer anybody.

[@rahulsbhatt]

The proof you made us understand is the best I will ever see for this algo. Thank you so much, man!

[@teamo8033]

Throwing my Cracking The Coding Interview in the trash... you are all I need

[@aks5739]

in one pass get sum of all elements of array . Say its S. if there suppose to be elements only from 1..n then sum of 1..n is n*(n+1)/2, say its T . S-T is answer.

[@nothingisreal6345]

I mean for loop detection it is useful. But could it be used for the general case to detect if an array of objects contains some duplicates?

[@algosavage7057]

And to be more accurate, I think it's better to initialize slow and fast with nums[0] instead with 0

[@niharbastia5740]

Amazingly explained ! God bless

[@rushikeshneelamsetty9693]

Hello @NeetCode, I have a different solution for this problem and I would like you to review it and tell me if it would be appropriate to use it in an interview. So the approach is, since there are integers only in the range 1 to n and only one element is repeated use the formula for 'sum of n natural numbers' i.e., n*(n+1)/2 and we can find n by nums.size() -1. After finding the natural sum and the total sum of the array and finding the difference between them would be the answer.

[@yskida5]

This was my approach as well, but I think the problem with this kind of solution is cases where a # is repeated several times, i.e. [1, 2, 2, 2, 3]. It's ambiguous which digit is causing the difference if we do not know the frequency of said repeated digit. I may be wrong tho, would love input from others

[@nikhil_a01]

@@yskida5 You're correct. If you code this solution on LeetCode it will fail the test case [2, 2, 2, 2, 2].

[@ianokay]

At 11:35 you say "Plus C again", but this is the most profound and mysterious part of the entire problem, and you just casually and flippantly throw that out there as if it's intuitive or known, while trying to intuitively explain the problem. You're trying to grant us intuition with a magical answer that reveals no intuitive understanding. 😬💡

[@mostinho7]

Done thanks Todo:- implement this and add notes Floyd’s algorithm uses fast slow pointers to detect the BEGINNING of a cycle in linkedlist. This identifies the node where the cycle begins. The algorithm is as follows: Do fast slow pointer, they will meet at some node if there’s a cycle. Then you make place a slow pointer at the start of the linkedlist and a slow pointer at where the fast and slow pointers intersected. The node where the two slow pointers intersect will always be the node that the cycle begins at.

[@ruxiz2007]

Thanks so much, to be honest for so many years I could not get this straight until watching this.

[@piyushraj8701]

Omg. It was just wow. No one can explain better now. Finally satisfied with Floyd explanation. Thanks a lot sir🙏🙏🙏

[@rajastylez]

I appreciate the brutal honesty at the start of this video lol.

[@학교-m5c]

The fast pointer is not guarranteed to loop twice if p is really long and c is short, it will loop more than 2 so the distance fast pointer travelled becomes P + nC - X, at which im lost

[@nw3052]

This explanation is definitely the best out there, but I didn't quite get the last point where p is really long and the fast pointer circled n times. For the math to work we need to have c multiplied by n/2 in the slow pointer part of the equation, but that would mean that the slower pointer travelled the cycle half the times of the fast pointer (n/2 times), which is not exactly intuitive.

[@princeofexcess]

There is a related problem that would only have one number repeating. This solution will work if only one number is repeating: Sum of n - 1 : (n-1) n /2 since for n it is n (n + 1) /2 For example in video: (5-1)* 5 /2 = 10 sum the loop = 12 12 - 10 = 2 The number that repeats is 2 I was thinking of totaling with ^ or | and using parity 1 2 3 = 2 odd 1 even 2 2 2 = 3 even I just feel like there must be a different way.

[@prammar1951]

WOW, really loved that proof. Never studied this in uni thanks for your help

[@onethousandtimes6294]

One thing that made me confused is when he say "the thing in index 0 is never gonna be part of the loop". Which is intuitively true until you actually realize that the duplicate number can be at the index 0. This means that the linked list representation will be a whole loop (Circle loop). And with the formula that is proven, they will have p of 0 and x of 0 which means it will return the first number (which will meet in other index).

[@deresel4874]

what a champ! Thanks for explaining this algo, i had trouble visualising the slow1==slow2 intersecting part.

[@iaamnew2060]

Hi, I was doing the algebra myself and I think you drew the graph wrong and then got the wrong p formula for proof Here is what I found: Graph should be 0 -> 1 -> 3 -> 2 ->

[@srikanthperne2057]

We can solve it in a much simpler way using indices: def findDuplicate(self, nums: List[int]) -> int: res = 0 for num in nums: if nums[abs(num)] < 0: res = abs(num) nums[abs(num)] = -nums[abs(num)] for i, num in enumerate(nums): if num < 0: nums[i] = -num return res

[@danafaiez3663]

I like that solution too but this solution modifies the array and the problem statement in Leetcode says "You must solve the problem without modifying the array ."

[@srikanthperne2057]

We can iterate over the array one last time and modify the -ve values back to +ve. That way the array remains unchanged.

[@fangzhengchen7620]

The intro makes total sense why I wouldnt never think this is a linkedlist problem

[@agustinconsolo8886]

In what other type of problems it would be useful to use floyd's algorithm?

[@nevermore7755]

It's like Leafy teaching me how to land a FAANG job. Respect!

[@supercarpro]

I like how you quickly removed the perimeter around the linked list

[@tomonkysinatree]

This is one of those things where I feel like LC just makes things stupid hard. In reality if you have a problem like this you'd just use O(n) memory 99.9% of the time and go the hashmap route. Great explanation but holy smokes this was difficult

[@abhijl]

Beautifully explained.

[@xiaoyangchen8483]

It is not true that the distance from the starting point to the cycle entrance and the distance from the intersection to the cycle entrance are the same. We can only make sure p = x + nC.

[@pranchalgupta2370]

best explanation without a doubt.

[@kartikeyamishra3964]

Incredible explanation man, thanks a ton

[@gxyxy1012]

I was able solve with cyclic sort. Easier to understand imo. i believe there's a medium article providing the 14 leetcode patterns (and cyclic sort is one)

[@MP-ny3ep]

Amazing explanation as always. Thank you so very much !!!

[@riteshsaha6881]

Thank you for helping me understand Floyd's algorithm.

[@bossmusa9075]

Indexes are nodes and values in those indexes are next pointers ( to indexes). That how it is linked list

[@sharaj4893]

thanks for clearing my doubt of how x will be same after 1st collison

[@matheusmenezes4702]

Thank you for this content!! The best explanation about this algorithm

[@aadil4236]

12:51 It should p === x. You said p === 0. But I got the point. Great explanation as always!

[@linli7049]

Fantastic explanation about the math proof of Floyd's algorithm!!!

[@rekhasrivastava5114]

Best Explanation I was having idea of Floyd algorithm but I was not clear about it. Your explanation clears my all doubt Thank You so much

[@johnpaul4301]

One thing I'm having a hard time to fully understand. How does returning the index work here? Like I don't understand how returning the index will give us the correct value since the question is asking for the value of the duplicate but we're just returning the index based on the graphs you drew

[@ЕленаДоманская-к5х]

You are really talanted in explaning complicated things, even I got it) Thank you

[@VivekKumar-ny8kv]

4:37 Linked List representation is for indices or values ?