Back to solutions

Find Duplicate Number

MediumArrays

Find the one repeated value in [1, n] using O(1) space.

Open problem
Constraints
  • 2 <= m <= 10^5
  • values in [1, m-1]
  • exactly one value repeats

Floyd's cycle detection

Time O(n)Space O(1)

Treat each value as a 'next index' pointer: i -> nums[i]. Because some value repeats, two indices point to the same place, which creates a cycle, and the cycle's entrance is the duplicate. Use a slow and a fast pointer to find a meeting point, then walk one pointer from the start until they meet again at the entrance.

Key terms
pigeonhole principle:
With more items than containers, some container holds two items here, a repeated value must exist.
cycle entrance:
The first node where the looping path rejoins itself; it equals the duplicate value.
tortoise and hare:
A slow pointer moving one step and a fast pointer moving two, used to detect cycles in O(1) space.
int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];
    do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
    slow = nums[0];
    while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
    return slow;
}
Step by step
  1. Follow pointers i -> nums[i]. Advance slow by one and fast by two until they meet inside the cycle.
  2. Reset slow to the start; move both slow and fast one step at a time.
  3. They meet at the cycle entrance, which is the duplicated number.
  4. Return that value; the array is never modified.