Running the Pair Search on an Unsorted Array

The opposite-ends pair search is correct only on sorted input; on an unsorted array it can report no pair when one exists. Every move in it rests on one claim: a sum that is too large means no value to the left of the right pointer can make a smaller pair with the left value, because those values are smaller. Without sorted order the claim is false, so a move can throw away the pair that was wanted.

The readings 7 2 9 4 1 hold a pair that adds up to 6: 2 and 4. The listing runs the same search on them as given and again after sorting, printing every move.

def opposite_ends(values: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            print(f"  {values[left]} + {values[right]} = {total}: found")
            return values[left], values[right]
        if total < target:
            print(f"  {values[left]} + {values[right]} = {total}, too small: left moves right")
            left += 1
        else:
            print(f"  {values[left]} + {values[right]} = {total}, too large: right moves left")
            right -= 1
    print("  pointers met: no pair")
    return None


readings = [7, 2, 9, 4, 1]
print("unsorted:", *readings)
print("result:", opposite_ends(readings, 6))
print("sorted:", *sorted(readings))
print("result:", opposite_ends(sorted(readings), 6))

unsorted: 7 2 9 4 1
  7 + 1 = 8, too large: right moves left
  7 + 4 = 11, too large: right moves left
  7 + 9 = 16, too large: right moves left
  7 + 2 = 9, too large: right moves left
  pointers met: no pair
result: None
sorted: 1 2 4 7 9
  1 + 9 = 10, too large: right moves left
  1 + 7 = 8, too large: right moves left
  1 + 4 = 5, too small: left moves right
  2 + 4 = 6: found
result: (2, 4)

On the unsorted readings the left pointer never leaves the 7, because every sum with 7 is too large, and the right pointer walks across the 4 and the 2 without ever pairing them with each other. On the sorted readings 1 2 4 7 9 the same moves are safe and find 2 + 4.

Sorting is not free. It costs O(n log n) and moves every value, so a problem that asks for the original indices loses them unless each value is sorted together with its index. When the indices matter, a hash map of complements finds the pair in one pass at O(n) time and O(n) extra space, as the Hash Map Patterns topic shows.

The same caution applies to hand traces. A widely shared pair-search trace once added 1 + 6 and wrote 8, and nobody noticed until it was run, which is why every trace in this topic comes from a run.