Two Pointers
Walk two indices through a sequence — toward each other or in tandem — to turn many O(n²) scans into a single O(n) pass.
Key ideas
- —Use opposing pointers on sorted data to find pairs without nested loops.
- —Use fast/slow pointers to detect cycles or find midpoints in one pass.
- —The invariant you maintain between the pointers is what makes it correct.
When it applies
Reach for two pointers when the input is sorted (or can be), when you need pairs/triples that satisfy a condition, or when you are partitioning an array in place. The core move is advancing one pointer based on a comparison so you never re-examine elements you have already ruled out.
The invariant
On a sorted array with left and right ends, if the current pair sums too high you move the right pointer in; too low, the left pointer out. Because the array is sorted, every move provably discards only pairs that cannot be the answer — that is what keeps it linear and correct.
Practice this
Sources
- Two Pointers TechniqueGeeksforGeeks
- Floyd's Cycle Detection (fast/slow pointers)Wikipedia