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

Find a canonical value pair using two distinct input positions. The returned values are ordered, and when several pairs work the smallest first value wins.

All-pairs enumeration is straightforward but quadratic. Sorting a copy makes it possible to reject an entire group of pairs after one comparison. Sorting the original violates input ownership and may erase position information needed by other APIs.

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.

Sorting a copy makes the sum monotone in either pointer. If the sum is too small, moving the right pointer cannot help; advance the left pointer. The first successful left value is the smallest feasible first component. Use distinct positions even for equal values. Final O(n log n) time, O(n) copied storage.

A copied primitive array isolates sorting from the caller while retaining duplicates as distinct positions:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long[] original = {5, 1, 5};
        long[] ordered = original.clone();
        Arrays.sort(ordered);
        assert Arrays.equals(original, new long[]{5, 1, 5});
        assert ordered[1] == 5 && ordered[2] == 5;
        assert ordered.length == 3;
    }
}

Two equal values can still form a pair because they occupy different positions. A set-based simplification would lose that multiplicity. The pointer loop must use left < right so one position cannot be paired with itself.

Keeping values separate from positions

Sort-and-discard arguments are useful for sum constraints, deduplication, and joining ordered value streams. The important step is proving which pointer move cannot discard a better valid answer.

Return the lexicographically smallest ascending value Pair(a,b) with a+b == target using distinct positions, or null. Negative values and duplicates are valid. [5] cannot pair with itself; [5,5] can.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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