In-Place Partitioning & Rearrangement

Core idea: One pointer reads every element; a second pointer writes only the elements you want to keep, packing them toward the front. The region behind the write pointer is always the finished, cleaned result — so you transform the data in a single forward pass with O(1) extra space.

The read–write pointer, in one picture

Think of a conveyor belt feeding a packing worker: items stream past (read), and the worker drops only the good ones into a clean box, left to right (write). Bad items are skipped, never shifting anything backward. The clean region grows forward and never needs a second array.

This is the same machine behind garbage-collector compaction (slide live objects over dead ones), log/LSM compaction (drop tombstones), and array defragmentation — all O(n), all in place.