Find the Duplicate Number
Problem Statement
Given an integer array nums containing n + 1 integers where each integer is in the range 1 to n, return the repeated number.
There is exactly one repeated number, but it may appear more than twice. You must not modify the array and must use only constant extra space.
Input
An integer array nums of length n + 1, with values constrained to valid indices from 1 through n.
Output
The duplicated integer.
Constraints
- •
1 <= n <= 10^5 - •
nums.length == n + 1 - •
1 <= nums[i] <= n - •
All integers in nums appear only once except for one integer that appears two or more times - •
Do not modify nums and use only O(1) extra space
Examples
Example 1
nums = [1,3,4,2,2]
2Example 2
nums = [3,1,3,4,2]
3Example 3
nums = [1,1]
1Learning Objectives
- Model an array as a functional graph where each index has one outgoing edge.
- Explain why the duplicate value is the entrance to an implicit cycle.
- Apply Floyd's detection and reset phases without modifying the array.
- Respect the O(1)-space constraint that rules out sorting or hash sets.
Intuition
Pattern Recognition
The constraints are the signal: values are between 1 and n, while the array has n + 1 positions. Treat each index as a node and nums[index] as the next index. That creates a one-next graph, the same shape as a linked list with a cycle.
The index-to-value-to-index mapping is what makes the trick legal. From index i, move to index nums[i]. Because every value is a valid index from 1 to n, the walk never leaves the array after the first move. Two different indices pointing to the same value create the merge that becomes a cycle, and the cycle entrance is exactly the duplicate value.
Sorting would modify the array, and a hash set would use O(n) space. Floyd's algorithm satisfies both constraints: no mutation and O(1) extra space.
Common mistakes
- ×Treating values as counts instead of next indices, which misses the functional graph.
- ×Starting from every index instead of following one deterministic path from index 0.
- ×Using sorting or sign marking even though the problem forbids modifying the array.
- ×Returning the first Floyd meeting immediately instead of running the entrance reset phase.
Algorithm Explanation
Key idea
Build an implicit linked list where node i points to node nums[i]. Since there are more nodes than possible next values, the path from 0 must enter a cycle. The duplicate value is the first node in that cycle because it has multiple incoming edges.
Pointer walkthrough
For nums = [1,3,4,2,2], the path is 0 -> 1 -> 3 -> 2 -> 4 -> 2 .... Start slow = nums[0] = 1 and fast = nums[0] = 1. First move: slow goes to 3, while fast goes from 1 to 3 to 2. Second move: slow goes from 3 to 2, and fast goes from 2 to 4 to 2, so they meet at 2.
Now reset slow to nums[0] = 1 and keep fast at 2. Move both one step through the index-to-value mapping: slow goes 1 -> 3 -> 2, while fast goes 2 -> 4 -> 2. They meet at 2, the cycle entrance and duplicate number.
Algorithm
- Initialise slow = nums[0] and fast = nums[0].
- Repeatedly move slow = nums[slow] and fast = nums[nums[fast]] until they meet.
- Reset slow = nums[0] while fast remains at the meeting value.
- Move both one step with nums[pointer] until they meet again.
- Return the meeting value; it is the duplicate.
Solutions
Solution: Floyd cycle detection on indices
Interpret the array as a deterministic next-pointer graph. The first Floyd phase finds a meeting point inside the cycle, and the reset phase finds the cycle entrance. The entrance value is the duplicated number because multiple indices point to it.
Step-by-step
- Start both pointers at nums[0] so the walk immediately enters the value-index domain.
- Use a do-while style detection phase: move slow once and fast twice until they meet.
- Reset slow to nums[0] and leave fast at the meeting value.
- Move both pointers one step at a time by reading nums[pointer].
- Return the value where they meet; that value is the duplicate.
O(n)
O(1)
Floyd's two phases make a linear number of array reads and store only two pointers.
Java implementation
Dry Run
Sample input
nums = [1,3,4,2,2]. Interpret each step as following index -> nums[index].
| phase | slow | fast | movement | meaning |
|---|---|---|---|---|
| detect start | 1 | 1 | both start at nums[0] | inside valid value indices |
| detect move 1 | 3 | 2 | slow one read, fast two reads | not equal |
| detect move 2 | 2 | 2 | slow reaches 2, fast wraps to 2 | meeting inside cycle |
| entry start | 1 | 2 | reset slow to nums[0] | prepare entrance search |
| entry move 1 | 3 | 4 | both move one read | not equal |
| entry move 2 | 2 | 2 | both move one read | duplicate found |
The second meeting is 2. In the functional graph, that value is the cycle entrance, so it is the repeated number.
Interview Tips
This problem is really Linked List Cycle II wearing array clothing. Say the mapping clearly: index i points to index nums[i]. Then explain why the duplicate creates a cycle entrance rather than just a repeated edge. Also state why common alternatives are disallowed: sorting mutates the array, and a set breaks the O(1)-space requirement.
Likely follow-ups
- How would you solve it if modifying the array were allowed?
- How would you solve it if O(n) extra space were allowed?
- What changes if there can be multiple distinct duplicated values?
- Can you use binary search on value ranges to solve it without modifying the array?
Similar Problems
Key Takeaways
- Array values can act as next pointers when every value is a valid index.
- The duplicate is the cycle entrance because it has more than one incoming edge.
- Floyd's algorithm satisfies both constraints: no array modification and O(1) extra space.
- Do not return the first meeting until the reset phase finds the entrance.