Find the Duplicate Number
Medium Floyd's cycle on indexes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
An array of n + 1 numbers has values in 1..n, so one value repeats (possibly many times). Find it without modifying the array and with O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: n+1 numbers in 1..n, so one repeats. Find it without changing the array or using extra memory.
Why this works: treat index → nums[index] as "next". Two indexes pointing to the same place form a loop, and the loop's entrance is the duplicate. Floyd's slow/fast pointers find it.
Example: [1, 3, 4, 2, 2]
path: 0 → 1 → 3 → 2 → 4 → 2 → 4 …loop is 2 → 4 → 2, entered at 2answer 2
✦Hints open one at a time
↗Approach
Floyd's algorithm: move slow one step and fast two steps until they meet. Reset one pointer to the start and move both one step at a time; where they meet again is the cycle entrance, which is the duplicate value.
</>Solution (Java)
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast); // phase 1: meet inside the cycle
slow = nums[0];
while (slow != fast) { // phase 2: find the entrance
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}!Common mistake
Sorting or marking with negatives — both modify the array, which the problem forbids.
- Time: O(n).
- Space: O(1).
