Stable Compaction & Cyclic Placement

The previous lesson's converging pointers move toward each other and meet in the middle — a symmetric shape. These two techniques break that symmetry: the pointers move at different speeds, or the destinations aren't neighbors at all. Same discipline — pick an invariant, prove it in three steps — applied to a less obvious shape.

Technique 3: read/write pointers (stable compaction)

The workhorse. Task: keep some elements, drop the rest, preserve relative order, O(1) space.

Back to the train one more time: an inspector walks car by car from the engine, checking each one's cargo. Cars carrying valid cargo get re-coupled immediately behind the last car that passed inspection — no gap, no reshuffling of cars already re-coupled — while cars carrying nothing worth keeping are simply skipped and left behind on the original track. By the time the inspector reaches the caboose, every kept car is coupled into one short, gap-free train at the front, in the same relative order it started in.

Two indexes walk the same array:

• read scans every element, left to right — the inspector walking car by car.
• write marks the boundary of the finished prefix — the coupling point where the next kept car will join the shortened train.

Invariant: nums[0 .. write) holds exactly the keepers seen so far, in their original relative order.

def keep_if(nums: list[int], keep) -> int:
    write = 0
    for read in range(len(nums)):
        if keep(nums[read]):
            nums[write] = nums[read]
            write += 1
    return write          # keepers occupy nums[0:write]

The three steps:

• Initialization. write = 0, so nums[0 .. 0) is the empty range. Zero keepers seen, zero keepers stored. True.
• Maintenance. read advances every iteration; write advances only when a keeper is placed. So write ≤ read always holds — the inspector never re-couples a car further forward than one already inspected. That is the safety argument: the slot you overwrite has already been read on this or an earlier iteration, so you can never destroy data you still need. A keeper appends to the prefix and grows it by one; a non-keeper leaves the prefix alone. Either way the invariant survives.
• Termination. read has passed every element, so "keepers seen so far" means all of them. The invariant now reads: nums[0 .. write) holds every keeper, in order. write is the new logical length.

Note what the invariant does not promise. It says nothing about nums[write .. n). That region is leftover history, which is precisely why the function returns a length instead of pretending the array shrank.

Step through the template below — the tinted regions are the invariant:

The next two problems, Remove Duplicates and Move Zeroes, are this exact template with different keep conditions. That's why they're your first solve-first exercises.

Technique 4: cyclic placement (a preview)

Some rearrangements are permutations with known destinations: "the element at i belongs at (i + k) mod n." Read/write pointers don't apply here — there's no single prefix growing left to right, because every element's destination can be anywhere.

You can chase each displacement cycle instead — hold a value, drop it at its destination, pick up whatever was there, continue — for O(n) time and O(1) space. Picture a group of people each holding one parcel, where every parcel has a specific new owner: you take your neighbor's parcel to give to its rightful owner, but that owner is already holding a parcel of their own, which you now must carry onward to ITS rightful owner, and so on — you keep passing parcels along a chain of owners until, eventually, someone hands you the parcel that was meant for you all along, closing the loop. It's subtle, because you have to detect when a cycle closes and where the next one starts.

That is the trap, drawn. With n = 6 and k = 2 the arrows do not form one big loop — they form two disjoint cycles, like two separate parcel-passing groups who never hand anything to each other. Following displacements from index 0 returns you to 0 having moved only half the array.

In general, shifting n elements by k splits them into exactly gcd(n, k) disjoint cycles, each of length n / gcd(n, k) — here gcd(6, 2) = 2, so two cycles of length 3. Change the shift and the shape changes with it: n = 5, k = 2 gives gcd(5, 2) = 1, a single cycle that touches all 5 elements before closing. So the algorithm can't assume one pass through the array finishes the job — it has to notice when a cycle closes, jump to an index it hasn't touched, and go again.

Rotate Array offers it as the expert variant, and "index as destination" comes back in cycle sort and several hard problems.