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.
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
Worked example
- Scan the array with
read. - When an element should be kept, copy it to
a[write]and advancewrite. - 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
writemust also be cleaned, but only the kept prefix matters. - Students often advance
writeeven when rejecting an element. - Students often forget that sorted deduping compares against the last kept value, not merely the previous index.
How to recognize it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Opposite-End Two Pointers and Sorted Pair Search.
Least You Need to Know: Opposite-End Two Pointers and Sorted Pair SearchRelated lessons
Keep going with nearby lessons in the same topic.