Why does the converging two-pointer technique for finding a pair with a target sum require sorted input?
answer
- what does one comparison prove?
- the high end is the largest remaining
- too small — only one move can help
- each step safely retires one element
- unsorted ends prove nothing about partners
basics
~20 sSorted order gives each comparison a direction: a sum below the target is only fixable by advancing the low end, one above only by retreating the high end. With unsorted input no move is provably safe, so the scan could skip the answer.
solid answer
~50 sPlace one pointer at each end and compare `a[lo] + a[hi]` to the target. On a match you are done; if the sum is too small, the only way to raise it is `lo = lo + 1`, because `a[hi]` is already the largest value still in play; if too big, only `hi = hi - 1` can lower it. That decision rule is exactly what sortedness buys: each comparison proves one end's element can never be part of an answer inside the window, so discarding it is safe. On unsorted data the comparison tells you nothing about where a better partner sits, and an inward move could walk past the answer — so sorting is a correctness precondition, not a speed-up. The scan does at most n-1 moves: O(n), plus O(n log n) first if you must sort.
go deeper
Be ready to state the setup — one pointer per end of sorted data — the three-way decision on the sum, and the O(n) cost of the pass. Say clearly that sortedness is what makes each move safe.
An interviewer expects the direction argument: a too-small sum means the low element can pair with nothing remaining, because the high end is the largest candidate left. Explain it, don't just assert it.
Be ready to place the pattern among alternatives: sorting cost versus auxiliary-space cost, when the input is already sorted, and how the argument generalizes to any pairwise predicate that is monotone in each element.
Own the framing: this pattern is a worked example of exploiting input structure to delete a loop. Use it to probe whether engineers reason about why each move is safe rather than reciting the recipe.
**The scenario.** A ledger of transaction amounts is stored in ascending order, and a chargeback of exactly `T` must be explained by two entries. The brute-force answer checks every pair: two nested loops, O(n²) comparisons. The converging two-pointer technique replaces that with a single linear pass — but only because the ledger is sorted. **The mechanism.** Place `lo` at the first (smallest) entry and `hi` at the last (largest). Each iteration computes `s = a[lo] + a[hi]` and takes one of three actions: - `s == T`: a qualifying pair is found — done. - `s < T`: advance `lo` by one. - `s > T`: retreat `hi` by one. Loop while `lo < hi`. Each step moves exactly one pointer inward one position, so after at most `n - 1` moves the pointers meet and the scan ends: O(n) time, O(1) extra space. **Why sortedness is a correctness requirement, not a speed-up.** Consider the `s < T` case. Because the array is sorted, `a[hi]` is the largest element still inside the window `[lo, hi]`. If even `a[lo] + a[hi]` falls short of `T`, then `a[lo]` plus *any* element of the window falls short — the low element has been proven partnerless, and discarding it cannot lose an answer. The mirrored argument covers `s > T`: `a[lo]` is the smallest remaining, so if the sum is already too big, `a[hi]` can pair with nothing in the window. Every inward move is backed by this small proof. On unsorted data the proof evaporates. `a[hi]` is just some value, not the maximum of the window, so `a[lo] + a[hi] < T` says nothing about `a[lo]`'s other potential partners. A move made anyway might discard the exact element the answer needed — and the scan would then report "no pair" incorrectly. This is the core wrong belief to avoid: sorting is not an optimization that makes two pointers faster; it is the precondition that makes the moves valid at all. **Another wrong belief: "it's a heuristic."** Some candidates accept the linear pass but hedge that a quadratic check is still needed "to be sure". It is not. Each move discards only pairs proven impossible, so when the pointers meet without a match, every pair has been either examined or eliminated by proof. The scan is exact, not approximate. (The full invariant-style argument deserves its own treatment, but the one-line version: the answer, if one exists, always remains inside the current window.) **Cost accounting.** | approach | time | extra space | precondition | |---|---|---|---| | brute-force all pairs | O(n²) | O(1) | none | | sort, then converge | O(n log n) | sort-dependent | may reorder the data | | converge on sorted input | O(n) | O(1) | already sorted | If the data arrives sorted the pattern is essentially free. If not, sorting dominates the cost, and whether it is worthwhile depends on whether reordering is allowed and how many queries will amortize the sort. **Where the pattern generalizes.** Nothing here depends on sums specifically. The technique applies whenever the input's order makes each end-comparison a *decision*: a predicate over the pair that is monotone in each element, so a failed test at one end condemns that end's element outright. Verifying a mirror constraint from both ends of an ordered roster, closest-pair-to-target variants, and bounded-difference checks all reuse the same skeleton — one comparison, one provably safe inward move. **What interviewers listen for.** Naming the three-way decision is table stakes. The differentiator is spontaneously producing the safety argument — "the high end is the largest remaining, so a too-small sum condemns the low element" — because that shows you can justify each move rather than pattern-match the recipe. Follow-ups usually probe exactly that: why one move per step, what breaks unsorted, and what the scan proves when it ends empty-handed.
- The input arrives unsorted — what does the two-pointer route cost end to end?Sorting first costs O(n log n), which then dominates the O(n) converging pass. Whether that is acceptable depends on whether you may reorder the data (or can afford a sorted copy) and how many queries will amortize the sort; when the data is already sorted, the pattern is essentially free.
- Does the technique need random access, the way binary search does?No. It only ever reads the two current ends and steps inward one position at a time, so bidirectional sequential access suffices — a doubly-linked sequence works. Binary search, by contrast, needs O(1) jumps to arbitrary midpoints to keep its O(log n) bound.
- Can both pointers ever need to move on the same comparison?Only on a match while enumerating all pairs: after recording, both must advance or the same pair repeats. On a non-matching comparison exactly one pointer moves — that one-move-per-step discipline is what gives the n-1-step bound and keeps every move individually justified.
Two clerks work a price-ordered shelf from opposite ends. If the cheapest plus the priciest item together cost too little, swapping the priciest for anything cheaper only lowers the total — the cheap item is hopeless and gets set aside.
saying these in an interview costs you the question
- Claims two pointers works on unsorted arrays with no preprocessing
- Treats sorting as a speed optimization rather than a correctness requirement
- Says the pass halves the search space like binary search, giving O(log n)
- Believes an O(n^2) all-pairs check is still needed afterwards to be sure