ASAPUtils
The crucial reframe
The constraints are the clue: every nums[i] is a valid next index in 1..n. Start from index 0
and follow:
0 → nums[0] → nums[nums[0]] → ...
There are more array positions than possible destinations, so the functional graph contains a cycle. The duplicate is its entrance.
Optimal solution
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
int seeker = 0;
while (seeker != slow) {
seeker = nums[seeker];
slow = nums[slow];
}
return seeker;
}
function findDuplicate(nums) {
let slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
let seeker = 0;
while (seeker !== slow) {
seeker = nums[seeker];
slow = nums[slow];
}
return seeker;
}
Why phase two finds the entrance
Floyd’s first phase guarantees a meeting inside the cycle. The path length from index 0 to the entrance is congruent, modulo the cycle length, to the remaining distance from that meeting to the entrance. Starting one pointer at each location and moving equally makes them arrive together.
Complexity
Both phases are linear: O(n) time. The array is read-only and three indices use O(1) space.
Traps
- Treating values as data instead of valid next indices.
- Returning the phase-one meeting, which is not generally the entrance.
- Starting from
nums[0]inconsistently between phases. - Using a set or sorting despite explicit O(1)-space/read-only requirements.
Blank re-solve prompt
Draw the index-to-value arrows for
[1,3,4,2,2]. Locate the cycle, then derive both Floyd phases using indices only—no linked-list node objects.