Closing in from both ends

Checking every pair of items costs O(n²), and the Big-O lesson showed how fast that grows. When the data is sorted, or you only care about items next to each other, two moving markers do in one pass what nested loops need n² steps for.

You have a price list, already sorted from cheap to expensive, and a gift card worth an exact amount. You want two items whose prices add up to exactly that amount, so you spend the card to the last cent.

The first idea is to try every pair: item 1 with item 2, item 1 with item 3, and so on. For a short list that is fine. For a list of a million prices it is a million times a million pairs: the O(n²) trap from lesson 09.

The list is sorted, though, and the order lets you throw away whole parts of the list without checking them. That gives the answer in one pass.

Take the first test: the prices [1, 3, 4, 6, 8] and the target 10. Put one marker on the cheapest price, 1, and the other on the most expensive, 8. Together they make 9, which is too little.

Which side do you move? The 1 fell short even together with the 8, the largest price there is. With any cheaper price it would fall short by more. So the 1 is in no answer, and you can drop it: move the left marker to 3. Now 3 + 8 = 11, too much. By the same reasoning the other way round, the 8 is too big even with the smallest price left, so drop it: the right marker moves to 6. Then 3 + 6 = 9, too little again, so the left marker moves to 4. And 4 + 6 = 10. Found it.

Each move dropped one price together with every pair it could form, and nothing was checked twice. Four sums were enough instead of all ten pairs.

Put marker lo on the cheapest item and marker hi on the most expensive one. Add up the two prices they point at.

• The sum equals the target: the pair is found. Done.
• The sum is too small: the only way to make it bigger is to take a pricier item instead of the cheap one. Move lo one position to the right.
• The sum is too big: move hi one position to the left so the sum gets smaller.

Each step is safe because the list is sorted. Say the sum is too small. Then nums[lo] falls short of the target even together with the largest remaining price, nums[hi]. With every other, cheaper price it falls short by more. So nums[lo] is in no valid pair, and you can drop it. Stop when the markers meet.

Trace it on [1, 3, 4, 6, 8] with target 10. lo points at 1 and hi at 8: the sum is 9, too small, move lo. lo at 3, hi at 8: the sum is 11, too big, move hi. lo at 3, hi at 6: the sum is 9, too small, move lo. lo at 4, hi at 6: the sum is 10, found. The answer is positions 2 and 3.

Time is O(n): each marker only moves inward, so together they take at most n steps. Memory is O(1): two variables with indices, and nothing grows with the input. If the list has to be sorted first, add O(n log n) for the sort.

Compare it with the hash approach from lesson 18. It also finds a pair in O(n) time, but it spends O(n) memory on a set. On data that is already sorted, two pointers give the same speed and need no extra memory.

Payment matching: in a ledger sorted by amount, find the two original charges that together make up the amount of a refund. An order book (a list of orders sorted by price) matches a buy order with a sell order. Antifraud systems (fraud detection) and deduplication pipelines look through sorted records for a pair that differs by no more than an allowed amount. Wherever money or ordered records are matched, the task looks the same: sorted input and a search for a pair. Two pointers solve it.