Sign in to watch this lesson
Algorithms - Arrays · 4:48
Two Pointers
Two indices that only ever move one way turn quadratic pair searches into linear scans. We find a pair summing to 15 in a sorted array by watching each comparison wipe out a whole row or column of the pair grid, prove why that is safe and linear, and race it against checking every pair. Then the same-direction version, where the left pointer chases the right one, plus merging, three-sum and the classic traps.
You will learn
- Solve pair-sum problems on sorted arrays with opposite-end pointers and explain which pairs each move discards
- Prove a two-pointer scan is linear by bounding how far each pointer can move
- Apply the same-direction pattern (for each r, the smallest valid l) when validity is monotone in l
- Extend two pointers to merging and three-sum while avoiding the index, duplicate and sorting traps