Find the Duplicate Number Without Modifying the Array

Pattern: Fast & Slow Pointers (Floyd’s Cycle Detection) · Difficulty: Medium · Asked at: Amazon, Microsoft, Google

Classic version: LeetCode 287

Problem

nums has n + 1 integers, each in the range [1, n], so at least one value repeats. Exactly one value is repeated (possibly more than twice). Return it without modifying nums and using O(1) extra space.

Examples

find_duplicate([1, 3, 4, 2, 2]) → 2
find_duplicate([3, 1, 3, 4, 2]) → 3
find_duplicate([2, 2, 2, 2, 2]) → 2

Starter code

def find_duplicate(nums: list[int]) -> int:
    pass

Hints

Where this shows up in data engineering

A favourite for testing whether you can map an unfamiliar problem onto a known algorithm. Also a good place to discuss constraints: with a mutable array you’d mark visited indices by negating values; with memory you’d use a set; and with read-only, O(1) memory, Floyd.

Solution

def find_duplicate(nums: list[int]) -> int:
    slow = fast = nums[0]
    while True:                         # phase 1: meet inside the cycle
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    p = nums[0]                         # phase 2: walk to the cycle entry
    while p != slow:
        p, slow = nums[p], nums[slow]
    return p

Tests

Your solution should pass these:

assert find_duplicate([1, 3, 4, 2, 2]) == 2
assert find_duplicate([3, 1, 3, 4, 2]) == 3
assert find_duplicate([2, 2, 2, 2, 2]) == 2
assert find_duplicate([1, 1]) == 1
a = [1, 4, 4, 2, 4]
assert find_duplicate(a) == 4 and a == [1, 4, 4, 2, 4]

Explanation

The mapping: nodes are indices 0..n, edges are i → nums[i]. Values are in [1, n], so the walk from 0 stays inside 1..n forever and must cycle. The duplicated value d has two incoming edges (from two indices holding d): one from the tail leading into the cycle and one from inside it, so d is the cycle’s entry node.

Then Floyd’s two phases find the entry. O(n) time, O(1) space, read-only.

Other approaches and why they’re excluded: sorting (modifies or copies), set (O(n) memory), sum formula (fails when the value repeats more than twice), and binary search on the value range counting ≤ mid (O(n log n), read-only, O(1); a good second answer).

Follow-up questions