Floyd's Cycle Detection: Visualizing LeetCode 287

#The Problem

LeetCode 287: given n + 1 integers in the range [1, n], find the duplicate — without modifying the array, in O(1) space.

The trick is to treat the array as a linked list where index i points to nums[i]. Two indices mapping to the same value means a cycle, and the cycle entrance is the duplicate. Floyd’s algorithm finds it in two phases: a fast/slow pointer collision, then a walk from both the start and the meeting point until they converge.

#Visualizer

#Why Phase 2 Works

• $L$ — tail length (start to cycle entrance)
• $D$ — distance into the cycle where the pointers meet
• $C$ — cycle length

When the pointers collide, slow has taken $L + D$ steps. Fast moves at double speed, so it has taken $2(L + D)$. The extra $L + D$ steps are full laps around the cycle, so $L + D$ is a multiple of $C$:

Rearranging to solve for $L$:

The $kC$ part is just full laps around the cycle — they bring you right back to where you started. So walking $L = kC - D$ steps from the meeting point is the same as walking $-D$ steps, which backs up $D$ to the cycle entrance. That’s the same place you reach by walking $L$ steps from the start. So phase 2 just starts one pointer at the head and one at the meeting point — they converge at the entrance.

#The Code

def findDuplicate(nums: list[int]) -> int:
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow  # O(n) time, O(1) space