204. Find the Duplicate Number

Treat each value as a 'next' pointer: index i links to index nums[i]. Because some value repeats, two indices point to the same place, creating a cycle whose entrance is the duplicate.

Array as a linked list

Read nums[i] as a pointer from node i to node nums[i]. Values lie in [1, n] and there are n+1 slots, so by pigeonhole two indices share a target — the sequence 0 → nums[0] → nums[nums[0]] → … must eventually cycle, and the cycle's entrance is exactly the duplicated value.

Two phases (Floyd)

1. Find the meeting point. Advance slow by one step and fast by two until they meet inside the cycle.
2. Find the entrance. Reset one pointer to the start; move both one step at a time. They meet at the cycle entrance — the duplicate.

slow = fast = nums[0]
repeat: slow = nums[slow]; fast = nums[nums[fast]]  until slow == fast
slow2 = nums[0]
while slow2 != slow: slow = nums[slow]; slow2 = nums[slow2]
return slow

Worked example

nums = [1,3,4,2,2]. Following pointers from 0: 0→1→3→2→4→2→4→… cycles at 2. Floyd meets, resets, and both converge on 2.

Complexity

• Time: O(n).
• Space: O(1) — no array modification, two integer pointers.

class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: find a meeting point inside the cycle.
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        // Phase 2: find the cycle entrance = the duplicate.
        int slow2 = nums[0];
        while (slow2 != slow) {
            slow = nums[slow];
            slow2 = nums[slow2];
        }
        return slow;
    }
}