Find the Duplicate Number

Find the Duplicate Number looks like a simple counting problem until you read the constraints: you may not modify the array and you must use only constant extra space. That rules out sorting and hash sets, and pushes you toward a beautiful trick — treating the array itself as a linked list and running Floyd's cycle detection on it.

The slow way first

The obvious idea: keep a hash set of values you have seen, and the first value already in the set is the duplicate. That is O(n) time but O(n) space — and the problem forbids extra space. Sorting and scanning for neighbors is O(n log n) but modifies the array, which is also banned.

The question to ask: how can I find a repeat using only a couple of integer variables? The key realization is that the array secretly encodes a linked structure.

The idea: the array is a linked list with a cycle

Read each index i as a node whose next pointer is nums[i]. Starting from index 0, follow the links: 0 → nums[0] → nums[nums[0]] → …. Because there are n + 1 slots but values only go up to n, two different indices must point to the same place — that makes a cycle, and the node where the cycle begins is exactly the duplicated value.

So finding the duplicate becomes finding the start of a cycle in a linked list — the classic Floyd's tortoise-and-hare problem. Phase one finds a meeting point inside the cycle; phase two finds where the cycle begins.

Walk through it

Step through the animation. In phase 1, slow advances one link and fast advances two until they collide inside the cycle (here at index 2). In phase 2, slow jumps back to index 0 while fast stays put, and now both move one step at a time. The point where they meet again is the cycle entrance — index 2 — and that index value 2 is the answer.

Pseudocode

slow = fast = 0
repeat:                       # phase 1: find a meeting point
    slow = nums[slow]         # one step
    fast = nums[nums[fast]]   # two steps
until slow == fast
 
slow = 0                      # phase 2: find the cycle entrance
while slow != fast:
    slow = nums[slow]         # both move one step now
    fast = nums[fast]
return slow                   # the entrance index == the duplicate value

The Python solution

def find_duplicate(nums):
    # treat nums[i] as a pointer to index nums[i]
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # second walk: find the cycle entrance
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

• slow and fast both start at index 0, the head of our virtual linked list.
• In phase 1, slow = nums[slow] takes one hop and fast = nums[nums[fast]] takes two; a faster pointer in a cycle always laps the slower one, so they are guaranteed to meet.
• The meeting point is inside the cycle, not necessarily at its entrance — that is why a second phase is needed.
• In phase 2, resetting slow to 0 and moving both one step at a time makes them meet exactly at the cycle entrance (a property of Floyd's algorithm).
• That entrance index is the value that two slots pointed to — the duplicate — so we return slow.

Complexity

Both pointers traverse a linear number of links, so the whole thing is O(n) time, and we only ever hold a couple of integer indices — O(1) space, with the input left exactly as it was.

When this pattern shows up

Practice