Find the Duplicate Number
An array of n + 1 integers holds values in [1, n]. One value repeats. Find it without modifying the array and in O(1) space.
Intuition
Read each index as a pointer i → nums[i]. Because two indices share a value, this functional graph contains a cycle, and the duplicate is the cycle's entrance. Floyd's tortoise and hare finds that entrance without extra space.
Approach
The easy solutions each break a rule
A hash set finds the repeat instantly but uses O(n) space; sorting finds it but mutates the array. The problem forbids both. To respect 'read-only and O(1) space' we need to see hidden structure in the input — and there's a beautiful one: the values themselves can be read as pointers.
Read the array as a linked list with a cycle
Interpret each index as a pointer: i leads to nums[i]. Because there are n+1 slots but values only range over [1, n], two different indices must point to the same place — and that collision means following the pointers eventually revisits a node, i.e. forms a cycle. Crucially, the entrance of that cycle is exactly the duplicated value, because that's the value two indices point into.
Floyd's two-phase cycle finding
Now it's the classic 'find the start of a cycle' problem. Phase 1: move slow one hop and fast two hops until they meet somewhere inside the loop (a fast pointer must lap a slow one in a cycle). Phase 2: reset slow to the start and advance both one hop at a time; the distance arithmetic of Floyd's algorithm guarantees they collide precisely at the cycle's entrance — the duplicate. Only index reads, two variables: O(n) time, O(1) space, array untouched.
Solution & live demo
Edge cases
Floyd's method finds the cycle entrance regardless of how many times the value repeats.
Indexing by value, not position, makes the location in the array irrelevant to the cycle math.
Only index reads are used; the array is never written, satisfying the no-modify rule.