Two pointers
In a sorted array, start one pointer at each end. If the pair is too small, the left value can never help, so move left in. If too big, move right in. Each step rules out a whole row of pairs.
13468111315
Find two values that add up to 17. Press play or step forward to start.
1function pairWithSum(a, target) {2 let lo = 0, hi = a.length - 1;3 while (lo < hi) {4 const sum = a[lo] + a[hi];5 if (sum === target) return [lo, hi];6 if (sum < target) lo++;7 else hi--;8 }9 return null;10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the outermost pair already adds up |
| average | n | any target |
| worst | n | no pair exists: the pointers walk until they meet |
| space | 1 | just two indexes |
Where it breaks
- Unsorted input. "Too small, so move left in" only works if everything to the right is bigger. On unsorted data it skips valid pairs. Sorting first costs n log n, so a hash set is the faster choice for a one-off unsorted search.
- Checking every pair instead. The nested-loop version makes about n²/2 checks. Pick Missing 20 above: two pointers rule out all 28 pairs of 8 items in 7 steps.
- Using the same item twice. The loop runs while
lo < hi. Change it tolo <= hiand a target that is twice one value can match that value with itself.