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
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.
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.
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!!
@@apyyymnmn3442 watch his linked list cycle video, he proved it there. basically slow always increases reverse distance between them by 1 and faster decreases it by 2, which basically means that every step the distance decreases by 1 and eventually faster will catch slow again
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.
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 :)
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
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.
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!
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.
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.
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.
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.
this would happen in cases that, p >> c, in this case the intuition is imagine expanding the cycle however many times it takes until c > p, i.e. if the cycle is 1->2->3->1, you could arbitrarily say that the cycle is actually 1->2->3->1'->2'->3'->1*->2*(etc)->1, this expansion would guarantee that the fast pointer only oops over "the cycle" once
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. 😬💡
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
great explanation, but there's a small bug, in your drawn cycle, it should start with 0 -> 1 -> 3, or you can start with 1 - > 3, but then slow and fast should both set to nums[0] initially.
I believe for this problem, its better to study the bit manipulation and binary search solution. As floyd cycle is not super intuitive in an interview setting.
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.
I think that a very important thing to note is that: - Zero MUST point to a number. - But NO number can point to zero - zero not included in boundaries of numbers - This guarantees that zero MUST be attached to a cycle where one number has two pointers - can't have full loop with last number pointing back to zero So we can confidently start our algorithm from zero every time.
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.
@@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.
Explanation for why this works even when the cycle is shorter than the beginning sequence: s is the start node cs is the start of the cycle p is the number of steps needed to reach cs from s c is the length of the cycle aka the number of steps to end up at the same node after doing a round in the cycle In one iteration the fast pointer fs makes 2 steps while the slow pointer sp makes 1 step 1. Finding the intersection in the cycle - sp reaches the beginning of the cycle after p iterations - at that moment fp has done p steps in the cycle (possibly having done multiple rounds) - let r be the number of rounds fp has done in the cycle and s the number of additional steps fs is into the cycle so that r*c+s = p - The number of nodes between fp and sp is given by c-s since sp is at the beginning of the cycle and fp is s steps into the cycle - This means that fp and sp will intersect after c-s iterations - Since c-s iterations means sp will do c-p steps the intersection will happen c-s steps into the cycle 2. Finding the beginning of the cycle - Now fp is ignored and a new slow pointer sp2 is placed at the start - sp2 will need p iterations to reach the start of the cycle - from fp we know that the p steps sp will do in the cycle result in r rounds and s additional steps - since sp is c-s steps into the cycle it will be at the start of the cycle p steps later - thus after p steps sp=sp2=cs
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
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 ."
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.
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
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
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.
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
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.
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.
🚀 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
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.
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 😎
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
+ 1 to this, i got confused for a bit because of this, glad to get confirmation.
GOAT explanation. Everyone advised me to just memorize the algorithm, you're the only person to explain it to me.
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
@@apyyymnmn3442 watch his linked list cycle video, he proved it there. basically slow always increases reverse distance between them by 1 and faster decreases it by 2, which basically means that every step the distance decreases by 1 and eventually faster will catch slow again
I like the fact that you disliked this problem
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
Kudos! No one explained the algorithm better than this, thank you so much
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.
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 :)
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
Your explanation was very clear, easily understandable. Thank you
Difficult problem, hard to solve without prior experience on it. Thank you so much.
Thankyou for the Humility toward us coders. God bless 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.
Had to re-watch this to get the mathematical proof, thanks for the great explanation!
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
Its safe to say, subscribing to neetcode is kinda the best decision I've ever taken in my life.
Hands down, this is the best explanation I’ve found regarding Floyd’s algorithm.
wow bro you are so brutally honest and feels so nice to watch your tutorial
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!
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.
somehow i can tell you play league of legends
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❤
you know its a beautiful algorithm when the code for it is so simple
Throwing my Cracking The Coding Interview in the trash... you are all I need
Honestly, blows my mind how companies expect anyone to derive this relation without having seen it before.
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.
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.
Such an excellent explanation of Floyd's algorithm - thank you NeetCode!
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.
Thanks! That’s the best explanation I have seen. Now I feel like I actually get the point 😊
Loved the explanation:)
Perhaps the cleanest explanation I've seen so far
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.
Never understood this problem until I watched this. Thank you!
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.
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?
this would happen in cases that, p >> c, in this case the intuition is imagine expanding the cycle however many times it takes until c > p, i.e. if the cycle is 1->2->3->1, you could arbitrarily say that the cycle is actually 1->2->3->1'->2'->3'->1*->2*(etc)->1, this expansion would guarantee that the fast pointer only oops over "the cycle" once
About as good an explanation as possible for such a problem. Great job and subscribed!
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. 😬💡
The proof you made us understand is the best I will ever see for this algo.
Thank you so much, man!
whenever i fall in a frenzy over a leetcode problem....i just google it's neetcode solution. Great explanations man.
great explanation. Especially the maths explanation was really good!!
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
great explanation, but there's a small bug, in your drawn cycle, it should start with 0 -> 1 -> 3, or you can start with 1 - > 3, but then slow and fast should both set to nums[0] initially.
This question looks so complex only for the code to be so easy, thanks man
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.
The best and clear explanation I have found on this algorithm so far ! Thank you !!!!!
I believe for this problem, its better to study the bit manipulation and binary search solution. As floyd cycle is not super intuitive in an interview setting.
Thank you so much ! This is the best explanation of Floyd's algorithm
I appreciate the brutal honesty at the start of this video lol.
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.
Thanks so much, to be honest for so many years I could not get this straight until watching this.
Best explanation for A solution. Respect.
man, this is such a golden explanation
Amazingly explained ! God bless
I think that a very important thing to note is that:
- Zero MUST point to a number.
- But NO number can point to zero
- zero not included in boundaries of numbers
- This guarantees that zero MUST be attached to a cycle where one number has two pointers
- can't have full loop with last number pointing back to zero
So we can confidently start our algorithm from zero every time.
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 .
what a champ!
Thanks for explaining this algo, i had trouble visualising the slow1==slow2 intersecting part.
I wasn't ready for this 💀
WOW, really loved that proof. Never studied this in uni thanks for your help
If the company I am interviewing for asks me to solve it in constant space, I would leave the interview right away.
Incredible explanation man, thanks a ton
Amazing explanation as always. Thank you so very much !!!
Thank you for this content!! The best explanation about this algorithm
You are really talanted in explaning complicated things, even I got it) Thank you
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
Explanation for why this works even when the cycle is shorter than the beginning sequence:
s is the start node
cs is the start of the cycle
p is the number of steps needed to reach cs from s
c is the length of the cycle aka the number of steps to end up at the same node after doing a round in the cycle
In one iteration the fast pointer fs makes 2 steps while the slow pointer sp makes 1 step
1. Finding the intersection in the cycle
- sp reaches the beginning of the cycle after p iterations
- at that moment fp has done p steps in the cycle (possibly having done multiple rounds)
- let r be the number of rounds fp has done in the cycle and s the number of additional steps fs is
into the cycle so that r*c+s = p
- The number of nodes between fp and sp is given by c-s since sp is at the beginning of the cycle and fp is s steps into the cycle
- This means that fp and sp will intersect after c-s iterations
- Since c-s iterations means sp will do c-p steps the intersection will happen c-s steps into the cycle
2. Finding the beginning of the cycle
- Now fp is ignored and a new slow pointer sp2 is placed at the start
- sp2 will need p iterations to reach the start of the cycle
- from fp we know that the p steps sp will do in the cycle result in r rounds and s additional steps
- since sp is c-s steps into the cycle it will be at the start of the cycle p steps later
- thus after p steps sp=sp2=cs
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
The intro makes total sense why I wouldnt never think this is a linkedlist problem
It's like Leafy teaching me how to land a FAANG job. Respect!
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].
sooo good explanation, i watched a bunch of videos, until i landed on your video and got it
Your Videos are so useful. ❤️
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.
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
Fantastic explanation about the math proof of Floyd's algorithm!!!
Beautifully explained.
Best Floyd´s explanation ever. I´ve been trying to get it since I´ve watched Joma´s video 'If Programming Was An Anime'
Thanks for the reassurement that this was a ridiculous question, it totally stumped me haha
12:51 It should p === x. You said p === 0. But I got the point. Great explanation as always!
10:13 how do we know the slow pointer is going to make
And to be more accurate, I think it's better to initialize slow and fast with nums[0] instead with 0
Thank you for helping me understand Floyd's algorithm.
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
Thank you very much, its a nice explanation. Thanks again for all the efforts you put into it.
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
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.
Thank you so much for the wonderful explanation! Really liked it
Great Explanation ! Thank you so much !
best explanation without a doubt.
very nice and clear explanation really helpful for building logical mind thanks subscribed
Neetly explained! I'm bad with time complexities, I'd love for you to break down the time complexity as well.
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
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.
Wont work ,as there are more than 1 duplicates
Dude, it seems that in 2:38 the first node is 1, not 0. As I understand inside the nodes we write the elements of the array, not indexes.
Yeah, I guess its a small mistake on his part, but the awesome explanation covers up for that mistake lol.
The best explanation of Floyd's algorithm!
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.