You are given nums, a list of n + 1 integers, each between 1 and n. There are more numbers than
possible values, so some value must appear more than once. Here exactly one value does, though it
may appear more than twice.
Return that repeated value. Don't change nums (no sorting it and no marking its entries), and
use only a constant amount of extra memory, so no set or extra list.
Example 1
- Input
- nums = [2, 5, 1, 4, 3, 5]
- Output
- 5
Example 2
- Input
- nums = [4, 4, 4, 1, 4]
- Output
- 4
Constraints
- 1 ≤ n ≤ 10⁵, and
numsholds n + 1 numbers. - Every number is between 1 and n.
- Exactly one value appears two or more times; every other value appears at most once.
Show the pattern
Linked list, Binary search
Read each value as a pointer to the position it names, and the list becomes a chain of next pointers that must loop. The repeated value is where the loop begins, and fast and slow pointers find that in constant space.
See linked list in a visualiserShow the approach
Think of position i as a node whose next node is nums[i]. Every value is between 1 and n, so a
walk that starts at position 0 never leaves the list and never comes back to 0; it must end up
going round a loop. The node where the loop begins is entered from two different positions, so
those two positions hold the same value. That value, the loop's entrance, is the answer.
Floyd's cycle finding locates the entrance. Move slow one step at a time (slow = nums[slow])
and fast two (fast = nums[nums[fast]]) until they meet inside the loop. Then put slow back at
the start and move both one step at a time: they meet again exactly at the entrance.
(Binary search on the answer also uses constant memory, in O(n log n) time: count how many
numbers are at most mid; more than mid of them means the repeat is at most mid.)
Time: O(n) · Space: O(1)