Problem
You are given an integer array nums containing n + 1 integers where each integer is in the range [1, n]. There is exactly one number that appears more than once.Return the duplicate number without modifying the array and using only constant extra space.
Example
Consider the following example to understand the expected input and output.Input
nums = [1,3,4,2,2]Output
2Solution
This solution uses Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm. The key idea is to treat the array as a linked list where the value at each index points to another index.Since every value is in the range [1, n], each value can be used as a valid index. Because there are n + 1 elements but only n possible values, the duplicate value creates a cycle in this implicit linked list. The duplicate number is the entry point of that cycle.
First, the slow pointer moves one step at a time while the fast pointer moves two steps at a time. When they meet, a cycle has been detected.
Next, reset slow to the beginning of the array. Move both pointers one step at a time. The point where they meet again is the duplicate number.
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
// Find the intersection point inside the cycle.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// Find the entrance of the cycle.
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}Complexity
The slow and fast pointers traverse the implicit cycle a limited number of times, resulting in O(n) time complexity.The algorithm uses only two pointers and does not modify the input array, so the extra space complexity is O(1).
