Two Pointers
Two indices moving under a rule can do in one pass what a nested loop does in n squared. The rule that moves each pointer is the whole idea.
Find two values that add up to 14. The array is sorted, so start at both ends and let the sum tell you which pointer to move.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
1 + 15 against a target of 14. Which pointer moves?
Answer: Move right down. The sum is over. Moving left up would only make it bigger, so right is the only option.
1 + 11 against a target of 14. Which pointer moves?
Answer: Move left up. The sum is short. Moving right down would only make it smaller, so left is the only option.
3 + 11 against a target of 14. Which pointer moves?
Answer: Found it. The sum is exactly 14, so neither moves.
How it runs, step by step
Find two values that add up to 14. The array is sorted, so start at both ends and let the sum tell you which pointer to move.
Looking for a pair summing to 14 in a sorted array, with a pointer at each end.
1 + 15 = 16, too big. Only a smaller right value can help, so right moves down.
1 plus 15 is 16. More than the target, so the right pointer moves to index 5.
1 + 11 = 12, too small. Only a bigger left value can help, so left moves up.
1 plus 11 is 12. Less than the target, so the left pointer moves to index 1.
3 + 11 = 14. That is the pair.
3 plus 11 is 14. That equals the target.
Pair found at indices 1 and 5 in 3 steps. One pass, no nested loop.
A pair summing to 14 was found.
Write it yourself
Define reverseValues(values) and return the same values in the opposite order. It runs in your browser against this lesson's own 3 examples.
// Swap the ends and step both pointers inward until they meet.function reverseValues(values) { return values;}
Remember
- Opposite direction needs sorted input, because the sum has to tell you which side to move.
- Same direction is a reader and a lagging writer, which compacts in place with no second array.
- If you cannot say why exactly one pointer moves, the technique does not apply.
Topics covered
Related
Where this is used
SearchIntersecting posting lists in a search index
Apache Lucene stores each term as a posting list of document ids in ascending order, and an AND query walks two of those lists with one cursor each, always advancing whichever cursor is behind. Because both sides are already sorted, the intersection falls out in a single pass over each list instead of testing every pair. Elasticsearch and Solr sit on top of the same conjunction loop.
RuntimesCompacting a heap during garbage collection
A mark-compact collector, such as HotSpot's serial old-generation collector, sweeps the heap with a reading pointer and a lagging writing pointer and slides every live object down over the dead ones. It is the remove-duplicates loop at heap scale: the writer only ever trails the reader, so objects move in place with no second heap, and wherever the writer stops becomes the new allocation boundary. Allocation afterwards is a pointer bump, which is what the pause buys you.
Operating systemsRing buffers between a producer and a consumer
The Linux kfifo, and the descriptor rings a network card shares with its driver, are two indices chasing each other around one fixed array: the producer moves the write index, the consumer moves the read index, and the gap between them is how much data is queued. Since each side only writes its own index and only moves it forward, a single producer and a single consumer need no lock. Empty and full both look like the indices touching, so implementations either leave one slot unused or let the indices run free and compare their difference.
LibrariesPartitioning inside a library sort
Hoare's partition, the step at the centre of quicksort, runs one pointer up from the left and one down from the right and swaps the pair that is on the wrong side, stopping when they cross. Java's dual-pivot quicksort for primitives and Rust's slice::sort_unstable still have this inward walk at their core, because it splits the array in place with no scratch buffer and touches each element about once. The three-way version for inputs full of equal keys is the Dutch national flag problem, the same idea with a third pointer.
Why it works this way
Why is it safe to throw away a whole side?
When the sum is too small, a[l] is finished. Every partner it still has left sits in a[l+1..r], and all of those are at most a[r], so a[l] plus any of them is still under the target. Moving l past it strikes out a whole row of the pair table in one step, which is what the nested loop was paying for. None of this survives on unsorted input: a[r] would no longer be the largest partner a[l] has left, so a sum under the target would say nothing about the pairs still unexamined.
Why is this O(n) when the pointers move in no fixed pattern?
Count travel, not nesting. l only ever rises and r only ever falls, so between them they can take at most n steps before they meet. Each pass through the loop spends exactly one of those steps, so the body runs at most n times whichever branch happens to fire.
l < r, not l <= r
With <= the final iteration puts both pointers on the same element, so a[i] + a[i] can pass the target test and l to r is returned with l and r being the same index. That is the standard two sum bug, since the problem asks for two different elements. If a variant does allow reusing one element, write <= on purpose rather than by accident.
The writer compares against the last value kept, and never overtakes the reader
a[read] != a[write - 1] tests against the most recent survivor, so a run of equal values collapses to one no matter how long it is. Comparing against a[read - 1] gives the same answer on this input, since compaction never touches a slot the reader has not already passed. The a[write - 1] form is the one that generalises: a rule like keep at most two of each value reads a[write - 2], which only means anything among the survivors. write advances at most once per read, so it always trails read and can never overwrite a value that has not been looked at yet. The array is not shortened either: everything past the returned count is stale, and the version shown assumes at least one element because it starts write at 1.
Read more
- Merge algorithmWikipedia
- Two PointersUSACO Guide
- Dutch national flag problemWikipedia
- Tortoise and hare cycle detectioncp-algorithms
- Sum of Two ValuesCSES 1640 · cses.fi