Why Two Pointers Works

Finding a pair with target sum in sorted array:

Brute force: All pairs. $O(n^2)$.

Two pointers: left=0, right=n-1.

• Sum $<$ target: move left right (need larger)
• Sum $>$ target: move right left (need smaller)
• Equal: found

Why it works: Moving left discards pairs with current left and smaller rights. Sorted property guarantees those sums are smaller. No need to check.

Each pointer moves at most $n$ times. $O(n)$.