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
@@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]
@@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.
@@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
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.
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!
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.
I absolutely love the fact that you code the solution right in front of us while explaining it, whereas other coding RUclipsrs just show their already written code which sometimes becomes difficult to understand. Thanks a ton for your awesome videos
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!!
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 :)
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.
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
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.
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!
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.
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
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!
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❤
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 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.
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.
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.
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.
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.
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?
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
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.
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
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).
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.
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.
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.
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
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
@@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.
Thanks for great explanation but the equation seems a bit wrong. Isn't it possible that the fast pointer does multiple iterations for the loop before it meets the slow pointer? Then eq would be slow=p+nc-x. (n iterations)Any thoughts?
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 ->
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. 😬💡
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
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 ."
Hi Neetcode, atfter googling for floyd's cycle detection algorithm, I am not agreed with your explanation of p = x. Actually it should be p + c - x = kc, where c is the cycle length and k is any integer, this equation means that the distance between the fast point and slow point after their first intersection will be always be constant and this distance is a multiple of c. So after resetting the slow pointer and move them both on 1 step pace, as long as the slow pointer enter the cycle, based on the nature of the cycle that any two points with the distance of kc will meet, the first intersection point of the slow pointer and the fast pointer after reset is the start of the cycle. I guess the only tricky part to prove this algorithm is that to prove the fast and slow pointers will meet in the cycle for the first intersection in the first place, that is there exists a point index i where X(i) = X(2i) in the cycle.It is just mathematical.
``` 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.
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.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
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
@@nithishthomas1514 ha ha ha ha
@@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]
@@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.
@@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
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.
This is the best video of explanation of Floyd’s algorithm I have seen so far…
This guy is seriously awesome 😎
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!
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.
I absolutely love the fact that you code the solution right in front of us while explaining it, whereas other coding RUclipsrs just show their already written code which sometimes becomes difficult to understand. Thanks a ton for your awesome videos
agreed, it's way easier to understand code as its being written, even though it's entirely psychological lol
@@alganyagiz8301 yeah it's like we see it step by step how the logic is built and code is written
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!!
Was thinking the same thing!
My exact thoughts
That proof explanation was very good.. Even other big channels have failed to do it so smooth. thanks
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
@@apyyymnmn3442 I guess he demoed it at 7:27 but maybe you're looking for mathematical proof?
@@apyyymnmn3442 He did prove it in linked list cycle video
This is the only explanation of Floyd's algorithm that I could understand... Thanks for this video...
This code s not working
@@IshithaNhe wrote fast[nums[fast]] just change it into nums[nums[fast]] then the code will work fine
GOAT explanation. Everyone advised me to just memorize the algorithm, you're the only person to explain it to me.
Kudos! No one explained the algorithm better than this, thank you so much
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 :)
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.
I agree with you. The head node is confusing
I was losing my mind tryna understand why the headnode was 0. LOL thanks
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.
@@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 :)
Yes, I had been staring at the screen for quite some time and was searching for this.
I like the fact that you disliked this problem
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
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.
Your explanation was very clear, easily understandable. Thank you
Very clean and understandable explanation. I would rewatch it for more times. Thank you for your great work!
Football fans are code monkeys too now. Hazard is finished btw
Up the blues
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!
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.
@@The6thProgrammer please can you also explain how fast =num[num[fast] is increasing by 2 position at a time.
Difficult problem, hard to solve without prior experience on it. Thank you so much.
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
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
Had to re-watch this to get the mathematical proof, thanks for the great explanation!
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!
you know its a beautiful algorithm when the code for it is so simple
About as good an explanation as possible for such a problem. Great job and subscribed!
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?
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❤
wow bro you are so brutally honest and feels so nice to watch your tutorial
Honestly, blows my mind how companies expect anyone to derive this relation without having seen it before.
Never understood this problem until I watched this. Thank you!
Such an excellent explanation of Floyd's algorithm - thank you NeetCode!
This question looks so complex only for the code to be so easy, thanks man
Loved the explanation:)
Perhaps the cleanest explanation I've seen so far
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.
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.
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.
Its safe to say, subscribing to neetcode is kinda the best decision I've ever taken in my life.
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.
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.
Great video. In the Drawing Explanation, is there a mistake? Shouldn't it be 0 -> 1 -> 3?
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.
I drew this multiple times and the only way this makes sense is if it is 0 -> 1 -> 3
Thank you so much ! This is the best explanation of Floyd's algorithm
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.
great explanation. Especially the maths explanation was really good!!
The proof you made us understand is the best I will ever see for this algo.
Thank you so much, man!
Throwing my Cracking The Coding Interview in the trash... you are all I need
I got this problem in my interview and the interviewer asked me to explain why this algo works, basically prove it
What company? Google?
I mean if you have seen this before then it's not too bad but if you haven't they don't want you.
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.
The best and clear explanation I have found on this algorithm so far ! Thank you !!!!!
whenever i fall in a frenzy over a leetcode problem....i just google it's neetcode solution. Great explanations man.
what a champ!
Thanks for explaining this algo, i had trouble visualising the slow1==slow2 intersecting part.
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?
If the company I am interviewing for asks me to solve it in constant space, I would leave the interview right away.
I will cry if I got this question in intervew
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
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.
He did mention it at 13:30
@@asdfasyakitori8514I may skipped to the coding part, thanks.
Thanks@@asdfasyakitori8514 , I was also having the same doubt .
Thanks so much, to be honest for so many years I could not get this straight until watching this.
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
Amazing explanation as always. Thank you so very much !!!
WOW, really loved that proof. Never studied this in uni thanks for your help
sooo good explanation, i watched a bunch of videos, until i landed on your video and got it
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?
Incredible explanation man, thanks a ton
I appreciate the brutal honesty at the start of this video lol.
You are really talanted in explaning complicated things, even I got it) Thank you
Amazingly explained ! God bless
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).
Best Floyd´s explanation ever. I´ve been trying to get it since I´ve watched Joma´s video 'If Programming Was An Anime'
Thank you very much, its a nice explanation. Thanks again for all the efforts you put into it.
man, this is such a golden explanation
In [1,3,4,2,2] example, the digram omitted the node “1”. Except that, it is very good explaining! Thank you very much 🙂
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.
Best explanation for A solution. Respect.
I like how you quickly removed the perimeter around the linked list
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.
And to be more accurate, I think it's better to initialize slow and fast with nums[0] instead with 0
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.
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
@@yskida5 You're correct. If you code this solution on LeetCode it will fail the test case [2, 2, 2, 2, 2].
The intro makes total sense why I wouldnt never think this is a linkedlist problem
Thank you for this content!! The best explanation about this algorithm
Thanks for the reassurement that this was a ridiculous question, it totally stumped me haha
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
Omg. It was just wow. No one can explain better now. Finally satisfied with Floyd explanation. Thanks a lot sir🙏🙏🙏
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
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 why fcaepalm?
This seems correct
@@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.
but it will only work if number is repeated only once
numbers from 1-n aren't guaranteed to repeat
Thank you so much for the wonderful explanation! Really liked it
It's like Leafy teaching me how to land a FAANG job. Respect!
What do you use to draw your work for the videos?
Fantastic explanation about the math proof of Floyd's algorithm!!!
Thanks for great explanation but the equation seems a bit wrong. Isn't it possible that the fast pointer does multiple iterations for the loop before it meets the slow pointer? Then eq would be slow=p+nc-x. (n iterations)Any thoughts?
Neetly explained! I'm bad with time complexities, I'd love for you to break down the time complexity as well.
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 ->
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. 😬💡
Thank you for helping me understand Floyd's algorithm.
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
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 ."
We can iterate over the array one last time and modify the -ve values back to +ve. That way the array remains unchanged.
Your Videos are so useful. ❤️
Great Explanation ! Thank you so much !
very nice and clear explanation really helpful for building logical mind thanks subscribed
Hi Neetcode, atfter googling for floyd's cycle detection algorithm, I am not agreed with your explanation of p = x. Actually it should be p + c - x = kc, where c is the cycle length and k is any integer, this equation means that the distance between the fast point and slow point after their first intersection will be always be constant and this distance is a multiple of c. So after resetting the slow pointer and move them both on 1 step pace, as long as the slow pointer enter the cycle, based on the nature of the cycle that any two points with the distance of kc will meet, the first intersection point of the slow pointer and the fast pointer after reset is the start of the cycle. I guess the only tricky part to prove this algorithm is that to prove the fast and slow pointers will meet in the cycle for the first intersection in the first place, that is there exists a point index i where X(i) = X(2i) in the cycle.It is just mathematical.
```
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.
The absolute best explaination I found on RUclips for Floyd's algo
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.
Beautifully explained.
Ah yes the "trivial" cycle linked list for a seemingly easy problem, this is why I suck so badly at LC style interview :(
What happens when we have array [2,3,1,4,2]. Since 2 is in index 0, it wont be at the start of the cycle right?
The index 0 won't be the cyclic point as the range number is between [1,n] inclusively, therefore, number '0' won't be mentioned again.
best explanation without a doubt.