Find the duplicate number

Treat each value as a pointer to an index. Because values are in 1..n and there are n+1 of them, following those pointers must eventually revisit a node — and the entrance to that cycle is the duplicate. Floyd's tortoise and hare finds it in O(n) time and O(1) space.

Lists & arraysCoding problemHard

Step through it

What to watch

  • The two pointers move at different speeds until they meet.
  • Meeting is not the answer — phase two finds the entrance.
  • Nothing is written to the array and nothing is allocated.

Say this out loud

"The constraints rule out sorting and a set. If you read each value as a next-pointer, the array is a linked list that must contain a cycle, and the cycle entrance is the duplicate - so it's Floyd's algorithm."

Overview

Given n+1 values from 1 through n, there must be a duplicate. Under the no-modification and constant-space constraints, interpret each value as a next index and use cycle detection to locate the repeated value.

In this guide
  1. Run it: Find the duplicate number in code
  2. The solutions, in order
  3. Read the constraints first
  4. Turning the array into a linked list
  5. Why phase two works
  6. Why it is a cycle problem
  7. The constraints and which solution each allows
  8. Edge cases and assumptions
  9. The related problems
  10. Sources and next steps

Run it: Find the duplicate number in code

Floyd's two phases with the pointer positions printed, checked against a set-based version on random inputs, plus the binary-search-on-value alternative.

1Python
Output
2Python
Output
3Python
Output

The solutions, in order

Set: O(n) time, O(n) space.

4Python
Output

Sort: O(n log n) time, O(1) extra space — but it modifies the array.

Binary search on the value range: O(n log n) time, O(1) space, no modification.

5Python
Output

The reasoning: if there are more than mid values less than or equal to mid, the duplicate must be in [lo, mid] by pigeonhole. This is binary searching the answer rather than an array — a technique worth recognising, because it applies whenever a predicate over the answer space is monotonic.

Floyd's cycle detection: O(n) time, O(1) space, no modification — the intended answer.

Read the constraints first

The easy answers are all excluded on purpose. A set is O(n) space. Sorting modifies the array. Marking visited indices by negating them modifies it too. Each constraint removes one obvious solution, and what is left is the intended one — which is why reading the constraints aloud is a real technique, not a stall.

Turning the array into a linked list

Start at index 0 and repeatedly jump to the index named by the current value. Values are in 1..n, so no jump leaves the array and no jump lands on index 0 — index 0 is the start of the chain and never re-entered.

There are n+1 slots and only n distinct values, so two slots share a value, so two different nodes point at the same next node. That shared target is where the chain closes into a loop, and it is the duplicate value.

Why phase two works

Once the pointers meet inside the loop, the distance from the head to the loop entrance equals the distance from the meeting point to the entrance. So walking one pointer from the start and one from the meeting point, one step at a time, makes them meet exactly at the entrance.

It looks like magic and falls out of the arithmetic. Say that the same two-phase structure detects a cycle in an actual linked list — the interviewer is usually checking whether you recognise the algorithm rather than whether you can rederive the proof.

Why it is a cycle problem

The reframing is the insight, and it is not obvious.

Treat the array as a function: from index i, jump to index nums[i]. Since every value is between 1 and n, every jump lands on a valid index, so following the jumps from index 0 traces a path.

That path must eventually repeat, because there are finitely many indices — so it enters a cycle. And the entrance to the cycle is the duplicated value, because two different indices point at it.

For [1, 3, 4, 2, 2]: 0 → 1 → 3 → 2 → 4 → 2 → 4 → … The cycle is 2 → 4 → 2, entered at 2, which is the answer.

So the problem is "find the entry point of a cycle in a linked list", and Floyd's tortoise-and-hare algorithm solves that in O(1) space:

6Python
Output

Phase 1 finds some point inside the cycle. Phase 2 resets one pointer to the start and advances both one step at a time; they meet at the cycle's entrance. That second phase is a result about the distances involved, and it is worth knowing rather than deriving under pressure.

The constraints and which solution each allows

ConstraintSetSortBinary searchFloyd
O(1) spaceNoYesYesYes
No modificationYesNoYesYes
O(n) timeYesNoNoYes
Easy to explainYesYesModerateHard

Floyd's is the only one satisfying all three constraints, which is why the constraints are stated as they are.

In an interview, the right sequence is to give the set solution immediately, note that it uses O(n) space, then binary search for O(1) space at O(n log n), and then Floyd's for O(n) with O(1) space. Presenting the progression demonstrates more than jumping to the final answer, and it is a safer route if the cycle insight does not arrive.

Edge cases and assumptions

CaseBehaviour
[1, 1]Returns 1
Value repeated many timesReturns that value
Several distinct duplicatesReturns one of them — ask which is wanted
Values outside 1..nFloyd's breaks — the guarantee is required
Zero presentBreaks — index 0 would be part of a cycle from the start
Array of length 1No duplicate can exist; the constraints exclude it

The zero case matters: Floyd's relies on index 0 not being a target, so that the path from 0 leads into the cycle rather than starting inside it. That is why the problem specifies values from 1 to n rather than 0 to n−1.

Find all duplicates. Floyd's finds one. For all of them, either use a set (O(n) space), or if modification is allowed, mark visited values by negating nums[abs(x)-1] — O(1) space using the array itself as the marker.

Find the missing number. XOR all values with 1..n, or use the sum formula. Different technique.

Find both a missing and a duplicated number. Sum and sum-of-squares gives two equations in two unknowns.

Linked list cycle detection. The original setting for Floyd's algorithm.

Happy number. Also Floyd's — iterating a function and detecting whether it cycles.

The unifying idea: Floyd's algorithm applies to any function iterated on itself, not only to linked lists. Recognising that a problem is "iterate a function, find where it cycles" is what makes the technique available.

For the underlying ideas, see cycle detection, binary search and time complexity.

Sources and next steps

How the code works

Floyd's two phases with the pointer positions printed, checked against a set-based version on random inputs, plus the binary-search-on-value alternative.

How the code works

  1. fast = values[values[fast]]Two jumps to the tortoise's one. Inside a loop the gap closes by one node per step, so they are guaranteed to meet.
  2. meeting is not the answerPhase one only proves a cycle exists and finds a point inside it. Returning slow here is the most common way to get this almost right.
  3. while finder != slow:Phase two. The distance from the head to the entrance equals the distance from the meeting point to the entrance, so two pointers advancing in step converge exactly on it.
  4. binary_search_on_valueThe alternative worth naming: count values ≤ mid and use pigeonhole to pick a half. O(n log n) time, O(1) space, and much easier to derive under pressure.

Change one thing

  • Put the duplicate at both ends — [2, 3, 4, 2]. The step count changes and the answer does not.
  • Return meeting instead of finder. It is right often enough to pass a careless test and wrong in general.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Why can the array be treated as a linked list?

  2. The meeting point of the two pointers is:

  3. Which constraint rules out using a set?

Cheat sheet

Find the duplicate number

Find the one duplicate in an array of n+1 integers from 1 to n without extra space. Apply Floyd's cycle detection and see why it works here.

INTERVIEW · vizlearn.in/interview/find-the-duplicate-number.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.