vizlearn

Find the duplicate number

Interview QuestionsBy Updated

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.

Overview

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.

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."

Find the duplicate number

An array of n+1 integers holds values from 1 to n. Find the duplicate without modifying the array and in O(1) space.

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.

Run it in Python

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.

find_duplicate.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/find-the-duplicate-number.html
More in Interview
InterviewKth largest elementInterviewTrapping rain waterInterviewSort an array of 0s, 1s and 2sInterview3Sum
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.
About VizLearnGitHubLinkedInContact