Find the Duplicate Number

n + 1 numbers in the range 1..n, exactly one value repeated; find it without modifying the array and in O(1) space. Treat each value as a pointer i → nums[i]. The duplicate value is where two pointers lead into the same index, the entrance to a cycle. Floyd's tortoise and hare finds it.

Traced input: nums = [1, 3, 4, 2, 2] → 2. Original problem: neetcode.io/problems/find-duplicate-integer

Complexity

Two phases, each linear.

Key idea

• Index 0 is never a target (values are 1..n), so it's a safe start outside the cycle.
• Phase 1: slow moves 1 step, fast 2 steps, until they meet inside the cycle.
• Phase 2: reset one pointer to 0; move both 1 step. They meet at the cycle entrance: the duplicate.

Common mistakes

• Sorting or marking negatives modifies the array, which is forbidden.
• A HashSet uses O(n) space.

Solution

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

def findDuplicate(nums: List[int]) -> int:
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

int findDuplicate(vector<int>& nums) {
    int slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Edge cases

Each one has its own trace in the interactive view.