Find the Duplicate Number Explained

Problem Statement

Given an array nums of n + 1 integers where each integer is in the range [1, n], there is exactly one number that appears more than once. Find this duplicate number without modifying the array and using only O(1) extra space. This problem tests advanced techniques like Floyd’s Tortoise and Hare algorithm to detect a cycle in a linked-list-like structure.

Example

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

Output: 2

Explanation: The number 2 appears twice, while all other numbers appear once.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 3, 4, 2, 2};
        System.out.println(sol.findDuplicate(nums)); // 2
    }
}
            

def find_duplicate(nums):
    slow = nums[0]
    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

# Example usage
print(find_duplicate([1, 3, 4, 2, 2]))  # 2
            

function findDuplicate(nums) {
    let slow = nums[0];
    let 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;
}

// Example usage
console.log(findDuplicate([1, 3, 4, 2, 2])); // 2
            

Explanation

• Treat the array as a linked list where each value points to the index equal to that value.
• Use Floyd’s cycle detection with two pointers: slow moves one step, fast moves two steps.
• When slow and fast meet, a cycle is detected.
• Reset slow to nums[0] and move both pointers one step at a time.
• The point where they meet again is the duplicate number.

Note