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.
Each value is the height of a line. Pick two lines so the water between them is deepest: the shorter height times the distance. Start with the widest pair and squeeze inward.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
Left line is 1, right line is 7. Which pointer moves?
Answer: Move left up. 1 is the limit. Moving the taller 7 inward would keep the cap at 1 and lose width.
Left line is 8, right line is 7. Which pointer moves?
Answer: Move right down. 7 is the limit. Moving the taller 8 inward would keep the cap at 7 and lose width.
Left line is 8, right line is 3. Which pointer moves?
Answer: Move right down. 3 is the limit. Moving the taller 8 inward would keep the cap at 3 and lose width.
Left line is 8, right line is 8. Which pointer moves?
Answer: Either, they are equal. Equal heights: whichever moves, the other still caps the depth at the same value.
Left line is 6, right line is 8. Which pointer moves?
Answer: Move left up. 6 is the limit. Moving the taller 8 inward would keep the cap at 6 and lose width.
Left line is 2, right line is 8. Which pointer moves?
Answer: Move left up. 2 is the limit. Moving the taller 8 inward would keep the cap at 2 and lose width.
Left line is 5, right line is 8. Which pointer moves?
Answer: Move left up. 5 is the limit. Moving the taller 8 inward would keep the cap at 5 and lose width.
Left line is 4, right line is 8. Which pointer moves?
Answer: Move left up. 4 is the limit. Moving the taller 8 inward would keep the cap at 4 and lose width.
How it runs, step by step
Each value is the height of a line. Pick two lines so the water between them is deepest: the shorter height times the distance. Start with the widest pair and squeeze inward.
Each value is a line height. Looking for the pair of lines holding the most water, starting with a pointer at each end.
Lines 1 and 7 are 8 apart, so they hold min(1, 7) x 8 = 8. New best. 1 is the shorter line and caps the depth, so only moving it can help. Left moves up.
Lines 1 and 7 hold 8. That is a new best. The left pointer moves to index 1.
Lines 8 and 7 are 7 apart, so they hold min(8, 7) x 7 = 49. New best. 7 is the shorter line and caps the depth, so only moving it can help. Right moves down.
Lines 8 and 7 hold 49. That is a new best. The right pointer moves to index 7.
Lines 8 and 3 are 6 apart, so they hold min(8, 3) x 6 = 18. Best stays 49. 3 is the shorter line and caps the depth, so only moving it can help. Right moves down.
Lines 8 and 3 hold 18. The best is still 49. The right pointer moves to index 6.
Lines 8 and 8 are 5 apart, so they hold min(8, 8) x 5 = 40. Best stays 49. The heights tie, so moving either side is the same bet. Move left up.
Lines 8 and 8 hold 40. The best is still 49. The left pointer moves to index 2.
Lines 6 and 8 are 4 apart, so they hold min(6, 8) x 4 = 24. Best stays 49. 6 is the shorter line and caps the depth, so only moving it can help. Left moves up.
Lines 6 and 8 hold 24. The best is still 49. The left pointer moves to index 3.
Lines 2 and 8 are 3 apart, so they hold min(2, 8) x 3 = 6. Best stays 49. 2 is the shorter line and caps the depth, so only moving it can help. Left moves up.
Lines 2 and 8 hold 6. The best is still 49. The left pointer moves to index 4.
Lines 5 and 8 are 2 apart, so they hold min(5, 8) x 2 = 10. Best stays 49. 5 is the shorter line and caps the depth, so only moving it can help. Left moves up.
Lines 5 and 8 hold 10. The best is still 49. The left pointer moves to index 5.
Lines 4 and 8 are 1 apart, so they hold min(4, 8) x 1 = 4. Best stays 49. 4 is the shorter line and caps the depth, so only moving it can help. Left moves up.
Lines 4 and 8 hold 4. The best is still 49. The left pointer moves to index 6.
The most water is 49, between the lines at indices 1 and 8. 8 moves for 9 lines, one pointer step each, so O(n).
The most water is 49, between indices 1 and 8.
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.