Find the Duplicate Number

Problem

LeetCode 287 — Find the Duplicate Number

Given an array nums of n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one duplicate. Return the duplicate number.

Constraints: do not modify the array, use only O(1) extra space.

Example

nums = [1, 3, 4, 2, 2]  →  2

Treat each index as a node with one outgoing edge to nums[i]:

0 → 1 → 3 → 2 → 4 → 2  (cycle enters at node 2)

The duplicate value 2 is the entry point of the cycle.

Approach — Floyd’s Tortoise & Hare

Reinterpretation: the array is not a list of values to search — it’s an implicit linked list where next(i) = nums[i]. With n + 1 values in [1..n], at least two indices point to the same next node, so a cycle must exist.

Phase 1 — detect the cycle: walk slow one step and fast two steps until they meet. This confirms a cycle but the meeting point is somewhere inside the cycle, not necessarily the duplicate.

Phase 2 — find the entry: reset slow to index 0. Walk both pointers one step at a time. When they meet again, that node is the cycle’s entry point — the duplicate.

Common mistake

The first meeting point is not the answer. You need phase 2 to find the entry.

Complexity

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

Solution

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

Why It Teaches You Something

The same two-phase Floyd algorithm finds the start of a linked-list cycle (LC 142). The pattern: when constraints forbid a hash set and the input defines a next pointer, ask whether you’re really searching for a value or detecting structure in an implicit graph.