Fast and Slow Pointers on Sequences
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Pointers do not have to be at two ends. Two pointers can start together and move at different speeds. This finds the middle of a chain in one pass and spots a loop without storing what you visited.
A slow and a fast pointer
Fast and slow pointers are two pointers that walk the same sequence at different speeds, usually one step and two steps. They find the middle in one pass and detect a loop without extra memory.
Some data is a chain: each item says where the next one is. You may not know its length. Move a slow pointer one step and a fast pointer two steps. When fast reaches the end, slow is in the middle.
values = ["A", "B", "C", "D", "E"]nxt = [1, 2, 3, 4, -1]slow = fast = 0while fast != -1 and nxt[fast] != -1: slow = nxt[slow] fast = nxt[nxt[fast]]print(values[slow])Example 1 · Middle of an even chain
values = ["A", "B", "C", "D", "E", "F"]nxt = [1, 2, 3, 4, 5, -1]slow = fast = 0while fast != -1 and nxt[fast] != -1: slow = nxt[slow] fast = nxt[nxt[fast]]print(values[slow])D
What this code does
- With six items there are two middles, C and D. This version stops on the second one.
- For a Python list,
values[len(values) // 2]is simpler. The pointers matter when only next links exist.
Here nxt[i] is the next item after item i, and -1 means the end. The loop checks fast and nxt[fast] so the two-step move never runs past the end.
Detect a loop
A chain can loop back, for example a retry list that sends a task to itself. If there is a loop, the fast pointer laps the slow one inside it and they meet. If the chain ends, they never meet.
def has_cycle(nxt): slow = fast = 0 while fast != -1 and nxt[fast] != -1: slow = nxt[slow] fast = nxt[nxt[fast]] if slow == fast: return True return False
print(has_cycle([1, 2, 3, -1]))print(has_cycle([1, 2, 3, 1]))Example 2 · Loop detection with a set
def has_cycle_set(nxt): seen = set() node = 0 while node != -1: if node in seen: return True seen.add(node) node = nxt[node] return False
print(has_cycle_set([1, 2, 3, 1]))print(has_cycle_set([1, 2, 3, -1]))True False
What this code does
- A set remembers visited items. It is easy to write, but it uses O(n) space.
- Fast and slow pointers give the same answer with O(1) space.
Example 3 · Watch the two pointers meet
nxt = [1, 2, 3, 4, 2]slow = fast = 0while True: slow = nxt[slow] fast = nxt[nxt[fast]] print("slow", slow, "fast", fast) if slow == fast: breakslow 1 fast 2 slow 2 fast 4 slow 3 fast 3
What this code does
- The chain goes 0, 1, 2, 3, 4, then back to 2, so the loop is 2, 3, 4.
- Fast catches slow inside the loop after three rounds.
Inside a loop, fast gains one step on slow each round, so they must meet. Time is O(n) and space is O(1), while a set of visited items would cost O(n) space.
Find the repeated number
A list of n + 1 numbers between 1 and n holds one repeated value. Treat each number as the index of the next item. Two items point to the repeated number, so the chain loops there.
def find_duplicate(nums): slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow
print(find_duplicate([3, 1, 3, 4, 2]))Example 4 · Two repeated-number lists
def find_duplicate(nums): slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow
print(find_duplicate([3, 1, 3, 4, 2]))print(find_duplicate([1, 3, 4, 2, 2]))3 2
What this code does
- In
[1, 3, 4, 2, 2]the indexes 3 and 4 both hold 2, so the chain enters its loop at 2. - The list is not changed and no extra set is built, so space is O(1).
The first loop finds a meeting point inside the loop. Restarting one pointer from the start and moving both one step at a time makes them meet at the entry of the loop, which is the repeated number.
Happy numbers
Replace a number by the sum of the squares of its digits and repeat. It either reaches 1 or falls into a loop. The sequence is a chain without a list, and fast and slow pointers work on it too.
def step(n): return sum(int(digit) ** 2 for digit in str(n))
def is_happy(n): slow, fast = n, step(n) while fast != 1 and slow != fast: slow = step(slow) fast = step(step(fast)) return fast == 1
print(is_happy(19))print(is_happy(2))Example 5 · Happy numbers up to 10
def step(n): return sum(int(digit) ** 2 for digit in str(n))
def is_happy(n): slow, fast = n, step(n) while fast != 1 and slow != fast: slow = step(slow) fast = step(step(fast)) return fast == 1
print([n for n in range(1, 11) if is_happy(n)])[1, 7, 10]
What this code does
- 1, 7 and 10 reach 1. The other numbers fall into the loop 4, 16, 37, 58, 89, 145, 42, 20.
- A set of seen numbers works too, but the pointer version uses O(1) space.
step gives the next item, so slow = step(slow) and fast = step(step(fast)). The pointers meet on 1 or inside a loop.
Next step
Check your understanding
11 quick questions