Find the Duplicate Number (LeetCode 287)

The problem

You get an array nums of length n + 1. Every value is between 1 and n, and exactly one value repeats (it may repeat more than twice). Return that value. You must not modify the array, and you may only use O(1) extra space.

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

Five slots hold values from 1 to 4, so by the pigeonhole principle some value must repeat. Here it is 2.

How to think about it

Start with brute force. A set of seen values finds the duplicate in O(n) time but uses O(n) space. Sorting and checking neighbours is O(n log n) but modifies the array. Comparing every pair is O(n²). Each breaks one of the rules.

The key insight: the array is a linked list. Read each index i as a node whose next is nums[i]. Because every value is in 1..n, every “next” is a valid index, so following the links from index 0 never falls off and must eventually loop. Index 0 is never a target (no value is 0), so it is a clean starting point outside any cycle.

Why the cycle’s entrance is the duplicate. The entrance of a cycle is a node with two incoming arrows: one from the path leading in, one from the end of the loop. Two incoming arrows means two indices i and j with nums[i] == nums[j]. That shared value is the duplicate. So the problem becomes “find where the cycle starts”, which Floyd’s algorithm does in O(1) space.

Which pattern is this? Fast & slow pointers on an implicit linked list, plus the head-reset trick from Linked List Cycle II. The tell is “values are in the range of the indices, and you can’t use extra space”.

Approach

1. Start s and f at nums[0].
2. Repeat: s = nums[s] (one step), f = nums[nums[f]] (two steps), until s == f.
3. Reset s to nums[0]. Keep f at the meeting point.
4. Step both one at a time (s = nums[s], f = nums[f]) until they are equal.
5. Return s: the cycle entrance, which is the duplicate value.

Solution

def find_duplicate(nums):
    s = f = nums[0]
    while True:
        s = nums[s]; f = nums[nums[f]]     # tortoise 1 step, hare 2 steps
        if s == f: break                   # met inside the cycle
    s = nums[0]                            # restart one pointer from the "head"
    while s != f: s = nums[s]; f = nums[f] # both 1 step: meet at the entrance
    return s
# find_duplicate([1,3,4,2,2]) -> 2

Dry run

On [1, 3, 4, 2, 2], the links from index 0 are 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 …, so the cycle is 2 -> 4 -> 2 and its entrance is 2.

On [3, 1, 3, 4, 2] the same code returns 3, and on [1, 1] it returns 1.

Complexity

• Time: O(n). Both phases are the Floyd walks from Linked List Cycle II, each linear in the number of nodes.
• Space: O(1). Two integer pointers. The array is never written to.

Edge cases and pitfalls

• The duplicate appears many times (for example [2, 2, 2, 2]): there is still exactly one node with several incoming arrows, and the algorithm still returns it.
• Starting at index 0 matters. No value equals 0, so index 0 is not inside the cycle and behaves like a list head. Starting elsewhere can put you inside the cycle with no “tail” to measure.
• do-while shape. Both pointers start equal, so the meeting loop must move before it checks. That is why it uses while True with a break.
• Other valid answers include binary search on the value range (count how many values are ≤ mid), which is O(n log n) and also O(1) space. Floyd’s is the expected optimal answer.

Related problems

• Linked List Cycle II (LeetCode 142): the same algorithm on real nodes.
• Happy Number (LeetCode 202): another sequence defined by a “next” function.
• Missing Number (LeetCode 268): the mirror problem on a 0..n array, solved with XOR or a sum.