n + 1 numbers in 1..n, one repeated. Treat each value as a pointer to an index: the duplicate starts a cycle, and fast and slow runners find it.
▼The problem
LeetCode 287 (Medium). An array nums holds n + 1 integers, each in [1, n]; exactly one value repeats (possibly many times). Return it without modifying the array and using only O(1) extra space.
Examples (LeetCode's): [1,3,4,2,2] → 2, [3,1,3,4,2] → 3, [3,3,3,3,3] → 3.
The solution
def find_duplicate(nums):
slow = fast = 0
while True: # meet in the loop
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0 # find the entrance
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowTranscript
Find the Duplicate Number. You get n plus one numbers, each from one to n, and one value repeats, maybe many times. Return it without changing the array, in constant extra space.
One, three, four, two, two gives two. Three, one, three, four, two gives three. Five threes give three.
The easy ways break a rule. A hash set costs n extra space. Sorting puts the twins together, but changes the array.
The key idea: each slot is a teleporter pad, and its number is where it sends you. Start on pad zero; no number is zero, so nothing leads back. Two pads send you to the same pad, so the path falls into a loop, and its entrance is the duplicate. It's Linked List Cycle, hiding in an array.
In code, slow jumps once and fast twice until they meet in the loop. Then slow restarts at pad zero, and both jump once. Both are equally far from the entrance, give or take whole laps, so they meet there.
Now one, three, four, two, two. Slow to pad one, fast to pad three. Slow to three, fast to four. Slow to two, fast lands on four again. Slow to four: they meet. Slow restarts at zero. Slow to one, fast to two. Slow to three, fast to four. Slow to two, fast to two: the duplicate is two.
Each phase is a few laps: linear time. Two pointers, and the array never changes: constant space.
Follow the pads, find the loop, find its door. That's Find the Duplicate Number.