Two Pointer Problems
Both problems live on the same rule: start at the ends and move the pointer that can still improve things. For the container, the shorter line caps the depth, so only it is worth moving. For three sum, fix an anchor and the rest is two-sum on a sorted array.
Find every set of three values adding up to 0, without repeats. The array is sorted. Fix an anchor, then run two-sum on everything to its right.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 10, with their answers.
-4 + -1 + 2 = -3 against a target of 0. What happens?
Answer: Move left up. Too small, and right is already the largest available. Left has to move.
-4 + -1 + 2 = -3 against a target of 0. What happens?
Answer: Move left up. Too small, and right is already the largest available. Left has to move.
-4 + 0 + 2 = -2 against a target of 0. What happens?
Answer: Move left up. Too small, and right is already the largest available. Left has to move.
-4 + 1 + 2 = -1 against a target of 0. What happens?
Answer: Move left up. Too small, and right is already the largest available. Left has to move.
The next anchor is -1. The previous anchor was -4. What now?
Answer: Search from it. A new anchor value means new triplets are possible.
-1 + -1 + 2 = 0 against a target of 0. What happens?
Answer: Found a triplet. Exactly 0. Record it, then keep looking for more with this anchor.
-1 + 0 + 1 = 0 against a target of 0. What happens?
Answer: Found a triplet. Exactly 0. Record it, then keep looking for more with this anchor.
The next anchor is -1. The previous anchor was -1. What now?
Answer: Skip it. Same anchor value, same partners available, same triplets. Searching again would only repeat them.
The next anchor is 0. The previous anchor was -1. What now?
Answer: Search from it. A new anchor value means new triplets are possible.
0 + 1 + 2 = 3 against a target of 0. What happens?
Answer: Move right down. Too big, and left is already the smallest available. Right has to move.
How it runs, step by step
Find every set of three values adding up to 0, without repeats. The array is sorted. Fix an anchor, then run two-sum on everything to its right.
Looking for every triplet summing to 0 in a sorted array, one anchor at a time.
Anchor -4 at index 0. Left and right start at the ends of everything to its right.
The anchor is -4 at index 0, with left at index 1 and right at index 5.
-4 + -1 + 2 = -3, short of 0. Only a bigger left value can help, so left moves up.
-4 plus -1 plus 2 is -3. Less than the target, so the left pointer moves to index 2.
-4 + -1 + 2 = -3, short of 0. Only a bigger left value can help, so left moves up.
-4 plus -1 plus 2 is -3. Less than the target, so the left pointer moves to index 3.
-4 + 0 + 2 = -2, short of 0. Only a bigger left value can help, so left moves up.
-4 plus 0 plus 2 is -2. Less than the target, so the left pointer moves to index 4.
-4 + 1 + 2 = -1, short of 0. Only a bigger left value can help, so left moves up.
-4 plus 1 plus 2 is -1. Less than the target, so the left pointer moves to index 5.
Anchor moves to -1 at index 1. Everything before it is done. Left and right reset to the ends of the rest.
The anchor is -1 at index 1, with left at index 2 and right at index 5.
-1 + -1 + 2 = 0. That is a triplet: (-1, -1, 2). Move both pointers inward.
-1 plus -1 plus 2 is 0. That is a triplet. Both pointers move inward.
-1 + 0 + 1 = 0. That is a triplet: (-1, 0, 1). Move both pointers inward.
-1 plus 0 plus 1 is 0. That is a triplet. Both pointers move inward.
Anchor -1 at index 2 is the same value as the previous anchor, so any triplet it starts was already found from there. Skip it.
The anchor -1 repeats the previous anchor and is skipped.
Anchor moves to 0 at index 3. Everything before it is done. Left and right reset to the ends of the rest.
The anchor is 0 at index 3, with left at index 4 and right at index 5.
0 + 1 + 2 = 3, past 0. Only a smaller right value can help, so right moves down.
0 plus 1 plus 2 is 3. More than the target, so the right pointer moves to index 4.
2 triplets: (-1, -1, 2) (-1, 0, 1). Each anchor ran a linear two-sum, so O(n^2) in all, with no duplicates to filter out.
2 triplets found: (-1, -1, 2) (-1, 0, 1).
Write it yourself
Define mostWater(values) and return the largest area between two lines, width times the shorter of the two. It runs in your browser against this lesson's own 3 examples.
// Start at the ends. The shorter side is the one that limits the area, so move that one inward.function mostWater(values) { return 0;}
Remember
- Container: the shorter line caps the depth, so moving the taller one can only lose width.
- Three sum: sort first, fix an anchor, then two-sum the rest with a pointer at each end.
- Skip duplicate anchors and duplicate partners, or the same triplet comes out twice.
Topics covered
Related
Where this is used
Standard librariesReversing and rotating in place
CPython reverses a list through reverse_slice, whose whole body is while (lo < hi) with one pointer stepping up and the other stepping down. The random-access branch of C++ std::reverse is that loop written as first < last, and Java's Collections.reverse walks i up and j down to meet in the middle. Rotating without a scratch buffer is the same loop three times, reverse the front, reverse the back, reverse the whole, which is the path Java's Collections.rotate takes for lists it cannot index cheaply. Nothing is compared here, so what is left is the skeleton: two ends, a swap, and the crossing test that stops it.
Systems programmingMemory that grows from both ends
The classic process layout grows the heap up from low addresses and the stack down from high ones, and in that model running out of memory is the moment those two pointers meet. Game engines use the same shape on purpose in a double-ended arena: long-lived level data allocated from one end, per-frame scratch from the other, so two different lifetimes never fragment each other. One arena serves both because the only invariant to maintain is that the ends have not crossed.
Computational geometry3SUM as a hardness yardstick
Sort plus the converging scan solves 3SUM in n squared, and no substantially faster algorithm is known. That turned it into a reference point: deciding whether any three of n points are collinear is called 3SUM-hard, meaning a subquadratic method for it would hand you one for 3SUM as well. The plain two-pointer bound written here is the baseline those reductions are measured against.
CryptographyMeet in the middle on subset sum
Horowitz and Sahni split n items in half, enumerate every subset sum of each half, sort both lists and then walk one from the low end and the other from the high end looking for a pair that hits the target. That converging scan is what turns 2^n work into 2^(n/2), and the same halve-and-match idea is what makes double encryption far weaker than its doubled key length suggests. Drop the sorted order and there is no direction signal, so you are back to comparing every pair.
Why it works this way
Why is dropping the shorter line lossless?
Moving a pointer does not retire one pair, it retires every remaining pair that used that line. Each of those pairs is narrower than the one you just measured and still capped by the same short line, so none of them can beat it. That argument is what lets one pass stand in for the n squared pairs a brute force would check.
What if the two lines are the same height?
Then both can go: any surviving pair that keeps either one is narrower and still capped at that height. The code falls into else r--, so it drops only the right line and spends one extra step, which is correct but not the only correct move. What is never safe is moving the taller line on its own, because the short one stays behind and caps every pair you have left.
Why sort for three sum when the sort looks like the expensive part?
The sort is n log n and the anchor loop is n squared, so the sort disappears into the total and never shows up in the complexity. What it buys is the direction signal: on sorted data a sum that is too small can only be repaired by moving the left pointer, and that one fact replaces the entire inner nested loop. On unsorted input neither pointer has a rule to follow and the technique has nothing to stand on.
The duplicate skip that looks right and is not
The guard compares backwards on purpose: a[i] == a[i - 1] means this anchor was already used. Writing a[i] == a[i + 1] instead skips the first copy of a repeated value and keeps the last, which silently drops triplets that need two equal values, such as -1, -1, 2 inside -4, -1, -1, 2. The same ordering rule holds inside the loop, where you advance past duplicate partners only after recording the hit, never before.
Read more
- 3SUMWikipedia
- Quicksort: Hoare partition schemeWikipedia
- Two pointersUSACO Guide
- Subset sum problem: meet in the middleWikipedia
- Sum of Three ValuesCSES 1641 · cses.fi
Next up
- Fast and Slow PointersOne pointer moves twice as fast as the other. Finds middles and cycles in one pass.
- Opposite Direction PointersStart at both ends and move inward. The comparison decides which one moves.
- Remove Duplicates from Sorted ArrayThe writer only copies a value that differs from the last one it kept.