Find the Duplicate Number [Medium] — Floyd's Cycle Detection

Problem Statement

Given an array nums of n+1 integers where each integer is in [1, n], there is exactly one repeated number. Find it.

Constraints: Must use only O(1) extra space, cannot modify the array.

Input: [1,3,4,2,2] → Output: 2
Input: [3,1,3,4,2] → Output: 3

Intuition

Treat the array as a linked list where nums[i] is the next pointer. Because there's a duplicate, there's a cycle. Floyd's algorithm finds the cycle entry which is the duplicate.

Solutions

C

int findDuplicate(int* nums, int n) {
    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;
}

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;
}

JavaScript

var findDuplicate = function(nums) {
    let 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;
};

Python

def findDuplicate(nums: list[int]) -> int:
    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

Complexity

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

Alternative: Binary Search O(n log n)

Count elements ≤ mid; if count > mid, duplicate is in [1..mid].