What loop invariant makes the converging-pointer pair-sum search on a sorted array exact — why can an inward move never skip the answer?

## The claim to prove The converging-pointer pair-sum scan reports a pair summing to a target `T` in a sorted array, or reports absence, in one O(n) pass. Skeptics call it a heuristic — "how do you know an inward move never steps over the answer?" The reply is a standard **loop-invariant proof**, and being able to deliver it out loud is precisely what this question tests. ## The invariant *If any pair of indices `i < j` satisfies `a[i] + a[j] == T`, then at least one such pair satisfies `lo <= i < j <= hi`.* In words: **the window never loses the last remaining answer.** ## Proving it in three steps 1. **Initialization.** Before the first iteration, `lo = 0` and `hi = n - 1`: the window is the whole array, so every answer (if any) trivially lies inside. The invariant holds. 2. **Maintenance — the exchange-of-possibilities argument.** Suppose the invariant holds at the top of an iteration. - If `s = a[lo] + a[hi] < T`: sortedness makes `a[hi]` the maximum of the window, so for every `j` in the window, `a[lo] + a[j] <= a[lo] + a[hi] < T`. Every pair that includes index `lo` is thereby proven not to sum to `T`. Advancing `lo` removes exactly those pairs from consideration — all of them impossible — so any answer that was inside the window is still inside. - The `s > T` case mirrors it: `a[lo]` is the window minimum, so every pair including `hi` overshoots, and retreating `hi` discards only impossible pairs. - The invariant survives both moves. Note the discipline: **exactly one pointer moves per non-matching comparison.** Moving both on a miss would discard pairs no argument condemned. 3. **Termination.** Each iteration either returns or shrinks `hi - lo` by one, so the loop ends within `n - 1` iterations. If it ends with `lo == hi`, the window contains no pair at all — and the invariant says any existing answer would still be inside it. An empty window plus the invariant is a ***proof of absence***, not a shrug. That is the difference between an exact algorithm and a heuristic. ## Why "the sum approaches the target" is the wrong invariant A tempting but false claim is that `s` moves monotonically toward `T`. It need not: advancing `lo` across a large value gap can overshoot wildly, and the sum may oscillate around the target for many steps. Correctness does not rest on the sum's trajectory; it rests on what each comparison *proves* about the discarded element. Interviewers use this distinction to separate candidates who memorized the motion from candidates who understand the proof. ## One comparison kills up to n pairs, not one The scan makes at most `n - 1` comparisons yet adjudicates all Θ(n²) pairs. The resolution: each comparison eliminates an entire **pencil of pairs** — everything through the discarded index — in one stroke. Candidates who believe one test eliminates only the single tested pair conclude that a quadratic check is unavoidable; the exchange argument is exactly what frees you from it. ## Worked flavor In a refund-matching setting — transaction amounts sorted ascending, target chargeback `T` — the argument narrates naturally at a whiteboard: "this smallest amount, even paired with the biggest amount left, cannot reach the chargeback; no other partner is bigger, so this amount is dead — strike it." Each strike is justified the moment it happens, which is why the final "no match" is trustworthy. ## Generalization The proof template — a **window invariant** plus a **monotonicity fact** that condemns one end — extends beyond exact sums: - closest-sum tracking (record the best seen; the discarded element provably cannot beat it with any remaining partner); - mirror-constraint verification from both ends of an ordered roster; - any pairwise predicate monotone in each argument. Recognizing the template is worth more than the specific loop.