Find the Duplicate Number

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:
Input: nums = [3,1,3,4,2]
Output: 3

Approach: Floyd’s Cycle Detection (Fast and Slow Pointers)

At first glance, this looks like an array or binary search problem. However, because of the strict constraint $1 \le nums[i] \le n$ for an array of size $n+1$, we can map this perfectly to a Linked List Cycle problem.

If we treat the array values as “pointers” to the next index (e.g., node at index i points to index nums[i]), multiple indices will point to the same target index if and only if that target value is the duplicate. Thus, the duplicate number is the starting node of a cycle.

We can use Floyd’s Tortoise and Hare algorithm to find the start of the cycle in two phases:

Phase 1: Find the Intersection Point

1. Initialize two pointers, slow and fast, both starting at nums[0].
2. Move slow by 1 step (slow = nums[slow]) and fast by 2 steps (fast = nums[nums[fast]]).
3. Because there is guaranteed to be a cycle, slow and fast will eventually intersect.

Phase 2: Find the Start of the Cycle

1. Once they intersect, leave fast at the intersection point, but move slow all the way back to the start (nums[0]).
2. Now, move both slow and fast forward by 1 step at a time (slow = nums[slow], fast = nums[fast]).
3. The exact node where they meet again is the entrance to the cycle, which corresponds to our duplicate number!

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function findDuplicate(nums) {
    let slow = nums[0];
    let fast = nums[0];
    
    // Phase 1: Find the intersection point
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // Phase 2: Find the entrance to the cycle (the duplicate number)
    slow = nums[0]; // Reset slow back to start
    
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast]; // Both move at the same speed now
    }
    
    return slow; // or return fast, they are at the same spot
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the array. In Phase 1, the fast pointer will catch the slow pointer in at most $O(n)$ steps. In Phase 2, finding the start of the cycle takes at most $O(n)$ steps.
• Space Complexity: $O(1)$. We only use two integer pointers (slow and fast), adhering perfectly to the constant extra space constraint without modifying the original array.