Converging Two Pointers, Distinct Pairs

core

Implement pairs_summing(a, target) where a is sorted in non-decreasing order and may contain duplicates. Return every distinct value pair (x, y) with x <= y and x + y == target that can be formed from two elements at different indices, each such pair exactly once, ordered by x ascending. A pair with x == y needs two separate elements holding that value.

Do it with two pointers converging from the ends: l at the front, r at the back, moving l up while the sum is too small and r down while it is too large. When the sum matches, record the pair and then advance both pointers; advancing only one leaves you on the same pair. Then skip past the duplicates you just consumed, guarding each skip with l < r so it cannot walk off the array, or the same value pair is emitted once per copy.

Example: pairs_summing({1, 1, 2, 2}, 3) returns {{1, 2}}, one pair, not two. The pointers meet 1 and 2 at the ends, record (1, 2), move inward onto another 1 and another 2, and the duplicate skip steps over both rather than recording the same value pair again.

Input format: each test in tests/*.in is laid out as:

Line 1: n target, the array length and the pair-sum to find.
Line 2: the n sorted values, space-separated.

Test 06.in reads:

2 0
0 0

This is two zeros with target = 0: the two elements together form the single value pair (0, 0).

Where you'll use it:

✦ Solution & editorial unlock with the pass.