Two Pointers: Closing In From Both Ends of a Sorted Array

The two pointers pattern walks one array with two indices, called pointers, and moves one of them at every step, so a question about pairs is answered in a single pass. The cues are properties of the problem: the input is sorted, or can be sorted without losing the answer, and the question asks about a pair or a triple of values; or an array must be rewritten in place without a second array.

The first form starts one pointer at each end of a sorted array and moves them towards each other. To find two values that add up to a target, compare the sum at the pointers with it. A sum that is too small cannot be fixed by moving the right pointer, because every value to its left is smaller still, so the left pointer moves right. A sum that is too large moves the right pointer left for the same reason. Each move rules out every pair the discarded value could have made, which keeps one invariant: no pair outside the two pointers can be the answer.

The values 2 5 7 8 12 15 hold a pair that adds up to 19.

Each step moves one pointer one place and the pointers never cross, so the pass takes at most n − 1 steps for n values: O(n) time and O(1) extra space, against O(n²) for checking every pair.

Spending a gift voucher on two items from a menu ordered by price works the same way. With too little spent, swap the cheap item for the next dearer one; with too much, swap the dear item for the next cheaper one. The likeness breaks at going back: a diner can return to an item already turned down, and a pointer never moves back, which is safe only because the sorted order proved that item useless.

The second form moves both pointers in the same direction. A read pointer visits every value, and a write pointer marks the next free slot for a value worth keeping, so an array can be filtered in place. When the input is not sorted and sorting would lose the indices, a hash map of complements finds the pair instead, as the Hash Map Patterns topic shows.