Find the Duplicate Number

This is the most surprising use of fast and slow pointers, and a favourite hard-medium question. There is no linked list and no obvious cycle. The rules of the problem forbid every easy approach, and what remains is Linked List Cycle II applied to an array read in a new way.

The problem

You get an array of n + 1 integers. Every value is between 1 and n. Because there are more slots than possible values, at least one value appears more than once. Exactly one value is repeated, although it may appear more than twice. Return that value. You may not change the array, and you may use only O(1) extra space.

• [4, 3, 1, 4, 2] → 4. Here n = 4, and 4 appears at indices 0 and 3.
• [1, 4, 4, 2, 4] → 4. The repeated value appears three times.

Constraints: 1 ≤ n ≤ 10⁵. Can you do it in O(n) time?

Clarifying questions

• Is exactly one value repeated? Yes, but possibly many times. Other values may then be missing.
• May I sort or mark the array? No, it is read-only.
• O(1) space, strictly? Yes. That rules out a set and a counting array.

Approach 1: the simple ways, and why each is ruled out

Compare every pair. Two loops, return the first value that matches another. O(1) space but O(n²) time: at n = 10⁵ that is about 5 × 10⁹ comparisons.

1def find_duplicate_pairs(nums: list[int]) -> int:2    """Compare every pair: O(n^2) time, O(1) space."""3    for i in range(len(nums)):4        for j in range(i + 1, len(nums)):5            if nums[i] == nums[j]:6                return nums[i]7    raise ValueError("no duplicate")

A set. Return the first value already seen. O(n) time, but O(n) space, which the problem forbids.

Sorting. Sort, then look for equal neighbours. O(n log n) time, but it changes the array, which is also forbidden. (Sorting a copy costs O(n) space.)

Every easy route breaks one rule. That is the hint that something structural is going on.

The key insight

Read the array as a function on indices: from index i, go to index nums[i]. Every index has exactly one next index, so starting anywhere and following the arrows walks a chain, just like node.next.

Three facts turn this into Linked List Cycle II:

1. Index 0 is a clean head. Every value is between 1 and n, so no arrow ever points to index 0. Nothing loops back to it, so it sits on the tail, outside any cycle.
2. The chain must cycle. There are n + 1 indices and every arrow points into 1..n. Following arrows forever inside a finite set must revisit an index.
3. The entrance is the duplicate. The entrance of a cycle is a node with two arrows pointing into it: one from the tail and one from inside the loop. Two indices i and j point to the same index exactly when nums[i] == nums[j]. So the entrance index is the repeated value.

For [4, 3, 1, 4, 2]: 0 → 4 → 2 → 1 → 3 → 4. Index 4 is reached from index 0 and from index 3, because nums[0] = nums[3] = 4. The cycle is 4 → 2 → 1 → 3 → 4, its entrance is 4, and 4 is the answer.

Approach 2: Floyd's algorithm on indices

Replace node.next with nums[i] and the head with index 0. Phase 1 finds a meeting point; phase 2 resets one pointer to 0 and walks both one step until they meet.

1def find_duplicate(nums: list[int]) -> int:2    """Treat i -> nums[i] as a linked list from index 0; the duplicate is the cycle entrance."""3    slow = fast = 04    while True:                          # phase 1: move first, then compare5        slow = nums[slow]6        fast = nums[nums[fast]]7        if slow == fast:8            break9    walker = 0                           # phase 2: reset to the head, index 010    while walker != slow:11        walker = nums[walker]12        slow = nums[slow]13    return walker

Both pointers start at 0, so phase 1 must move before it compares, hence while True. There is no end-of-list check, because every index has a next index; the cycle is guaranteed.

Dry run on [4, 3, 1, 4, 2] (arrows: 0→4, 1→3, 2→1, 3→4, 4→2):

The tail is one step long (0 → 4), so phase 2 took a = 1 step, as the Cycle II equation predicts.

Time: O(n). The chain has at most n + 1 distinct indices, so both phases finish within O(n) steps, as in Linked List Cycle II. Space: O(1), three integers. The array is only read.

Edge cases

• Smallest input, [1, 1]. 0 → 1 → 1: index 1 points to itself. Phase 1 meets at 1 after one step; walker goes 0 → 1 and matches. Returns 1.
• The duplicate appears many times. [1, 4, 4, 2, 4] has three arrows into index 4. It is still the only index with more than one arrow into it, so it is still the entrance. Returns 4.
• Duplicate at index 0's target. If nums[0] is the duplicate, the tail is one step, as in the example. Nothing special is needed.

Follow-ups

• "Prove there must be a duplicate." Pigeonhole: n + 1 values placed in n possible slots means some slot gets two.
• "Another O(1)-space method?" Binary search on the value: for a guess m, count how many elements are at most m. If the count exceeds m, the duplicate is at most m. O(n log n) time, O(1) space, array unchanged.
• "What if you may change the array?" Mark visits in place: for each value v, negate nums[abs(v)]; if it is already negative, v is the duplicate. O(n) time, O(1) space, but the input is damaged unless you undo the signs.