Find the Duplicate Number – Solution & Complexity

• Sorting would either modify the array or require copying it first.
• A hash set finds the duplicate quickly, but it uses O(n) extra memory.
• The intended trick is to treat each index as a node with one outgoing edge: i -> nums[i]. Because values stay in [1, n], following pointers from index 0 must eventually enter a cycle, and the duplicate value is the cycle's entrance.

• Scan the array and remember values seen so far.
• The first value you encounter twice is the answer.
• This is correct and runs in O(n) time, but it violates the constant-space requirement, so it is only a warm-up.

• Think of index i as a node whose next pointer is nums[i]. Since every nums[i] is between 1 and n, once you move from index 0, you stay inside the node set 1..n.
• There are n + 1 indices but only n possible next-node values, so following pointers from 0 must eventually revisit a node: a cycle exists.
• The duplicate value is exactly the first node with two incoming edges on that reachable path, so it is the cycle entrance.
• Floyd's algorithm first finds any meeting point inside the cycle, then resets one pointer to the start and advances both one step at a time; they meet at the entrance.

• Start slow one step from the start and fast two steps from the start.
• Move slow by one edge and fast by two edges until they meet inside the cycle.
• Then reset a finder pointer to index 0, move finder and slow one step at a time, and return where they meet. That meeting value is the duplicate number.

The pointer graph is 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> ..., so the cycle starts at value 2.

Phase 1: find a meeting point inside the cycle

They first meet at value 4, which is inside the cycle but is not necessarily the duplicate.

Phase 2: find the cycle entrance

Now both pointers meet at 2, so the duplicate number is 2.

• Returning the first slow == fast meeting point directly. That point is somewhere inside the cycle, not always the duplicate value itself.
• Starting both pointers at nums[0]; that can make them appear to meet immediately before any real progress. Use one step vs. two steps at initialization.
• Mixing up indices and values, or subtracting 1 as if the graph were zero-based on 1..n. The values already are valid next indices for this construction.
• Using sorting or a hash set in the final answer, which breaks the read-only or constant-space constraints.

• Smallest valid input: [1,1] immediately forms a one-node cycle, so the answer is 1.
• A duplicate may appear three or more times, such as [2,5,9,6,9,3,8,9,7,1,4]; the entrance is still 9.
• The duplicate value can appear in the first array slot, the last slot, or only after a long tail before the cycle begins.
• The answer is the repeated value, not the index of one occurrence.

Treating the array as a functional graph lets Floyd's cycle detection find the duplicate in O(n) time with O(1) extra space, without modifying nums.