Two Pointers
01 / The shared mechanism
Two indices moving over the same sequence to maintain an invariant — the move rule changes per sub-pattern, but the mechanism is shared.
02 / The one-sentence essence
Two pointers advancing at different rates over the same sequence — the asymmetry lets you compress in place, locate a midpoint, or detect a cycle without extra memory.
Problemremove duplicates from a sorted array in-placeInput[1, 1, 2, 2, 3, 3]
10
11
22
23
34
35
Sorted input. The first element is always kept — slow at 0; fast will scan from 1.
step
0 / 8
slow · fast
0 · —
action
init
unique so far
1
0 / 8
03 / The pattern signature
# in-place compaction variantslow ← 0for fast in 1..n−1:if arr[fast] ≠ arr[slow]:slow++arr[slow] ← arr[fast]return slow + 1# cycle-detection variant: fast moves 2x, slow moves 1x — they meet iff a cycle exists
04 / When to recognize this pattern
"in place"
You must edit the input without allocating a second array. Slow tracks where the next kept element belongs.
"cycle"
Detect or locate a cycle in a linked list or pointer chain. Fast moves twice as fast as slow — they meet iff a cycle exists.
"middle"
Find the midpoint of a list in one pass: when fast hits the end, slow is at the middle.
"compact / partition"
Keep elements satisfying some predicate at the front, discard the rest. Same mechanism as remove-duplicates with a different keep-condition.
05 / Common pitfalls
i.
Initializing both pointers at the same position.
For compaction,
slow starts at 0 and fast at 1. For cycle detection, both start at the head — but fast advances before the first comparison. Pick the convention per problem.ii.
Advancing slow at the wrong moment.
Update
slow before writing, not after — otherwise you overwrite the last kept value. The off-by-one here is the difference between a correct result and a shifted one.iii.
Confusing this with sliding window.
Sliding window sizes a contiguous chunk. Fast/slow uses asymmetric speeds — the gap between the two pointers is the answer (or a signal), not a window over data.
06 / Go practice — on LeetCode
Four problems, ordered by difficulty. The first two are array compaction; the second two are the linked-list classics.
— / When to use which
converging
Use when the array is sorted and the answer is a pair.
two-sum · palindrome · container
fast / slow
Use for in-place modification or cycle detection.
remove-dupes · linked-list cycles
sliding window
Use when the condition is about a contiguous chunk.
longest/shortest · at-most-k