Two pointers is the pattern for monotone search over a sequence — once you can argue that moving one pointer never invalidates the other, you’ve collapsed O(n²) to O(n).
Variants
- Opposite ends, converging. Sorted array, target sum, “trapping rain water,” “container with most water.” Move the pointer that limits the answer.
- Same direction, fast/slow. Cycle detection (Floyd), removing duplicates in-place, partition.
- Sliding window. Special case where both pointers move forward and the gap encodes the answer — see Sliding window.
- Lexicographic search prefix narrowing. Sort, maintain
l/r, advance whichever side fails the prefix check (“search suggestions” type).
When it works
The invariant has to be monotone: moving one pointer in one direction can only make the candidate worse or better, not both. If you can’t articulate the invariant, you don’t have a two-pointer problem — you have a search problem.
For the “container” / “rain water” family, the invariant is: the shorter side always limits the area, so moving the taller side can only shrink things — move the shorter. Write the invariant down before coding.
Sort first, then collapse
Many “find triple summing to X” problems become two-pointer once you sort: fix one element, two-pointer the rest. Cost: O(n log n) to sort, O(n²) overall. Beats O(n³) brute force; loses to hashing for “exact target” but wins on “range” or “closest” because hashing can’t answer those.
The bug
Off-by-one when both pointers can advance. Define your loop condition (l < r vs l <= r) by what the terminal state should mean — pick one and stick with it.