Prove the discarded side is useless
Updated
Sorted a, inward L, R. If a[L]+a[R] > t, every pair (L', R) with L' ≥ L is even larger, so drop R. If a[L]+a[R] < t, every pair (L, R') with R' ≤ R is even smaller, so drop L.
What to focus on
The discarded index cannot form a valid pair with anyone still inside [L, R]. That is why moving one pointer is safe.
Worked examples
drop R
a = [1, 4, 9], t=8, L=0 R=2- 1+9=10>8
- 4+9=13>8 also
- no pair using 9 works
Result: R-- is safe, discard index 2
drop L
a = [1, 4, 9], t=12, L=0 R=2- 1+9=10<12
- 1+4=5<12 also
- no pair using 1 works
Result: L++ is safe, discard index 0
compact drop
a = [0, 1, 0, 9], keep nonzero, i=0- 0 is dropped
- later writes may overwrite index 0
- no kept value needed that 0
Result: skip is safe, discard a[0]
Try it
Write discardedPairs(a, t). a is a sorted array of integers. t is the pair-sum target. L is the left index. R is the right index. Print every pair that uses the discarded index and its sum. Return nothing. For a = [1, 4, 9] t=8, list every pair that uses index 2. For t=12, list every pair that uses index 0.
a is sorted non-decreasing, length ≥ 2, for the pair-sum cases. Compact uses a nonempty array and a keep rule that returns true or false.