Two pointers: from n² pairs to n steps

Given a list of prices and a gift card, is there a pair of items that spends it exactly? The obvious answer tries every pair: with $n$ items that is $\tfrac{n(n-1)}{2}$ pairs, about 5,000 for 100 items and 50 million for 10,000.

If the prices are sorted, you can do it in at most $n - 1$ checks. The trick is to stop thinking about pairs and start thinking about ruling values out.

L and R

Two indices: L starts at the smallest value, R at the largest. They only ever move inward.

sum

A[L] + A[R], compared with the target at every step.

ruled out

A value that cannot be part of any answer, given what we know. Each step rules out exactly one.

still possible

The positions between L and R: any answer must lie entirely inside them.

The reasoning is the whole algorithm:

• If A[L] + A[R] is too small, then A[L] plus anything still possible is too small, because A[R] is the largest thing left. So A[L] can't be in any answer: move L right.
• If the sum is too big, A[R] plus anything still possible is too big, because A[L] is the smallest thing left. So A[R] is out: move R left.

Pick "Pair at the ends" and count the checks: one. Pick "No pair" and watch L and R meet. Then make up your own sorted list and target in the input box.

• Two pointers use order to rule out one value per step, turning O(n²) pair checks into O(n).
• The invariant: any answer lies inside [L, R].
• The same shape solves 3Sum (fix one value, two-pointer the rest), container with most water, and removing duplicates in place.
• Next: the sliding window keeps two pointers moving in the same direction instead of toward each other.