visual walkthrough
Find the Duplicate Number
Treating an array as a linked list to find a cycle; a famous insight.
The idea
Each value is between 1 and n, so it's also a valid index. Read nums[i] as "the next node after i" and the array becomes a linked list.
The duplicate value is pointed to from two different indexes, so it's where a cycle begins. Linked List Cycle II's two-phase trick finds it with no extra memory.
Complexity
| approach | time | space |
|---|---|---|
| Remember what you've seen | O(n) | O(n) |
| Cycle detection on indexes | O(n) | O(1) |