Reader / writer pointers

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The list 0, 1, 0, 3, 12 should become 1, 3, 12, 0, 0: all the zeros moved to the end, the other numbers keeping their order, and you must do it inside the same array without making a new one.

By hand you might find a zero and shift everything after it one step left, then put the zero at the end. Each shift moves up to n elements, and there can be up to n zeros, so that is O(n²) moves. For an array of 100,000 numbers that is billions of moves to do something that sounds trivial.

Build the structure, one piece at a time

Two indices into the same array, with two different jobs.

The reader r walks the array once, left to right, looking at every element. The writer w marks the next slot where a kept element belongs. The writer never overtakes the reader, so it only ever writes into slots the reader has already finished with.

Rule: when the reader finds an element worth keeping (here: non-zero), place it at slot w and advance w. Otherwise just advance r. For "move zeroes" the placing is a swap, so the zero that was at w moves to r's position and nothing is lost.

The structure to picture is three zones: slots 0 … w − 1 are the finished answer so far, slots w … r − 1 are rejected elements, and slots from r onward are not yet read. Changing the "worth keeping" test changes the problem: "not equal to the previous kept element" removes duplicates from a sorted list; "not equal to x" removes every x; in string compression the writer emits a letter and a count while the reader counts a run.

Why it is correct

The invariant: slots 0 … w − 1 hold exactly the kept elements among the first r, in their original order. At the start r = w = 0 and the claim is about nothing. When the reader skips an element the prefix is unchanged and the claim still describes the first r + 1 elements. When it keeps one, it goes to slot w, which is the next free slot after all earlier kept elements, so order is preserved. Because w ≤ r always holds, writing at w never destroys an unread element. When r reaches the end, the prefix is the whole answer.

Why it is fast

The reader takes n steps and does at most one swap per step, so at most n swaps and n comparisons: O(n) time, with two integers of extra memory, O(1). Against the shift-everything method's O(n²), the gain comes from never moving an element more than once: each kept element travels straight to its final slot.

How to recognise it in an interview

Cues: "in place", "remove", "compact", "move all X to the end", "return the new length", "O(1) extra space", especially on arrays or strings. The first thing to say: "I will use a reader pointer that scans everything and a writer pointer that only advances on elements I keep; the prefix before the writer is the answer."

Move Zeroes is the example. Remove Duplicates from Sorted Array keeps an element when it differs from the last written one. String Compression is the same two pointers on characters, where the reader measures a run and the writer writes the letter followed by the run length's digits.

02The idea in one line

The writer trails the reader and keeps only what qualifies.

Reach for it when: Remove duplicates/elements in place, move zeroes, string compression.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Move Zeroes on [0,1,0,3,12]. These are its captions in order, so you can follow without the video or check a step you missed.

1. r reads every element; w is where the next non-zero belongs
2. nums[0] = 0: nothing to keep, only r moves
3. nums[1] = 1 is non-zero: swap into slot 0, w → 1
4. nums[2] = 0: nothing to keep, only r moves
5. nums[3] = 3 is non-zero: swap into slot 1, w → 2
6. nums[4] = 12 is non-zero: swap into slot 2, w → 3
7. Prefix [0, w) holds every non-zero in order; zeros fell to the end
8. One reader, one writer, no extra array: O(n) time, O(1) space

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Two Pointers: Opposite ends converge, Fix one, two-pointer the rest, Dutch national flag partition, Merge two sorted sequences, Two-sided max walls.