AlgoMaster Logo

Find the Duplicate Number

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have an array of n + 1 integers, and every value falls in the range [1, n]. By the pigeonhole principle, at least one number must be repeated. Our job is to find that duplicate.

The pair of constraints is what makes this problem hard: we cannot modify the array, and we can only use O(1) extra space. That rules out sorting the array and also rules out using a hash set.

The values in the array are all between 1 and n, and the indices are 0 through n. If we treat each value nums[i] as a pointer to another index, we create a graph where each node has exactly one outgoing edge. Since there are n + 1 nodes but only n possible destinations, at least two nodes must point to the same destination. That creates a cycle, and the entry point of that cycle is the duplicate number.

Key Constraints:

  • nums.length == n + 1 and 1 <= nums[i] <= n → There are more elements than the range of values allows, so by the pigeonhole principle, a duplicate is guaranteed.
  • Do not modify the array → Sorting is off limits. Any approach that rearranges elements (like cyclic sort) won't work here.
  • Only constant extra space → No hash sets, no frequency arrays. We need an O(1) space solution.

Approach 1: Brute Force (Nested Loops)

Intuition

For every element, check whether it appears anywhere else in the array. If two elements have the same value, that value is the duplicate. This approach ignores the space and modification constraints, so it serves only as a baseline.

Algorithm

  1. For each index i from 0 to n - 1:
  2. For each index j from i + 1 to n:
  3. If nums[i] == nums[j], return nums[i].
  4. This is guaranteed to find the duplicate since one must exist.

Example Walkthrough

1Initialize: compare every pair to find a match
0
i
1
1
3
j
2
4
3
2
4
2
1/6

Code

This approach is simple but too slow for the given constraints. The next approach counts how many values fall in a given range and uses binary search to narrow down the duplicate.

Approach 2: Binary Search on Value Range

Intuition

Instead of binary-searching the array itself, we binary-search the answer space: the range of possible values [1, n]. This rests on the pigeonhole principle. Pick any value mid in the range [1, n] and count how many numbers in the array are less than or equal to mid. If there is no duplicate in the range [1, mid], that count is exactly mid. If the duplicate falls in [1, mid], the count is greater than mid.

So we can binary search: if count > mid, the duplicate is in the lower half [1, mid]. Otherwise, it is in the upper half [mid+1, n].

Algorithm

  1. Set low = 1 and high = n (the range of possible values, not indices).
  2. While low < high:
    • Compute mid = low + (high - low) / 2.
    • Count how many elements in nums are less than or equal to mid.
    • If count > mid, the duplicate is in the range [low, mid], so set high = mid.
    • Otherwise, the duplicate is in the range [mid+1, high], so set low = mid + 1.
  3. When low == high, that value is the duplicate.

Example Walkthrough

1Initialize: search value range [1, 4], low=1, high=4
0
1
1
3
2
4
3
2
4
2
1/6

Code

The binary search approach respects both constraints but scans the array O(log n) times. The optimal approach treats the array as an implicit linked list with a cycle and finds the duplicate in linear time.

Approach 3: Floyd's Cycle Detection (Optimal)

Intuition

Since every element is in the range [1, n] and the array has indices [0, n], we can treat the array as a function: f(i) = nums[i]. Starting from index 0, we follow the chain: 0 → nums[0] → nums[nums[0]] → ....

Because the values are in [1, n], following this chain never returns to index 0 (no value equals 0, so nothing points back to it). Since there are only n possible destinations and we keep following links, the chain must eventually enter a cycle. The entry point of this cycle is the duplicate number: two different indices hold the same value, so two arrows point into the same node, which is where the cycle begins.

We use Floyd's tortoise and hare algorithm in two phases:

  1. Phase 1 (Detect the cycle): Move a slow pointer one step at a time and a fast pointer two steps at a time. They will eventually meet inside the cycle.
  2. Phase 2 (Find the entrance): Reset one pointer to the start (index 0) and move both pointers one step at a time. They will meet at the cycle entrance, which is the duplicate value.

Algorithm

  1. Initialize slow = nums[0] and fast = nums[nums[0]].
  2. Phase 1: While slow != fast, move slow = nums[slow] and fast = nums[nums[fast]].
  3. Phase 2: Set slow = 0. Then while slow != fast, move slow = nums[slow] and fast = nums[fast].
  4. Return slow (or fast, they are equal).

Example Walkthrough

1Phase 1: slow=nums[0]=1, fast=nums[nums[0]]=3
0
1
1
slow
3
2
4
3
2
fast
4
2
1/8

Code