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.

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.

Complexity

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

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.