An array nums holds n + 1 integers, every one of them in the range 1 .. n. By the pigeonhole principle at least one value repeats; you are told exactly one value is duplicated, though it may appear many times. Return that value.
- You must not modify the array — no sorting, no marking entries negative
- You may use only
O(1) extra space — no Set, no frequency array - Read
i -> nums[i] as a linked list: since every value is in 1 .. n, no jump ever leaves the array, and the duplicate creates a cycle whose entrance is the answer - Floyd's tortoise-and-hare finds that entrance in
O(n) time and O(1) space