Two pointers

One credit, two reversals

A partner bank sends a single credit of ₹10,000 with a note saying that it covers two of yesterday's payout reversals. You need to find which two. There were 40,000 reversals yesterday, and the list is already sorted by amount, from ₹150 up to ₹12,250.

The obvious method is to try every pair. Work out the cost: 40,000 × 39,999 / 2 is about 800 million pairs, and at 10 million additions a second that is 80 seconds in Python. A hash set from Unit 1 cuts that to 40,000 lookups, but it needs memory for 40,000 entries. Neither method makes use of the fact that the list is sorted.

Put one finger on the smallest amount and one on the largest. ₹150 + ₹12,250 = ₹12,400, which is more than ₹10,000.

Pause and predict ₹150 is the smallest amount on the list, and ₹150 + ₹12,250 = ₹12,400 is already more than ₹10,000. What does that tell you about ₹12,250?

Throw away what cannot win

A sorted array of n values has n(n - 1)/2 pairs. Two pointers finds a pair with a given sum after adding no more than n - 1 of them, and it never misses the pair. It cannot be checking each pair, so it must be ruling pairs out without adding them.

Take [1, 3, 4, 6, 8, 11] and the target 10. Put the pointer l on the smallest value and the pointer r on the largest. 1 + 11 = 12, which is bigger than 10.

Now think about 11 on its own. The smallest value it could pair with is 1, and even 1 + 11 is too big. Every other value is larger than 1, so every other sum with 11 is larger still. So 11 cannot be in any pair that adds up to 10, and you can drop it without ever adding 3 + 11 or 4 + 11.

Here is why that makes the algorithm correct. At the start, no position is outside [l, r], so the invariant holds. Each move keeps it true. If the sum is too small, nums[r] is the largest value still in range, so nums[l] plus any remaining value is at most this sum, which is already too small. Every pair that uses l is wrong, so l can move right. If the sum is too big, the same argument works the other way round: nums[l] is the smallest value left, so every pair that uses r is too big, and r can move left. So the pair you are looking for, if there is one, is never dropped. The range shrinks by one position per step until the pointers land on the pair or meet.

Picture every pair as a cell in a table, with one value as the row and the other as the column. Each pointer move crosses out a whole row or a whole column:

On these six values there are fifteen pairs. Two pointers uses four additions to rule out fourteen of them, and the fifth addition finds the answer.

The same argument, a different measure

Container With Most Water gives you a row of vertical walls of different heights and asks for the two walls that hold the most water between them. The water a pair holds is the distance between them times the height of the shorter wall. Start with the two outermost walls, which make the widest container.

Pause and predict You have measured the container between walls l and r, and the left wall is no taller than the right one: h[l] ≤ h[r]. Which wall can you drop for good?

The second family: same direction

Move Zeroes asks you to move every non-zero value to the front of the array, keeping their order. A reader pointer r visits every value, and a writer pointer w marks where the next kept value goes. In this family each candidate is a single value rather than a pair, and when the reader passes a zero, that zero is left behind for good.

Its invariant is: nums[0..w) holds exactly the kept values from nums[0..r), in their original order. Writing in place is safe because w moves only when r does, so w never gets ahead of r and a write never lands on a value the reader has not seen yet.

How to recognise it

Each of these signals comes with a condition. The opposite-ends version needs an order that tells you which side to drop, which usually means the array is sorted. The same-direction version only needs the writer to stay at or behind the reader.

Pause and predict These four problems look alike. Which one should you solve with two pointers?

Three that only look like it

• If the data is unsorted and the answer is a pair of positions, there is no order that tells you which value to drop. That is hashing.
• If the answer is a contiguous range that must meet a condition (the longest, the shortest, at most k of something), there are two indices again, but they mark the two ends of a window that must keep meeting the condition. That is sliding window.
• If the data is sorted and you want one value or the point where a condition starts to hold, you can halve the range at each step instead of shrinking it by one. That is binary search.

Where it bites

Pause and predict A sorted pair-sum loop runs on [2, 3, 5] with target 6, but its condition is while l <= r instead of while l < r. What does it return?

• Moving a pointer without a reason. In Container, moving the taller wall, or moving both walls, can drop the best container. Before you write the move, say why the value you drop cannot be in the answer.
• Writing l <= r for a pair. When the pointers meet, they point at one position, not two. Pair problems loop while l < r. (Rain Water and Sort Colors handle single cells, so there <= is correct.)
• Repeated triplets in 3Sum. Skip a fixed value when it equals the value before it (compare with i - 1, not i + 1), and after finding a triplet, move l past every copy of its value.
• In Sort Colors, moving mid forward after swapping a 2 to the back. The value that was swapped in from the back has not been looked at yet, so mid must stay where it is.
• Using opposite-end pointers on unsorted data. Without an order, a sum that is too small tells you nothing about the other values nums[l] could pair with.