Find the Duplicate Number as a Hidden Linked List Cycle

"Find the Duplicate Number" shows up again and again in Amazon, Google, Microsoft phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Fast and Slow Pointers pattern quickly and code it cleanly. Part 8 of 11 in the Fast and Slow Pointers arc.

The Problem

Given an array nums of n + 1 integers where each value is in the range 1 to n, exactly one value repeats (possibly more than twice). Find it without modifying the array and using O(1) space. Those two constraints kill sorting and hash sets — deliberately.

Input:  nums = [1, 3, 4, 2, 2]
Output: 2

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

Treat each index as a node whose next is nums[i]. Values in 1..n over n + 1 slots mean the walk from index 0 never escapes and — by pigeonhole — must cycle, and the cycle's entry is precisely the duplicated value. This reduction is a celebrated interview set piece.

The Approach

Run Floyd exactly as in Linked List Cycle II: fast and slow through i -> nums[i] until they meet, then reset one pointer to the start and advance both at equal speed; the meeting point is the duplicate.

Spend your explanation on the reduction, not the algorithm — why a duplicate value means two indices point at the same node, making it the cycle entry. The algorithm you have already proven earlier in this arc.

Python Solution

def find_duplicate(nums: list[int]) -> int:
    """The repeated value, via cycle detection on i -> nums[i]."""
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    probe = 0
    while probe != slow:
        probe = nums[probe]
        slow = nums[slow]
    return probe

Complexity

• Time: O(n) — both Floyd phases are linear in n
• Space: O(1) — three integer cursors

Interview Tips and Follow-Ups

• Starting position matters: index 0 is outside the cycle because no value maps to 0 (values are 1..n). If values were 0-based the reduction breaks — say so.
• Binary search on the value range (count how many are ≤ mid) also solves it in O(n log n)/O(1); naming both earns the follow-up.
• Negation-marking solves it in O(n) but mutates the array — explicitly banned here, and noticing that is part of the test.

That wraps part 8 of the Fast and Slow Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.