Find The Duplicate Number

Problem Description

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 O(1) extra space.

Examples

Constraints

• 1 <= n <= 10⁵
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for the precisely one integer which is repeated two or more times.

Floyd’s Cycle Detection (Tortoise and Hare)

Because elements are in the range [1, n] and the array length is n+1, we can map values to indices, treating the array as a directed graph where index i points to node nums[i]. Since there is a duplicate number, multiple indices will point to the same value, creating a cycle. We can find the entry point of the cycle (which is the duplicate number) using Floyd’s Tortoise and Hare algorithm:

1. Detect Intersection: Move slow pointer by 1 step (slow = nums[slow]) and fast pointer by 2 steps (fast = nums[nums[fast]]). They will meet inside the cycle.
2. Find Cycle Entry: Reset slow to index 0, and move both slow and fast by 1 step at a time. The point where they meet is the duplicate value.

Solution 1: Floyd’s Cycle Detection

Use fast and slow pointers to detect the intersection point, then trace back to the cycle entry.

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];

        // Phase 1: Meet inside the cycle
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // Phase 2: Find cycle entry
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        slow = nums[0]
        fast = nums[nums[0]]
        
        # Phase 1: Meet inside the cycle
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
            
        # Phase 2: Find cycle entry
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
            
        return slow

#include <vector>

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];

        // Phase 1: Meet inside the cycle
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // Phase 2: Find cycle entry
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

Complexity Analysis

• Time Complexity: O(n) since cycle detection is guaranteed to meet and resolve within linear bounds.
• Space Complexity: O(1) auxiliary space as we only use two integer pointers.

Where It Breaks

This solution depends on values being strictly positive and bounded by the array size. If elements can be zero or negative, the values cannot represent valid index pointers.

Common Mistakes

• Incorrect pointer initialization: Initializing both slow and fast to 0 or nums[0] in the same step. If they start at the same value, the loop condition slow != fast fails immediately, skipping the detection phase.
• Modifying the array: Attempting to sort or mark visited values (like negating values). While this resolves duplicates, it violates the non-modification constraint.

Frequently Asked Questions

Why does resetting slow to 0 locate the duplicate element? Mathematically, the distance from the array start to the cycle entry is exactly equal to the distance from the intersection point to the cycle entry (modulo cycle length).

Can we solve this using binary search? Yes. You can binary search the range [1, n]. For each candidate mid, count elements less than or equal to mid. If count exceeds mid, the duplicate is in [1, mid]; otherwise in [mid+1, n]. This takes O(n log n) time and O(1) space, but is slower than Floyd’s cycle detection.

← All Problems