Pointers from both ends

The version of two pointers you'll meet first puts lo on the first element and hi on the last, and moves one of them inward on every step until they meet. There's not much code to it. What makes it correct is an argument you have to be able to say out loud, and I'd say it in the interview even if nobody asks, because it's the part they're actually marking.

The argument always has the same shape. Look at the pair (lo, hi) and decide that one of the two ends can't be part of any better answer with anything still left between them. Then that end goes and the range shrinks by one. After at most n − 1 steps there's nothing left, and you've ruled out every pair without ever looking at most of them.

Squaring a sorted array is a good first example because it doesn't look like a pair problem at all. Take [−6, −2, 0, 1, 4]. Once you square them the order breaks, since −6 becomes the biggest. But the largest square has to come from one of the two ends, because those are the values furthest from zero on each side. So we compare the two ends, write the bigger square into the last free slot of the output and move that pointer in. We fill the answer from the back, and there's no sort.

The thing to notice is that we're asking which end wins, not which pair works. Plenty of two pointer problems are like that, and the discard argument is the same one: the end that loses has nothing left to offer.

Here's one where the input isn't sorted when you get it and you sort it yourself first. Each boat holds at most two people and a weight limit, and we want the fewest boats. After sorting, look at the heaviest person still waiting. If even the lightest person can't share with them, nobody can, so they go alone. If the lightest can share, put them together, because the lightest person is the easiest one to fit with anyone else later and we lose nothing by using them up now.

It's easy to come away thinking two pointers needs sorted input, and that's not quite right. In the container with the most water the heights are in any order, and the scan still works, because the shorter of the two walls caps every container it could make with a wall further in and all of those are narrower too. So that's the test I'd use. If you can prove that one end has had its best chance already, you can move it, sorted or not. If you can't prove it, you probably want a hash map instead.

Rain water trapped between walls goes one step further. Each pointer carries the tallest wall it has seen so far, and the side whose maximum is lower is the side whose water level is already known. It's the same idea with a bit more state.

• Pair with a given sum in a sorted array
• Count the pairs whose sum is below a target
• A palindrome, ignoring punctuation and case
• A palindrome after deleting at most one letter
• Squares of a sorted array, in order
• Two walls holding the most water
• Fewest boats under a weight limit
• Subsequences whose smallest and largest fit a target
• Rain water trapped between walls
• The shortest part to sort so the whole array is sorted
• The next permutation, in place