Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
287. Find the Duplicate Number
Bookmark
Input
Standard
Larger
Simple
Custom
nums
=
[1, 3, 4, 2, 2]
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
nums is a linked list: node i → nums[i]; a duplicate makes a cycle
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
nums is a linked list: node i → nums[i]; a duplicate makes a cycle
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
slow
fast
slow
1
≠ fast
3
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
slow
fast
fast = nums[nums[3]] = nums[2] =
4
(two hops)
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
slow
fast
fast = nums[nums[4]] = nums[2] =
4
(two hops)
Phase 1 · detect the cycle
0
1
2
3
4
1
3
4
2
2
slow
fast
slow = nums[2] =
4
(one hop)
Phase 2 · find the entrance
0
1
2
3
4
1
3
4
2
2
slow
fast
reset slow = 0
; keep fast at 4. Now both hop once.
Phase 2 · find the entrance
0
1
2
3
4
1
3
4
2
2
slow
fast
slow = nums[0] =
1
Phase 2 · find the entrance
0
1
2
3
4
1
3
4
2
2
slow
fast
slow = nums[1] =
3
Phase 2 · find the entrance
0
1
2
3
4
1
3
4
2
2
slow
fast
slow
3
≠ fast
4
duplicate found
0
1
2
3
4
1
3
4
2
2
slow
fast
slow == fast ==
2
= the cycle entrance = the duplicate
duplicate = 2
algo
master
.
io
Step:
Find the duplicate with Floyd's cycle detection
0 / 23
Input
Standard
Larger
Simple
Custom
nums
=
[1, 3, 4, 2, 2]
0 / 23
algo
master
.
io
Step:
Find the duplicate with Floyd's cycle detection
