Exploit monotonic pair sums
Updated
On a sorted array, fixing one end and sliding the other makes the pair sum monotonic. One pointer move therefore discards a whole slice of pairs without checking them.
What to focus on
If a[L]+a[R] > target, a[R] cannot pair with any remaining left ≥ L, so R -= 1 discards all of them. If the sum is too small, L += 1 discards this L against every remaining right ≤ R.
Worked examples
discard 9
a = [1, 4, 9], target=8, L=0, R=2- L=0, R=2: 1+9=10 > 8
- 4+9=13 is worse
- R -= 1 discards (1,9) and (4,9)
Result: L=0, R=1 · 9 gone
discard 1
a = [1, 4, 9], target=13, L=0, R=2- L=0, R=2: 1+9=10 < 13
- 1+4=5 is worse
- L += 1 discards (1,4) and (1,9)
Result: L=1, R=2 · 1 gone
dups still monotone
a = [1, 4, 4, 9], target=8, L=0, R=3- 1+9=10 > 8
- every larger left with 9 is larger still
- R -= 1
Result: L=0, R=2
Try it
Write discardSlice(a, L, R, target). a is a sorted array of integers. L is the left index. R is the right index. target is the pair sum. Move one pointer. Print every pair the move skips. Return nothing. On [1, 4, 9] targets 8 and 13 from (0, 2), and on [1, 4, 4, 9] target 8.
a is sorted non-decreasing, length ≥ 2. L < R.