4.9.8 — Find the Duplicate Number

LeetCode 287 · Medium

The problem

An array of n + 1 integers holds values between 1 and n. Exactly one value is repeated, possibly many times. Find it.

[1, 3, 4, 2, 2]      →  2
[3, 1, 3, 4, 2]      →  3

The constraints are the problem: you may not modify the array, and you must use O(1) extra space.

The Plain-English Breakdown

You have an array of length N+1. It contains integers from 1 to N. Because there are N+1 slots but only N possible numbers, the Pigeonhole Principle guarantees that at least one number MUST appear more than once. Your job is to find that duplicated number.

Constraints to note:

• Array length up to 10^5.
• Values are strictly in the range [1, N].
• NO modifying the array.
• ONLY O(1) extra space.
• O(N^2) time will fail.

(This replaces the Brute Force section, since brute forces are explicitly listed below as "banned").

Why the easy answers are banned

• A hash set — O(n) space. Banned.
• Sorting, then checking neighbours — modifies the array. Banned.
• Marking visited values by negating nums[abs(x)] — also modifies the array. Banned.
• Counting sort — O(n) space. Banned.

When a problem forbids every obvious approach, the constraints are a hint about which structure the setter has in mind. That is worth internalising as a general habit: read what is forbidden and ask what is left.

What is left here is very little, which is why the intended solution is surprising.

The pattern

Treat the array as a function: from index i, go to index nums[i].

That is legal because every value is between 1 and n, so every value is a valid index in an array of size n + 1. Each position has exactly one successor. That is a linked list, built out of an array with no pointers at all.

Now, why must this list have a cycle, and why does the cycle entrance give the answer?

Start at index 0. Nothing points to index 0, because values are at least 1 — so index 0 is outside any cycle, which makes it a safe starting point. Follow the chain. There are n + 1 positions and only n distinct values, so by the pigeonhole principle some value repeats, meaning two different positions point to the same place. That is a merge point, and a merge in a single-successor graph creates a cycle.

The node where the cycle begins is the position pointed to by two different indices — that is, the duplicated value.

[1, 3, 4, 2, 2]

index:  0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
                    ↑_______|

the cycle entrance is 2, and 2 is the answer

The solution

This is Floyd's cycle detection from 4.9.7, with nums[i] in place of node.next.

Python

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # phase 1 — find a meeting point inside the cycle
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # phase 2 — walk from the start and from the meeting point
        slow2 = 0
        while slow != slow2:
            slow = nums[slow]
            slow2 = nums[slow2]

        return slow

TypeScript

function findDuplicate(nums: number[]): number {
  let slow = 0, fast = 0;
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  let slow2 = 0;
  while (slow !== slow2) {
    slow = nums[slow];
    slow2 = nums[slow2];
  }

  return slow;
}

Phase 1 advances one and two steps until they land on the same index. That index is somewhere inside the cycle, not necessarily its start.

Phase 2 uses the arithmetic derived in 4.9.7: the distance from the start to the cycle entrance equals the distance from the meeting point to the entrance, up to whole laps. So restart one pointer at 0, move both one step at a time, and they meet at the entrance.

No while fast and fast.next guard is needed. In the linked-list version the list might end; here there is always a cycle, so the walk never falls off.

Both phases start at index 0, which is guaranteed to be outside the cycle because no value is 0.

ELI5 Analogy: Imagine every value in the array is a signpost telling you which index to visit next. Because multiple indices contain the duplicated number, multiple signposts point to the exact same index. If you follow the signposts, you will eventually walk into that heavily-pointed-to index, and then get trapped in a loop forever! The duplicated number IS the entrance to that loop. We just use a slow runner and a fast runner to find the loop, and then a math trick to find exactly where the loop starts.

Code Walkthrough (Floyd's Algorithm)

1. Phase 1 (Finding the intersection): We start slow and fast pointers at index 0. We enter a while True loop.
2. The Jump: slow takes one step by reading the value at its current index (nums[slow]). fast takes two steps by reading the value, and then reading the value at that index (nums[nums[fast]]).
3. The Meeting: Because there is a cycle, the fast pointer will lap the slow pointer and they will eventually land on the exact same index. When slow == fast, we break. They are now somewhere inside the cycle.
4. Phase 2 (Finding the entrance): We leave slow exactly where it is. We start a new pointer, slow2, at the very beginning (index 0).
5. The Synchronized Walk: Both slow and slow2 now take exactly one step at a time. The math of Floyd's Cycle Detection guarantees that they will collide exactly at the entrance of the cycle.
6. The Result: The index they collide on IS the duplicated number. We return it.

Complexity

O(n) time, O(1) space, and the array is untouched. That is the only solution meeting all three constraints.

Derivation:

• Time Complexity: In Phase 1, the slow pointer enters the cycle in at most N steps, and fast catches it in at most N more steps. In Phase 2, both pointers walk to the entrance in at most N steps. Maximum total steps is roughly 3N, making it O(N) time.
• Space Complexity: Only slow, fast, and slow2 pointers are allocated. This is O(1) auxiliary memory.

The binary search alternative

There is a second solution, and it is easier to arrive at under pressure.

Binary search on the answer rather than on the array. Pick a candidate value m, and count how many array elements are less than or equal to m.

If there were no duplicate, exactly m elements would be ≤ m. So:

• count > m → the duplicate is in the range [low, m].
• count ≤ m → the duplicate is in [m+1, high].

def findDuplicate(self, nums):
    low, high = 1, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        count = sum(1 for x in nums if x <= mid)
        if count > mid:
            high = mid
        else:
            low = mid + 1
    return low

O(n \log n) time, O(1) space, no mutation. Slower, but it also satisfies the constraints and it is far easier to derive from scratch. This is binary search on the answer, which gets its own treatment in 4.11.

In an interview, offer this first if the cycle idea has not arrived. A correct O(n \log n) beats a stalled O(n).

What the interviewer will push on

"Why is there guaranteed to be a cycle?" n + 1 positions, n possible values, so two positions share a value by pigeonhole, and a merge in a single-successor graph makes a cycle.

"Why is index 0 outside the cycle?" No value is 0, so nothing points to index 0.

"Why does the cycle entrance equal the duplicate?" The entrance is the position that two different indices point to, and those two indices hold the same value.

"Can you do it another way?" Binary search on the answer. Naming both, and the trade between them, is the complete answer.

"What if the array could be modified?" Then the problem is easy: swap each value to its home index, or negate nums[abs(x)] as a visited flag, both O(n) time and O(1) space.

One thing to volunteer: say why the obvious solutions are banned before you solve it. "No extra space rules out a set, and no mutation rules out sorting and marking — so the constraints are pointing at something else." That reasoning is the skill being tested, more than the trick itself.

Next: 4.9.9 LRU Cache — a design problem, and the clearest example in the book of two data structures combined to cover each other's weakness.