LeetCode 287: Find the Duplicate Number

Explanation

To solve this problem without modifying the array and using only constant extra space, we can use the Floyd's Tortoise and Hare algorithm. This algorithm is commonly used to detect cycles in a linked list but can also be applied to this problem as the array can be visualized as a linked list where the value at each index points to the next index.

1. Initialize two pointers, slow and fast, both starting at the first index.
2. Move the slow pointer one step and the fast pointer two steps at a time until they meet at some index.
3. Once they meet, reset the slow pointer to the first index and move both slow and fast pointers one step at a time until they meet again. The index at which they meet is the duplicate number.

This algorithm guarantees finding a duplicate number because there must be a cycle in the array due to the constraint that one number appears two or more times.

• Time complexity: O(n)
• Space complexity: O(1)

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[0];
    
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}