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.
Remove duplicates in place. The values are sorted, so equal values sit together. A reader scans; a writer only moves when a value is new.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
The reader sees 1. The last kept value is 1. What happens?
Answer: Skip it. 1 is already the last thing kept. Only the reader moves.
The reader sees 2. The last kept value is 1. What happens?
Answer: Keep it. 2 has not been kept yet, so the writer copies it forward and advances.
The reader sees 2. The last kept value is 2. What happens?
Answer: Skip it. 2 is already the last thing kept. Only the reader moves.
The reader sees 2. The last kept value is 2. What happens?
Answer: Skip it. 2 is already the last thing kept. Only the reader moves.
The reader sees 3. The last kept value is 2. What happens?
Answer: Keep it. 3 has not been kept yet, so the writer copies it forward and advances.
The reader sees 4. The last kept value is 3. What happens?
Answer: Keep it. 4 has not been kept yet, so the writer copies it forward and advances.
The reader sees 4. The last kept value is 4. What happens?
Answer: Skip it. 4 is already the last thing kept. Only the reader moves.
The reader sees 5. The last kept value is 4. What happens?
Answer: Keep it. 5 has not been kept yet, so the writer copies it forward and advances.
How it runs, step by step
Remove duplicates in place. The values are sorted, so equal values sit together. A reader scans; a writer only moves when a value is new.
Removing duplicates from a sorted array with a read pointer and a write pointer.
1 equals the last kept value, so it is skipped. The writer stays put.
Reading 1 at index 1. It repeats 1, so it is skipped.
2 is different from the last kept value 1, so it is written at index 1.
Reading 2 at index 2. It is new, so it is written to index 1.
2 equals the last kept value, so it is skipped. The writer stays put.
Reading 2 at index 3. It repeats 2, so it is skipped.
2 equals the last kept value, so it is skipped. The writer stays put.
Reading 2 at index 4. It repeats 2, so it is skipped.
3 is different from the last kept value 2, so it is written at index 2.
Reading 3 at index 5. It is new, so it is written to index 2.
4 is different from the last kept value 3, so it is written at index 3.
Reading 4 at index 6. It is new, so it is written to index 3.
4 equals the last kept value, so it is skipped. The writer stays put.
Reading 4 at index 7. It repeats 4, so it is skipped.
5 is different from the last kept value 4, so it is written at index 4.
Reading 5 at index 8. It is new, so it is written to index 4.
5 unique values sit in the first 5 slots. Whatever is past the writer is leftover and ignored.
The first 5 slots hold the unique values in order.
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