287. Find the Duplicate Number

Problem

Find the Duplicate Number

Approach

We can solve this problem with Floyd's Tortoise and Hare. If we interpret nums such that for each pair of index i and value nums[i], the next value nums[j] is at index nums[i], we can reduce this problem to cycle detection.

Code

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = nums[0];
        int slow = nums[0];
        while(true){
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(fast == slow){
                break;
            }
        }
        int head = nums[0];
        int q = fast;
        while(head != q){
            q = nums[q];
            head = nums[head];
        }
        return q;
    }
}