Lesson 6.1 · Two Pointers
Why Two Pointers Work
In a sorted array, one comparison of the two ends rules out every pair involving one of them. That elimination is why O(n²) pairs shrink to O(n) steps.
14 min
Think of it like this
Two friends want to split a restaurant bill exactly using one note each from a sorted wallet of notes. One holds the smallest note, the other the largest. Too much in total? The largest note is too big to pair with anything (even the smallest note was too much), so put it away. Too little? The smallest note is too small for anything, so put that away. Each check removes one note for good.
1.The elimination argument
Take a sorted array and a target sum. Let L point to the smallest remaining value and R to the largest. If a[L] + a[R] > target, then a[R] plus anything at or after L is also too big, because those values are at least a[L]. So a[R] can't be in any valid pair: drop it with R--.
If the sum is too small, a[L] plus anything at or before R is also too small, so drop a[L] with L++. Each step removes one element from consideration, so there are at most n steps.
a = [1, 3, 4, 6, 8, 11], target = 13Step 1/51 + 11 = 12 < 13: too small. 1 is too small even with the largest value, so drop it.
Quick check
Why must the array be sorted for this to work?
2.The loop condition
Use while (L < R): when they meet there's only one element left, and a pair needs two different elements. Problems about single elements in the middle (like palindrome checks) also stop there, because the middle character matches itself.
Remember
- Sorted input + pair condition → opposite-end pointers.
- Each comparison discards one element for good, so the scan is O(n).
- Loop while
L < R.
Common mistakes
- Using two pointers on unsorted data without sorting first.
- Moving both pointers when only one should move.