All Patterns
Pattern 3
Fast & Slow Pointers
Floyd's cycle detection: one pointer moves twice as fast. They'll meet if there's a cycle, or fast will hit null if there isn't.
Time
O(n)
Space
O(1)
Recognize it when
- Detect cycle in linked list or array
- Find middle of linked list in one pass
- Detect if number is happy (infinite loop detection)
- Find start of cycle
Progress0/4
0 solved0 attempted
Questions — ordered by difficulty
#202Easy
Happy Number
A happy number eventually reaches 1 under the process of replacing it with the sum of squares of its digits. Detect if a number will cycle forever.
mathhash-setfast-slow-pointers
#141Easy
Linked List Cycle
Detect if a linked list has a cycle, using O(1) memory.
linked-listfast-slow-pointers
#287Medium
Find the Duplicate Number
Find the duplicate in an array of n+1 integers where each integer is in [1, n]. Must not modify the array and use O(1) space.
arrayfast-slow-pointersbinary-search
#876Easy
Middle of the Linked List
Find the middle node of a linked list in one pass.
linked-listfast-slow-pointers