Find the Duplicate Number

Difficulty: Medium

You're given an array of n + 1 integers, where every value is between 1 and n (inclusive). Exactly one value appears more than once — it might appear two times or more — while every other value appears exactly once. Find that repeated value.

You're not allowed to modify the array, and you should use only a constant amount of extra memory (so sorting a copy or using a hash set doesn't count as satisfying the full challenge, even though either would give you a correct answer).

Examples

Input: nums = [1, 3, 4, 2, 2]
Output: 2

Input: nums = [3, 1, 3, 4, 2]
Output: 3

Input: nums = [1, 1]
Output: 1

Constraints

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
Exactly one value in nums repeats (one or more extra times).

Approach

The most direct approach doesn't worry about the space limit at all: remember every value you've seen in a set as you scan the array, and the first value you encounter a second time is the answer.

A better approach uses binary search over the range of possible values rather than over the array's positions. For a candidate midpoint value m, count how many entries in the array are less than or equal to m. If that count exceeds m, the duplicate must be somewhere in the lower half of the range; otherwise it's in the upper half.

The approach that satisfies every constraint at once treats the array as if it encoded a linked list: think of position i as a node whose "next" pointer is nums[i]. Because two different positions inevitably point at the same value, this structure always contains a cycle, and the entry point of that cycle is exactly the duplicated value — which Floyd's tortoise-and-hare cycle detection can find using no extra memory and without changing the array.

Solutions

Brute Force — Track Seen Values

Scan the array once, remembering every value already seen in a set. The first value that turns up a second time is the duplicate. Simple and fast, but it uses memory proportional to the array's size, which the strict version of this problem doesn't allow.

function findDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) return num;
    seen.add(num);
  }

  return -1; // unreachable given the problem's guarantees
}

Time: O(n) · Space: O(n)

Binary Search on the Value Range

Search over candidate values from 1 to n rather than over array positions. For a midpoint value m, count how many numbers in the whole array are <= m. If more than m numbers satisfy that, the duplicate has to be one of the values from 1 to m (there are "too many" small values for that to be a coincidence); otherwise it's above m. Narrowing this range in half repeatedly homes in on the exact duplicate.

function findDuplicate(nums) {
  let low = 1;
  let high = nums.length - 1;

  while (low < high) {
    const mid = Math.floor((low + high) / 2);

    let countLessOrEqual = 0;
    for (const num of nums) {
      if (num <= mid) countLessOrEqual++;
    }

    if (countLessOrEqual > mid) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

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

Optimal — Cycle Detection (Floyd's Tortoise and Hare)

Treat the array as a linked list where the "next" node after position i is position nums[i]. Because there are n + 1 positions but only n possible values to point at, at least two positions must point at the same value — which means this implicit list always loops back on itself, forming a cycle, and the value where the cycle begins is exactly the duplicated number.

First, run slow/fast pointers (slow moves one step, fast moves two) starting from index 0 until they meet somewhere inside the cycle. Then reset one pointer back to the start while leaving the other where it met, and advance both one step at a time — the node where they meet this second time is the entry point of the cycle, which is the duplicate value.

function findDuplicate(nums) {
  // Phase 1: find a meeting point inside the cycle.
  let slow = nums[0];
  let fast = nums[0];

  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Phase 2: find the entrance to the cycle, which is the duplicate.
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
}

Time: O(n) · Space: O(1)