Two Pointers

AI Generated

Two indices walk the data instead of two nested loops, which turns $O(n^2)$ into $O(n)$.

Two shapes cover most of it:

• Converging — l at the start, r at the end. Compare, then move whichever pointer could still improve the answer (container with most water, two sum on a sorted array).
• Same direction — a slow pointer writes the result while a fast pointer scans ahead (move zeroes, union of two sorted arrays).

Sorting first is usually what makes it legal: it's what guarantees "moving left increases, moving right decreases", so discarding a pointer's side can't discard the answer. Fixing one element and running two pointers on the rest is how 3Sum and 4Sum each shed a factor of n.