Fast and slow pointers
Two runners at different speeds detect cycles and find midpoints without extra memory.
Find the Duplicate Number. nums has n + 1 integers, each in 1..n, and exactly one value repeats (possibly many times). Find it without modifying the array and with O(1) extra space.
Signals that point here
- Linked lists: detect a cycle, find where it starts, find the middle, check a palindrome.
- Any function
f(x)iterated from a start value: "happy number", sequences that must repeat. - A constraint of
O(1)space where a hash set would be the obvious answer.
The idea
Treat i -> nums[i] as a linked list. Values are in 1..n so every arrow lands inside the array, and the duplicate value is a node with two incoming arrows: the entrance of a cycle.
Floyd's algorithm: phase 1, slow moves one hop and fast two until they meet inside the cycle. Phase 2, restart one runner at the start; moving both one hop at a time, they meet exactly at the entrance. The proof is one line of algebra; be ready to sketch it (distance to entrance equals distance from meeting point to entrance, modulo the cycle length).
def find_duplicate(nums: list[int]) -> int:
slow = fast = nums[0]
while True: # phase 1: meet inside the cycle
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0] # phase 2: walk to the entrance
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowpublic static class FastSlow
{
public static int FindDuplicate(int[] nums)
{
int slow = nums[0], fast = nums[0];
do // phase 1: meet inside the cycle
{
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0]; // phase 2: walk to the entrance
while (slow != fast)
{
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}Complexity
O(n) time, O(1) extra space. Mention the alternatives and why the constraints exclude them: a hash set is O(n) space; sorting modifies the array; binary search on the count is O(n log n).
Pitfalls interviewers watch for
- Starting phase 2 with
slow = 0versusnums[0]inconsistently with phase 1; both runners must start from the same node. - On linked lists, not checking
fast and fast.nextbefore stepping twice. - Claiming the algorithm without being able to say why phase 2 meets at the entrance.
Variants worth knowing
- Linked list cycle and cycle start: identical two phases on
node.next. - Middle of a linked list: when fast reaches the end, slow is in the middle.
- Palindrome linked list: find the middle, reverse the second half, compare.
Test it like the interviewer will
find_duplicate([1, 3, 4, 2, 2])returns2find_duplicate([3, 1, 3, 4, 2])returns3find_duplicate([1, 1])returns1find_duplicate([2, 2, 2, 2, 2])returns2- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: find_duplicate([3, 1, 3, 4, 2])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the node where a linked list's cycle begins, or null.
- Determine whether a number is "happy" (repeated digit-square sums reach 1).
- Check whether a singly linked list is a palindrome in
O(1)extra space.
Check yourself
Why must a duplicate create a cycle?
Every index points somewhere inside the array, so the walk must revisit a node; the duplicate value is the node with two incoming edges, the cycle's entrance.
What changes between phase 1 and phase 2?
One runner restarts from the beginning and both move one step at a time.