Find the Duplicate Number
Find the Duplicate Number: an array of n + 1 integers holds values in [1, n]. One value repeats. Find it without modifying the array and in O(1) space.
- 1 <= n <= 10⁵
- nums.length == n + 1
- 1 <= nums[i] <= n
- All the integers in nums appear only once except for precisely one integer which appears two or more times.
- How can we prove that at least one duplicate number must exist in nums?
- Can you solve the problem in linear runtime complexity?
Intuition
Find the duplicate number has n + 1 integers in the range 1 to n, with exactly one value repeated. The constraints are what make it interesting: the array may not be modified, and only O(1) extra space is allowed — which rules out sorting, a hash set, and marking visited indices.
The insight is to stop seeing an array and start seeing a linked list. Treat each index as a node pointing to the node at nums[i]. Since every value lies in 1 to n, every pointer stays in bounds, and starting from index 0 the traversal never returns there because no value is 0.
A duplicated value means two indices point to the same node, which is a node with two incoming edges:
- A repeated value makes the pointer chain form a cycle, and the duplicate is exactly the cycle's entry point.
So this reduces to Linked List Cycle II. Floyd's algorithm runs in two phases. First, advance a slow pointer one step and a fast pointer two until they meet somewhere inside the cycle. Then reset one pointer to the start and advance both one step at a time — they meet at the cycle's entrance, which is the duplicate.
That second phase is the part usually misremembered. The meeting point from phase one is not the answer, and moving at different speeds in phase two gives the wrong node.
The alternative is binary search on the value range: count how many elements are <= mid, and if that count exceeds mid, the duplicate is at or below it. That is O(n log n) — slower, but easier to reason about.
Treat the array as a function i → nums[i] and it becomes a linked list where the duplicate value is the node two pointers enter from different places — that is, the cycle entrance. Floyd's algorithm then applies unchanged. The constraint "don't modify the array, use O(1) space" is the tell that a cycle reading is intended.
Approach
Before reading on: sorting modifies the array, a hash set costs O(n) space, and both are banned. Read i → nums[i] as a pointer. What structure does an array of n+1 values in the range 1..n necessarily contain?
Note what the constraints forbid
The array cannot be modified and only O(1) space is allowed. That rules out sorting, a hash set, and index marking — the usual approaches are all excluded by design.
Read the array as a linked list
Treat index i as a node pointing to nums[i]. Every value lies in 1 to n, so pointers stay in bounds and index 0 is never revisited, since no value is 0.
See why a cycle must exist
A duplicated value means two indices point to the same node. That extra incoming edge forces a cycle, whose entry point is the duplicate itself.
Find the meeting point
Advance slow one step and fast two until they meet. This confirms the cycle but the meeting point is not the answer — a common misremembering.
Reset and walk in step
Move one pointer back to the start, then advance both one step at a time. They meet exactly at the cycle's entrance, which is the duplicated value.
Know the binary-search alternative
Count elements <= mid; a count exceeding mid places the duplicate at or below it. O(n log n) — slower than Floyd's but far easier to reason about.
Cost of the approach
Both phases traverse a bounded number of steps, giving O(n) time and O(1) space — the only combination the constraints permit.
Solution & live demo
Common pitfalls
Returning the meeting point
if slow == fast:
return slowslow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowThe meeting point is somewhere inside the cycle, not necessarily its entrance. The second phase — restarting one pointer at the head and stepping both one at a time — is what converges on the entrance, which is the duplicate.
Moving both pointers at the same speed in phase two
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]while slow != fast:
slow = nums[slow]
fast = nums[fast]Phase one needs the 2:1 speed ratio to guarantee a meeting; phase two needs them equal so the distance argument places them at the entrance together. Keeping the fast pointer doubled makes them meet at the wrong node or skip past each other.
Sorting or marking visited entries
for n in nums:
if nums[abs(n)] < 0: return abs(n)
nums[abs(n)] *= -1slow = fast = nums[0]
Negation-marking works but mutates the input, which the problem forbids; sorting mutates it too and costs O(n log n). Floyd's runs in O(n) time and O(1) space while leaving the array untouched.
Edge cases
Floyd's method finds the cycle entrance regardless of how many times the value repeats.
Indexing by value, not position, makes the location in the array irrelevant to the cycle math.
Only index reads are used; the array is never written, satisfying the no-modify rule.