Find the Duplicate Number — Floyd's on Array as Linked List

Problem 229 · Find the Duplicate Number

Difficulty: Medium · Pattern: Floyd's on Implicit Linked List

Array has n+1 integers in [1,n]. Find the one duplicate without modifying array, O(1) extra space.

Intuition

Treat array as: index i → nums[i]. Since duplicate exists, there's a cycle. Use Floyd's to find cycle entry = duplicate.

Solutions

# Python
def findDuplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

// Java
public int findDuplicate(int[] nums) {
    int slow = nums[0], 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;
}

// C++
int findDuplicate(vector<int>& nums) {
    int slow = nums[0], 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;
}

Complexity

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