On this page
Description
Cyclic sequence detection finds a loop in a sequence where each value decides the next one. That can be a linked list's next pointers, or an array read as "go to index nums[i]". Floyd's tortoise and hare does it with two pointers moving at different speeds and O(1) extra memory. They must meet inside the loop, and a second walk finds where the loop starts. That's how Find the Duplicate Number and Linked List Cycle II are solved without a hash set.
We'll go from simple to more technical:
- The pattern: phase 1 finds a meeting point, phase 2 finds the entrance.
- Where state-to-next-state loops show up in production.
- The mistakes: stopping at phase 1, and reaching for a set by reflex.
- When the O(1) space is worth the less obvious code.
The approach
The obvious way to find a repeat is to remember every value you've visited in a hash set. That's O(n) time, but also O(n) extra memory. Floyd's method uses two pointers instead. The slow one moves one step at a time, and the fast one two steps. Once both are inside the loop, the fast one gains one step per move, so it must catch the slow one.
Take nums = [2, 5, 1, 4, 3, 4] and read each value as the next index to visit. Starting at index 0, the walk goes 0, 2, 1, 5, then enters a loop between 4 and 3:
Index 4 is where the loop starts. Two indexes point to it, 5 and 3, so 4 is the value that appears twice. The two phases find it:
| Phase | slow | fast | Note |
|---|---|---|---|
| 1 | 2 | 2 | both start at nums[0] |
| 1 | 1 | 5 | |
| 1 | 5 | 3 | |
| 1 | 4 | 3 | |
| 1 | 3 | 3 | they meet inside the loop |
| 2 | 2 | 3 | slow restarts at nums[0]; now both move one step |
| 2 | 1 | 4 | |
| 2 | 5 | 3 | |
| 2 | 4 | 4 | they meet at the entrance: the duplicate is 4 |
Java
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast); // phase 1: they meet somewhere inside the cycle
slow = nums[0];
while (slow != fast) { // phase 2: distance from start to cycle entrance
slow = nums[slow]; // equals distance from meeting point to cycle entrance
fast = nums[fast];
}
return slow; // the cycle's entrance
Python
slow = fast = nums[0]
while True: # phase 1: they meet somewhere inside the cycle
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast: # phase 2: distance from start to cycle entrance
slow = nums[slow] # equals distance from meeting point to cycle entrance
fast = nums[fast]
# slow is the cycle's entrance
This is the same algorithm as cycle detection in a linked list: nums[i] plays the role of node.next. Why is the entrance the duplicate? Any walk over a finite set of indexes must loop eventually. No value is 0, so nothing points back to index 0, and the walk starts on a tail outside the loop. The node where the tail joins the loop is pointed to from the tail and from inside the loop. So its index appears twice as a value.
Where you'll see it
Any system that moves from one state to the next by a fixed rule can loop. An ID-remapping table that maps back onto itself is one example. With a limited number of states, a loop is guaranteed sooner or later, and this walk finds it without storing every state you've visited.
Which tool for which job?
| You need | Use |
|---|---|
| Does the sequence loop? (memory is fine) | a hash set of visited states |
| Does it loop? in O(1) space | Floyd: slow and fast pointers |
| Where the loop starts | Floyd phase 2: one pointer from the start, one from the meeting point |
| The loop's length | from the meeting point, walk until you're back |
| Fewer calls to an expensive next function | Brent's algorithm |
| A duplicate in n + 1 values from 1..n, read-only | treat values as next pointers; the entrance is the duplicate |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Returning the phase-1 meeting point | a point in the loop, not its entrance | run phase 2 |
| Moving both pointers two steps in phase 2 | they may never meet at the entrance | one step each in phase 2 |
Not checking fast and fast.next for null | a crash on lists without a cycle | check both before advancing |
Starting fast at a different place than phase 2 assumes | phase 2 lands off the entrance | start both at the head (or both one step in) |
| Sorting or marking the array to find the duplicate | the input is changed | Floyd leaves it untouched |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A solution finds the repeated value with a hash set of visited values. Is it wrong?
Show answer
No. It finds the duplicate correctly, using O(n) extra memory. Floyd's method finds the same answer in O(1) memory, and that saving is the whole reason to use it.
2. Is the point where the pointers meet in phase 1 the loop's entrance?
Show answer
Not necessarily. It's somewhere inside the loop. In the example they met at 3, but the entrance is 4. Phase 2 finds the entrance: restart one pointer and move both one step at a time.
3. Why must n + 1 values, each between 1 and n, contain a duplicate?
Show answer
There are n + 1 values but only n possible ones, so at least one value must repeat. This is the pigeonhole principle. You don't need to scan to know a duplicate exists, only to find which one it is.
Key takeaways
- An array whose values are valid indexes can be walked like a linked list. Floyd's method finds its loop in O(1) extra memory.
- Phase 1 only finds a meeting point somewhere in the loop. Phase 2 finds the entrance.
- With n + 1 values in a range of n, a duplicate must exist.
- The same two phases work for a linked list's
nextpointers and for array values read as indexes.