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 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.
اہم علامتیں
read
pointer scanning the full input
write
index of the next kept output slot
kept prefix
prefix `[0, write)` already rewritten correctly
مختصر حل شدہ مثال
- 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`.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.