Find the Duplicate Number: Why Floyd's Cycle Detection Works on an Array

Find the Duplicate Number gives n+1 integers in the range 1..n, exactly one repeated, and asks for O(1) extra space without modifying the array. The intended answer surprises people the first time: treat the array as a linked list.

The reframe

Read each index i as a node with an edge to nums[i]. Because values are in 1..n and index 0 is never a target, starting at 0 walks a path that must eventually enter a cycle. Two indices point to the duplicate value, so the duplicate is exactly the entry point of that cycle.

Floyd in two phases

def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Phase one finds a meeting point inside the cycle. Phase two restarts one pointer and moves both one step at a time; they meet at the cycle entrance because the distance from the start to the entrance equals the distance from the meeting point to the entrance, modulo the cycle length.

Alternatives worth naming

Binary search on the value range counts how many numbers are <= mid and runs in O(n log n) with O(1) space. Sorting or a set is simpler but breaks the constraints. Naming these first and then explaining why Floyd wins shows you read the constraints.

More interview walkthroughs from our team are at https://www.linkjob.ai/. Disclosure: I help build Linkjob AI.