Run it
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.
The solutions, in order
Set: O(n) time, O(n) space.
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.
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:
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
| Constraint | Set | Sort | Binary search | Floyd |
|---|
| O(1) space | No | Yes | Yes | Yes |
| No modification | Yes | No | Yes | Yes |
| O(n) time | Yes | No | No | Yes |
| Easy to explain | Yes | Yes | Moderate | Hard |
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
| Case | Behaviour |
|---|
[1, 1] | Returns 1 |
| Value repeated many times | Returns that value |
| Several distinct duplicates | Returns one of them — ask which is wanted |
| Values outside 1..n | Floyd's breaks — the guarantee is required |
| Zero present | Breaks — index 0 would be part of a cycle from the start |
| Array of length 1 | No 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.
Questions people ask
Why does treating the array as a linked list work? Every value is a valid index, so i -> nums[i] is a total function, and iterating it from any start must eventually repeat.
Why is the cycle entrance the duplicate? Two different indices hold the same value, so two nodes point at the same successor — which is exactly a cycle entrance.
What if there are several duplicates? Floyd's returns one. Ask whether that is acceptable.
Why must values be 1 to n rather than 0 to n−1? So that index 0 is outside the cycle and the traversal enters it from the start.
Is binary search here searching the array? No — it searches the value range, using a counting predicate. That is the "binary search the answer" pattern.
Which should I present first? The set version, then the space-constrained ones. Explaining the progression is worth more than producing only the clever answer.
Recap in one screen
- n+1 values in 1..n guarantees a duplicate by pigeonhole.
- The constraints — O(1) space, no modification, better than O(n²) — each eliminate one obvious solution.
- Treating the array as
i -> nums[i] makes it a cycle-detection problem, with the duplicate at the cycle's entrance. - Floyd's tortoise and hare finds it in O(n) time and O(1) space.
- Binary searching the value range is the easier-to-explain O(1)-space answer at O(n log n).