Two Pointers
Two indices moving under a rule, covering in one pass what a nested loop needs n squared for.
Two pointers is a way of not trying every pair. You hold two indices into the same sequence and one rule that decides which of them moves next. Because each pointer only ever moves forward and never back, the pair between them sweeps the whole array in n steps rather than the n squared a nested loop would spend.
There are two arrangements. Pointers starting at opposite ends walk inward, and the comparison at each step says which side to give up. Looking for a pair that sums to a target in a sorted array, a sum that is too small can only be raised by moving the left pointer up, so every pair it skipped was provably too small as well. Pointers moving in the same direction use a reader that scans ahead and a writer that lags behind, which compacts the array in place with no second array.
The rule is only sound if the structure justifies it. Opposite ends needs sorted input, or some other property that makes one side safe to discard; without it you are throwing away candidates you never examined. The fast and slow variant is the same idea at two speeds: on a linked list, a pointer taking two steps reaches the end as the other reaches the middle, and inside a cycle it is bound to lap the slow one.
After this you can
- Say why moving the pointer on the smaller side cannot skip past the answer
- Compact an array in place with a reader and a writer, using O(1) extra memory
- Replace a nested pair scan with one linear pass over sorted input
- Extend the pair technique to triples by fixing one element and converging on the rest
- Use a fast and a slow pointer to find a middle or a cycle without measuring the length first
1 + 15 = 16, too big. Only a smaller right value can help, so right moves down.
In this order
- Two PointersTwo indices moving under a rule do in one pass what a nested loop needs n squared for.
- Opposite Direction PointersStart at both ends and move inward. The comparison decides which one moves.
- Two Sum (sorted)Too small, move left up. Too big, move right down. The sorted order makes that safe.
- Container With Most WaterMove the pointer at the shorter line inward; the taller one can never improve the area alone.
- Same Direction PointersA reader scans ahead while a writer lags, compacting the array in place.
- Remove Duplicates from Sorted ArrayThe writer only copies a value that differs from the last one it kept.
- Three SumFix one element, run two-sum on the rest; skip duplicates.
- Fast and Slow PointersOne pointer moves twice as fast as the other. Finds middles and cycles in one pass.
Where people go wrong
Opposite pointers on unsorted data
The move rule is an argument about which candidates can still win, and the argument rests on order. Run it on unsorted values and moving a pointer discards pairs that were never compared, so a miss proves nothing.
Repeated triples in three sum
Skipping past an anchor value's duplicates is not an optimisation, it is what stops the same triple being reported once per copy. The same skip is needed on both inner pointers after a hit, not just on the anchor.
Letting the writer overtake the reader
Compaction is safe only because the write index is always at or behind the read index, so every slot overwritten has already been read. Swap the roles, or advance the writer on a value you have not examined, and you lose data.
Or a different category
Sliding Window
Both pointers move the same way and the answer depends on the contents between them rather than the two ends.
Hashing
The values are unsorted and one pass with a set of what you have seen costs less than sorting them.