2026-09-19 — Find the Duplicate Number

The two easy solutions are ruled out on purpose: a hash set is O(n) space, sorting modifies the input. Binary search on the value range (counting how many elements are ≤ mid) is a genuine O(n log n), O(1) answer and worth mentioning.

For the O(n) solution, look at the array differently. Treat each index as a node that points to the node at nums[i]:

i = 0 -> nums[0] -> nums[nums[0]] -> ...

Because values are in 1..n and there are n+1 slots, following those pointers from index 0 can never run off the end. What must eventually happen? And what does the duplicate correspond to in that structure?

def find_duplicate(nums: list[int]) -> int:
    # Phase 1: find a meeting point inside the cycle.
    slow = fast = nums[0]
    while True:
        slow = nums[slow]              # one step
        fast = nums[nums[fast]]        # two steps
        if slow == fast:
            break

    # Phase 2: walk from the start and from the meeting point, one step each.
    # They meet at the cycle's entrance, which is the duplicated value.
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

How it works. Treat the array as a function i -> nums[i]. Since all values lie in 1..n, following it from index 0 stays in bounds forever, so the sequence must eventually revisit a value — it contains a cycle.

The entrance to that cycle is a value reachable from two different predecessors, which is exactly the duplicated number: two distinct indices hold the same value, so two nodes point at it.

From there it is Floyd's tortoise and hare. Phase 1 finds a point inside the cycle. Phase 2 finds the entrance: the distance from the start to the entrance equals the distance from the meeting point to the entrance, going forward, so advancing both one step at a time makes them meet there.

Complexity. Time: O(n). Space: O(1) — three integer variables, and the array is never written to.

Edge cases that matter. - [1, 1] — the smallest possible input. - All elements identical, e.g. [2, 2, 2, 2, 2]. - The duplicate appearing more than twice — the argument does not depend on it appearing exactly twice. - Starting at index 0 is important: index 0 can never be inside the cycle, because no value is 0, so nothing points at it.

Common wrong answer. return sum(nums) - sum(set(nums)) finds the duplicate only when it appears exactly twice; it silently gives the wrong answer for [2, 2, 2, 2, 2], and set() is O(n) space anyway.

Worth saying out loud. Name the two easier solutions and why they are excluded, then give the binary-search-on-value-range answer (O(n log n), O(1)), then this one. Showing the ladder of solutions is worth more than jumping straight to the clever one.