Algorithms / Two Pointers Compaction
Least You Need to Know: Read/Write Pointers, Compaction, and Deduping
A read pointer examines every element while a write pointer marks where the next kept element belongs. This is the core interview pattern for in-place filtering, removing duplicates, and compacting arrays without extra output storage.
The least you need to know
- The read pointer explores candidates; the write pointer builds the kept prefix.
- Everything before the write pointer is already in final kept form.
- Stable compaction preserves the order of kept elements because writes follow reads.
- Removing duplicates from a sorted array keeps the first representative of each block.
- The algorithm is in-place even though later positions may contain stale values.
Key notation
read
pointer scanning the full input
write
index of the next kept output slot
kept prefix
prefix `[0, write)` already rewritten correctly
Tiny worked example
- Scan the array with `read`.
- When an element should be kept, copy it to `a[write]` and advance `write`.
- Ignore rejected elements by advancing only `read`.
- At the end, the valid answer is the prefix of length `write`.
Common mistakes
- Students often think the array tail after `write` must also be cleaned, but only the kept prefix matters.
- Students often advance `write` even when rejecting an element.
- Students often forget that sorted deduping compares against the last kept value, not merely the previous index.
How to recognize this kind of problem
- The prompt asks you to modify an array in place and return the new length.
- Only kept items need to survive, often in original order.
- A separate output array would be easy, but the interview constraint forbids it.