287. Find the Duplicate Number

LeetCode

If there is no duplicate in the array, the mapping f(index) = num must be one to one, otherwise the mapping is many to one.

If we linked all the mappings up we can reduce this problem to cycle detection. In an array with duplicate numbers, there must be at least two indexes mapped to the same num, one of the indexes belongs to the cycle, the other belongs to the “straight line”, thus the cycle entrance is the num.

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