Find the Duplicate Number

1. Define the problem

Given an array of n + 1 integers where every value is between 1 and n, there is exactly one repeated value (it may repeat more than once). Find that duplicate number without modifying the array and using only constant extra space. Treat each value as a pointer to another index — this turns the array into a linked list where the duplicate value creates a cycle, and Floyd's cycle detection (the classic slow/fast pointer trick) finds exactly where that cycle begins.

Constraints

1 ≤ n ≤ 10⁵
nums.length == n + 1
1 ≤ nums_i ≤ n
There is exactly one repeated number in nums, but it may repeat more than once.

Example

Inputnums = [1, 3, 4, 2, 2]

Output2

Explanation Following the chain of indices 0 → 1 → 3 → 2 → 4 → 2 loops back onto index 2, revealing that 2 is the duplicate.

2. Know the words first

In plain terms

Pointer to another index: Instead of reading nums_i as just a number, treat it as "go to index nums_i next" — the same idea used to walk a linked list.

3. Visualize the solution

Slow and fast pointers meet inside the cycle, then find its start

Statusinit

Start both slow and fast at nums[0] = 1.

What happens in this step

slow = nums[0] = 1
fast = nums[0] = 1

Step 1 of 6

Steps to visualize

Start both slow and fast at nums₀, then move slow one step (to nums_slow) and fast two steps (to nums[nums_fast]) per round.
Because a value repeats, this chain must eventually loop, so slow and fast are guaranteed to meet somewhere inside that loop.
Once they meet, reset slow back to nums₀ but leave fast where it is.
The highlight box always stretches between the two pointer positions, whichever one is further left.
Now move both one step at a time — the index where they meet again is exactly the duplicate value.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Slow and fast pointers meet inside the cycle, then find its start

Statusinit

Start both slow and fast at nums[0] = 1.

What happens in this step

slow = nums[0] = 1
fast = nums[0] = 1

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

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

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

  slow = nums[0];

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

  return slow;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 3, 4, 2, 2]`	`2`	example from the docstring
`nums = [1, 1]`	`1`	smallest valid input: n = 1 with the only possible value repeated
`nums = [3, 1, 3, 4, 2]`	`3`	the duplicate value sits at the very first index
`nums = [2, 2, 2, 2, 2]`	`2`	the same value repeated across every position
`nums = [1, 2, 3, 4, 4]`	`4`	the duplicate is the largest allowed value
`nums = [2, 4, 1, 4, 3]`	`4`	the duplicate is reached partway through a longer chain

Find the Duplicate Number