Prove no valid pair was skipped
Updated
Each move discards only pairs already proven impossible. Any surviving pair (i, j) with i < j and a[i]+a[j]==t still has i ≥ L and j ≤ R after the move. The remaining interval is a complete candidate set.
What to focus on
Count discarded pairs vs remaining. The hit, if it exists, is still inside. Crossing with no hit means zero valid pairs.
Worked examples
still inside
a = [1, 4, 9], t=13, after L++ from (0,2)- discarded (0,2) sum 10≠13
- remaining (1,2) sum 13
- the hit is still in range
Result: no skip of 4+9
all remaining checked
a = [1, 4, 9], t=8, L=0 R=2 then R-- then L++- discarded 1+9 and 1+4
- last (1,1) is not a pair
- never discarded 4+9 without testing it — 4+9=13≠8 anyway
Result: no valid pair existed
merge no skip
a = [1, 4, 9], b = [4, 7, 9], emit smaller heads- 1 emitted before any 4
- every input index is emitted once
Result: merge did not skip 7
Try it
Write remainingPairs(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 discarded pairs and remaining pairs after the first move. Return nothing. For a = [1, 4, 9] t=13, 4+9 remains after L++. For t=8, every pair was either tested or proven impossible.
a is sorted non-decreasing, length ≥ 2. Merge uses two nonempty sorted sequences.