Two Pointers
Two indices moving under a rule, covering in one pass what a nested loop needs n squared for.
Two Pointers: Two sum on a sorted array
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
In this order
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.