Data Structures19 sections · 729 units
Open in Course

Two Sum Sorted - Why It Works

Proof sketch

Why does two pointers find the answer? Suppose the answer is at indices ii and jj with i<ji < j. Initially, leftileft \leq i and rightjright \geq j.

Every time you move leftleft right, it's because the current sum is too small. Since the array is sorted, the correct leftleft index must be further right.

So you never skip past ii. Similarly, you never skip past jj when moving rightright left. Eventually, left=ileft = i and right=jright = j.