Find Duplicate Number

Array of n+1 ints in 1..n with one duplicate — Floyd cycle detection O(1) space, binary search on counts alternative.

intermediate3 min readUpdated Aug 4, 2026

dsa
arrays
interview
Google
Meta

The problem

nums has n + 1 integers, each in [1, n]. Exactly one number is duplicated (may appear 2+ times). Find it.

Constraints that hurt:

Must not modify the array (or some variants allow)
O(1) extra space preferred
O(n) time preferred

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

Brute options

// sort copy
function findDuplicateSort(nums: number[]): number {
  const a = [...nums].sort((x, y) => x - y);
  for (let i = 1; i < a.length; i++) if (a[i] === a[i - 1]) return a[i];
  return -1;
}

// set
function findDuplicateSet(nums: number[]): number {
  const s = new Set<number>();
  for (const x of nums) {
    if (s.has(x)) return x;
    s.add(x);
  }
  return -1;
}

method	time	space	notes
sort copy	O(n log n)	O(n)	ok baseline
set	O(n)	O(n)	violates O(1) space
mark negatives in place	O(n)	O(1)	mutates

Optimal: treat as linked list cycle (Floyd)

Index i points to nums[i]. Values in 1..n with n+1 entries ⇒ cycle; entrance = duplicate.

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

  // phase 1: meet inside cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // phase 2: entrance
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}


Time	O(n)
Space	O(1)
Mutates?	no

Alternative: binary search on value

For mid m, count how many nums[i] ≤ m. If count > m, duplicate is in [1,m], else (m,n].

function findDuplicateBS(nums: number[]): number {
  let lo = 1;
  let hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    let cnt = 0;
    for (const x of nums) if (x <= mid) cnt++;
    if (cnt > mid) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}


Time	O(n log n)
Space	O(1)

Pigeonhole principle — good if interviewer dislikes Floyd.

Edge cases

Duplicate appears many times
Duplicate is 1 or n
n = 1 → [1,1]

Common mistakes

XOR all with 1..n (fails when duplicate appears >2 times)
Assuming sorted input
Off-by-one in Floyd start

Interview delivery

Constraints: O(1) space, no mutate.
Set/sort as baselines.
Floyd cycle or count BS.
Prove pigeonhole briefly.
Complexities.