Find the Duplicate Number

Medium

Fast & Slow Pointers

Treat values as next-pointers; the duplicate is a cycle entrance.

Pointer Trace

Index i links to index nums[i], so the array is a linked list from 0. slow takes one step: nums[0] = 1.

StopLinked listExport

nums

CH1 slow

Problem

Given an array of n + 1 integers whose values are all in the range 1 through n, exactly one value appears at least twice. Return that repeated value while leaving the array unchanged and using only constant extra space.

Examples

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

Output: 2

The values define links 0 → 1 → 3 → 2 → 4 → 2, so the cycle begins at index 2, whose value is the duplicate 2.

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

Output: 3

The value 3 occurs more than once, so it is the duplicate.

The Goal

nums holds n + 1 numbers, each from 1 to n, so at least one number repeats. Return it without changing nums and with only constant extra space.

For [1, 3, 4, 2, 2], the answer is 2.

Read-only, constant space

Sorting changes the array, and a set takes O(n) extra space. Two pointers that only read nums fit both limits.

Treat the array as a linked list you can follow but not change.

Key Idea: Values Are Links

Treat index i as a node whose next is nums[i]. Every value is from 1 to n, so every link lands on a real index, and nothing links to 0. Start there.

There are only n + 1 indices, so the walk from 0 has to repeat. The index where it first comes back round has two links into it: one from before the loop and one from inside it. Two indices hold that number, so it's the duplicate.

From index i, go to index nums[i].

0 → 1 → 3 → 2 → 4 → 2

The Algorithm

Floyd's method runs two races. In the first, slow takes one link a step and fast takes two, until they meet inside the loop. Then slow goes back to 0, both take one link a step, and they meet where the loop starts.

python

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

The second race works because 0 and the meeting point are the same number of links from the loop's start.

Approach	Time	Extra space	Fits the limits?
Sort, then check neighbors	O(n log n)	O(1) to O(log n)	No: changes nums
Set of numbers seen	O(n)	O(n)	No: extra space grows
Slow and fast pointers	O(n)	O(1)	Yes: only reads nums

Walkthrough

Run it on [1, 3, 4, 2, 2]. The links are 0 → 1 → 3 → 2 → 4 → 2, so the loop is 2 → 4 → 2.

slow starts at 1 and fast at 3. Three steps later both are on 4. They've met inside the loop, but 4 isn't the answer.

slow goes back to 0 and fast stays on 4. Now each takes one link a step, and three steps later both are on 2, the duplicate.

Checkpoint · predict the next step

Step 6 of 16 on the stage: fast steps twice: 4 → 2 → 4.

slow on 2 · fast on 4 · links 0→1, 1→3, 2→4, 3→2, 4→2 · phase 1 · steps 3

What does step 7 show?slow on 0 · phase 2 · steps 0slow on 4 · phase 1 · steps 4slow on 2 · phase 1 · steps 3slow on 3 · phase 1 · steps 2

Step through it on the stage

Pitfalls

Don't mix up an index and the value stored there. slow = nums[slow] follows the link out of index slow.
The first meeting is inside the loop, not at its start. In the example it's 4, and the answer is 2.
In the second race, fast takes one link a step, not two.
A number can appear more than twice. Try Break it with [2, 2, 2, 2, 2]: the answer is still 2.

Why isn't a set the expected answer here?

Complexity

Each race takes O(n) steps. The walk from 0 reaches the loop within n links, and the loop holds at most n indices. So time is O(n).

The only state is two indices, so extra space is O(1), and nums is never written.

Two races, two indices

Time

O(n)

Space

O(1)

Where the time goes

First raceslow and fast meet inside the loop.dominantO(n)
Second raceBoth step one link to the loop's start.dominantO(n)
slow and fastTwo indices. nums is only read.O(1)

How it grows

Roughly what that costs

n	10	100	1,000	10,000
O(n)	10	100	1K	10K

Linear time, constant space, and the array is never written.

In short

Reading each index's value as a link forms a linked list with a cycle, because a repeated value points two indices to the same place. Use Floyd's cycle detection to find the meeting point, then a second walk from the start to locate the cycle's entry — the duplicate.

TimeO(n)SpaceO(1)

Common mistake

Sorting or using a set — correct but violates the classic O(1) space / no-mutation constraints this problem targets.

NextLinked List Cycle →A fast pointer laps a slow one if and only if there's a loop.

Linked List CycleEasy Contains DuplicateEasy