Find the Duplicate Number
Find the one repeated value in O(n) time and O(1) space by reading the array as a linked list and using Floyd's cycle detection.
Problem Understanding
Find the Duplicate Number: nums has n + 1 integers, each between 1 and n, and exactly one value repeats (possibly more than twice). Return it without modifying the array and using only O(1) extra space.
Example: [1, 3, 4, 2, 2] returns 2.
The Intuition: The Array Is a Linked List
Read each index as a node and nums[i] as its next pointer. For [1, 3, 4, 2, 2], the walk from index 0 is 0 → 1 → 3 → 2 → 4 → 2 → …: it falls into a loop.
It always does. Values are 1 to n, so no index points back to 0, and with n + 1 nodes the walk must repeat. The node the loop starts at has two incoming pointers, which means two indexes hold the same value: the duplicate.
So this is Linked List Cycle asking for the cycle's entrance, and Floyd's algorithm finds it in two phases:
- Slow moves one step, fast moves two, until they meet inside the cycle.
- Restart slow at the beginning; move both one step at a time. They meet at the entrance.
Interactive Walkthrough
INDEX i POINTS TO nums[i] · INDEX BELOW, VALUE INSIDE
START AT nums[0]
0
s f
1
2
3
4
slow
1
fast
1
Answer
—
the walk from index 0
0 → 1 → 3 → 2 → 4 → 2
Index i points to nums[i]. Start slow and fast at nums[0] = 1
Next
slow takes one step to 3; fast takes two to 2
nums
Legend & Complexity
slow (s)
fast (f)
The duplicate: where the cycle begins
Time
O(n)
Space
O(1), the array is not changed
Each cell is an index, with the index it points to written inside. s and f mark slow and fast. The walk from index 0 is written out beside the array, so you can see where the loop closes before the pointers find it.
Dry Run Table
Input: [1, 3, 4, 2, 2]
| Phase | slow | fast |
|---|---|---|
| start | 1 | 1 |
| 1 | 3 | 2 |
| 1 | 2 | 2 (meet) |
| reset | 1 | 2 |
| 2 | 3 | 4 |
| 2 | 2 | 2 (meet) |
The answer is 2.
The Solution Template
Floyd's tortoise and hare, phase 1 then phase 2.
Find the Duplicate Number Code
1var findDuplicate = function(nums) {2 let slow = nums[0], fast = nums[0];3 do {4 slow = nums[slow];5 fast = nums[nums[fast]];6 } while (slow !== fast);7 slow = nums[0];8 while (slow !== fast) {9 slow = nums[slow];10 fast = nums[fast];11 }12 return slow;13};
Edge Cases & Common Mistakes
- The value repeats many times:
[3, 3, 3, 3, 3]still works; the pointers meet at once and the entrance is 3. - Starting phase 1 with slow == fast: use a do-while (or
while Truewith the check after moving), or the loop never starts. - Resetting slow to 0 instead of nums[0]: both choices work only if phase 1 started from the same place; keep them consistent.
- Sorting or marking values negative: both modify the array, which the problem forbids.
Summary
Read nums[i] as a next pointer. The walk from index 0 enters a cycle whose entrance is the duplicate. Floyd's algorithm finds it: slow and fast meet inside the cycle, then a pointer from the start and one from the meeting point meet at the entrance. O(n) time, O(1) space, array unchanged.
More practice: DSA interview questions with answers · patterns cheat sheet