Sorting and two pointers

An audit tool is checking whether two ledger adjustments explain a disputed total. Entries may be negative, and two equal amounts are allowed only if they come from different entries. When several pairs work, the report needs a reproducible choice.

Checking every pair is a useful reference. Sorting a copy gives the search a stronger property: a sum that is too small or too large can rule out a whole group of pairs at once.

Explaining a total with two entries

Sorted order lets each comparison eliminate candidates. If the smallest-plus-largest sum is too small, every pair using that smallest value is too small, so advance the left pointer. If too large, move the right pointer. These eliminations depend on order, not on positivity.

Discarding pairs by their sum

For sorted values [-2, 1, 4, 7, 10] and target 9, the outer pair sums to 8. No smaller partner can rescue -2, so move the left pointer. Now 1 + 10 is too large, and no larger left value can rescue 10, so move the right pointer. Each move has a reason; neither requires trying all partners for the discarded endpoint.

std::vector<Int> sorted{4,1,3,2};
std::sort(sorted.begin(),sorted.end()); // sort a copy, never the caller's vector

Keeping values separate from positions

The answer is a value pair, not a pair of original indices. Distinct positions still matter: one 5 cannot satisfy target 10, while two 5s can. Starting at the minimum left value ensures the first matching pair is lexicographically smallest. Sorting costs O(n log n); the subsequent inward scan is O(n). Copying costs O(n) storage but protects the original order. Avoid unsigned right-index underflow on an empty vector: use signed cursors or iterator pairs with an explicit nonempty guard.

The sorted-copy method takes O(n log n) sorting time, an O(n) inward scan, and O(n) copy space. The all-pairs reference has O(n²) candidates. For already sorted input, only the linear scan is needed; for original positions, retain their association with each value.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

Sorting a copy leaves the original transaction order available for the rest of the audit.