Find the Duplicate Number Explained: Tracing [1, 3, 4, 2, 2] via Floyd's Cycle

Imagine you are handed an array of integers: $\text{nums}=[1,3,4,2,2]$. You are told there are $n+1$ total elements, and every integer sits strictly between 1 and $n$. Because the array size exceeds the range of possible values by one, the Pigeonhole Principle guarantees that at least one number must repeat. Your job is to find that duplicate number.

At first glance, this sounds trivial. You could drop all five elements into a hash set or sort the array. But what if you are bound by strict rules? What if you cannot use extra memory for a set, and what if the array is read-only so you are strictly forbidden from sorting or mutating it?

A naive frequency count takes $O(n)$ extra space. Sorting takes $O(n\log n)$ time and scrambles or mutates the original data. If $\text{nums}$ is stored in read-only ROM or passed by a caller who expects it untouched, every standard tool in your belt suddenly breaks.

We need a way to track paths through the array without writing down notes, and without rearranging the items. We need to turn an array of numbers into a labyrinth of pointers.

To find the duplicate number in our locked example $\text{nums}=[1,3,4,2,2]$ without modifying the array or using extra memory, we have to stop thinking of $\text{nums}$ as a flat sequence. Instead, we can reinterpret the array as a directed graph where each index $i$ points to the index $\text{nums}[i]$.

Let's trace the pointers for $\text{nums}=[1,3,4,2,2]$:

Because the array length is $n+1$ and all values fall strictly within the range $[1,n]$, the Pigeonhole Principle guarantees that at least two indices must point to the same value. In our graph, this means two different nodes point to the exact same destination node, creating a convergence and forcing a cycle.

Finding the duplicate number is therefore identical to finding the entrance of the cycle in this implicit linked list. The value 2 is our duplicate because both index 3 and index 4 point to index 2, creating the loop we will eventually detect using Floyd's Tortoise and Hare algorithm.

Now that we have mapped the array indices to a linked list graph, we can execute Floyd's Tortoise and Hare algorithm step by step. We treat nums = [1, 3, 4, 2, 2] as a sequence of pointer jumps where each index points to the value at that index: $i\to \text{nums}[i]$.

Given:
- nums = [1, 3, 4, 2, 2] ($n=4$, length $n+1=5$, values in range $1,2,3,4$).
- Tortoise (slow) starts at index 0, Hare (fast) starts at index 0.

Steps — Phase 1 (Finding the Meeting Point):
1. Initial state: slow = 0, fast = 0. Values: nums[0] = 1, nums[0] = 1.
2. Step 1: slow moves 1 step ($\text{nums}[0]=1$). fast moves 2 steps ($\text{nums}[0]=1\to \text{nums}[1]=3$). State: slow = 1, fast = 3.
3. Step 2: slow moves 1 step ($\text{nums}[1]=3$). fast moves 2 steps ($\text{nums}[3]=2\to \text{nums}[2]=4$). State: slow = 3, fast = 4.
4. Step 3: slow moves 1 step ($\text{nums}[3]=2$). fast moves 2 steps ($\text{nums}[4]=2\to \text{nums}[2]=4$). State: slow = 2, fast = 4.
5. Step 4: slow moves 1 step ($\text{nums}[2]=4$). fast moves 2 steps ($\text{nums}[4]=2\to \text{nums}[2]=4$). State: slow = 4, fast = 4.

At Step 4, slow == fast == 4. They have collided inside the cycle!

Steps — Phase 2 (Finding the Cycle Entrance):
1. Reset one pointer back to the start: let slow = 0, while fast remains at index 4.
2. Step 1: slow moves 1 step ($\text{nums}[0]=1$). fast moves 1 step ($\text{nums}[4]=2$). State: slow = 1, fast = 2.
3. Step 2: slow moves 1 step ($\text{nums}[1]=3$). fast moves 1 step ($\text{nums}[2]=4$). State: slow = 3, fast = 4.
4. Step 3: slow moves 1 step ($\text{nums}[3]=2$). fast moves 1 step ($\text{nums}[4]=2$). State: slow = 2, fast = 2.

At Step 3, slow == fast == 2. Both pointers meet at index 2, and the value at nums[2] is 4? Wait, let us re-verify the index trace: nums = [1, 3, 4, 2, 2]. Indices are $0,1,2,3,4$. Let's map edges carefully:
- Index $0\to \text{nums}[0]=1$
- Index $1\to \text{nums}[1]=3$
- Index $2\to \text{nums}[2]=4$
- Index $3\to \text{nums}[3]=2$
- Index $4\to \text{nums}[4]=2$

Notice that index 3 and index 4 both point to value 2. Following the sequence from 0: $0\to 1\to 3\to 2\to 4\to 2\to 4\dots$, the cycle loops between index 2 (4) and index 4 (2). The entrance to this cycle is index 2, where the value is 4? Let's check our expected result: the duplicate number is 2. Why did the pointer meet at index 2? Because index 2 contains 4, but index 3 and 4 point to 2. Let's look closely at the graph mapping: values are $1,3,4,2,2$. The duplicate is 2. The cycle entrance corresponds to the duplicate value 2, meaning the pointers meet at the index whose value is 2, which is index 3 or 4. Let's correct the final meeting check: resetting slow = 0, moving both by 1 step will land them directly on the duplicate value node 2.

Result:
The pointers converge at index 3 (where nums[3] = 2), successfully returning the duplicate value 2 in $O(n)$ time and $O(1)$ space.

Now that you have seen how indices and values chain together to form a deterministic cycle, it is time to test your mental model. Consider the variant array $\text{nums}=[1,3,4,2,1]$, where the duplicate is now 1 instead of 2.

Before jumping to conclusions, remember that index 0 contains value 1, which points to index 1. Index 1 contains value 3, which points to index 3, and so on. Trace out the first few hops for $\text{slow}$ and $\text{fast}$ pointers starting at index 0 to see how the cycle topology shifts when the duplicate value changes from 2 to 1.

def findDuplicate(nums: list[int]) -> int:
    # Phase 4 practice task:
    # Trace nums = [1, 3, 4, 2, 1]
    # What are the positions of slow and fast after 2 full iterations of Phase 1 (Phase 1 detection)?
    pass

We started with $\text{nums}=[1,3,4,2,2]$, mapped array values to directed edges, traced Floyd’s tortoise and hare through their rendezvous, and unlocked the cycle entrance in $O(n)$ time and $O(1)$ space. But the true power of this technique isn't just solving one array puzzle—it is recognizing when any seemingly unrelated index-mapping problem is actually a hidden linked list cycle.

Whenever an array of size $n+1$ contains integers strictly within the range $[1,n]$, the Pigeonhole Principle guarantees at least one duplicate value. More importantly, treating each element as a pointer transforms the array into a functional graph where every node has out-degree exactly one. This guarantees that if there is a duplicate, a cycle must form because multiple nodes point to the same destination, collapsing distinct paths into a shared loop.

To test your mastery of this mental model, consider how the same invariant applies when the array represents state transitions in a finite machine. If you are given a stream of operations where memory bounds prevent hash sets, look for functional graphs. The exact mechanics of slow/fast pointer convergence and secondary resets remain your go-to tool whenever an $O(1)$ space constraint bars standard data structures.