Find the Duplicate Number

MediumLinked ListArrayTwo PointersBinary Search

Problem

You are given an array of n + 1 integers where every value lies between 1 and n inclusive. Exactly one value is duplicated, possibly more than twice. Find the duplicate without modifying the array and without extra space proportional to its size.

Example. In [1, 3, 4, 2, 2], there are five entries with values between 1 and 4, and the duplicate is 2.

Key idea

Sorting or recording seen values in a hash set both find the duplicate easily, but sorting changes the array's order and a hash set uses space proportional to the input; both violate the constraints here. The fix is to stop thinking of this as an array problem: treat each index as a node, and the value stored there as a pointer to the next index to visit.

Because n + 1 values are squeezed into the range 1 through n, at least one value must be shared by two indices, meaning two "pointers" lead into the same node: the structure of a cycle. The duplicate value is that cycle's entry point. Floyd's fast-and-slow technique applies directly: walk two pointers through the array, one and two steps at a time from index 0, until they meet inside the cycle. Then reset one pointer to index 0 and advance both one step at a time; where they next meet is the duplicate number.

Solution

function findDuplicate(nums: number[]): number {
  let slow = nums[0];
  let fast = nums[nums[0]];

  while (slow !== fast) {
    slow = nums[slow]; // one step
    fast = nums[nums[fast]]; // two steps, guaranteed to meet slow inside the cycle
  }

  slow = 0; // restart from the start, keep fast where it is
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast]; // now both move one step; they meet at the cycle entrance
  }

  return slow;
}

Complexity

  • Time: O(n). A bounded number of linear passes through the implicit pointer chain.
  • Space: O(1). Only a couple of index variables are tracked, and the array itself is never altered.

Watch out for

  • This technique depends on values being confined to 1 through n with one extra entry: that constraint guarantees a cycle exists.
  • The second phase must restart one pointer from index 0, not continue from wherever it stopped.
  • Keep index and value roles straight, since values are being reinterpreted as pointers to other indices.

Pattern

This reuses the fast/slow cycle-detection pattern from Linked List Cycle, applied to an array by recognizing a linked structure hidden inside index-value relationships.

Related questions