Find the Duplicate Number
An array of n + 1 integers holds values in the range 1..n, so at least one value repeats. Exactly one value is duplicated (possibly many times). Find it without modifying the array and using constant extra space.
- 1 ≤ n ≤ 10^5
- nums.length = n + 1
- 1 ≤ nums[i] ≤ n
- Only one repeated value
- Values are valid *indices* into the array —
i → nums[i]is a functional graph - A duplicated value means two indices point to the same node → a cycle
- Read-only and O(1) space rule out sorting or hashing
Two pointers moving at different speeds along a sequence of next links meet if and only if the sequence loops (Floyd). The same trick locates the middle in one pass and finds the cycle entry, all in O(1) space. Any function f: [1..n] -> [1..n] iterated from a start is an implicit linked list.
Treat i → nums[i] as a linked structure starting from index 0. Because two positions map to the duplicated value, the walk enters a cycle whose entry node is that value. Run Floyd's cycle detection: slow and fast pointers meet inside the cycle; then restart one pointer at 0 and move both one step at a time — they meet exactly at the cycle entrance, which is the duplicate.
- Binary search on the value range counting how many elements are ≤ mid gives O(n log n) with O(1) space. Sorting or a hash set is easier but violates the constraints.