In a write-pointer compaction loop, what invariant guarantees the write never destroys unread data?
answer
- compare the two indices each step
- one index moves always, one sometimes
- which index can never be ahead
- the write lands in already-read territory
- self-copy while nothing has been dropped
basics
~20 sThe write index advances only on a keep while the read index advances every step, so write never overtakes read. Every slot written was therefore already read, and the region below write holds exactly the survivors so far, in order.
solid answer
~40 sTwo facts drive it. The read index advances on every iteration; the write index advances only on a keep. So `write <= read` holds at every step, which means the slot being written was either already consumed or is the very slot just read — never an element still waiting to be examined. The second half of the invariant is `[0, write)` holds exactly the kept elements seen so far, in their original relative order; that is what makes the pass order-preserving. Before the first drop, `write == read` and the copy is a self-assignment: harmless, and worth branching around only when a write is expensive, never for correctness. Total cost is one pass, at most `n` copies, `O(1)` extra space.
code
pseudocode · 10 lineswrite = 0
for read in 0..length(a)-1
if valid(a[read])
a[write] = a[read]
write = write + 1
...
// invariant at every step: write <= read
// [0, write) = valid frames among a[0..read-1], in order
// [read, n) = untouched input
return write // number of valid framesgo deeper
Recall that the write index moves only when an element is kept, while the read index moves on every iteration, and that survivors end up packed at the front in their original order.
State the invariant precisely — write is never ahead of read, and the region below write holds exactly the kept elements so far — and use it to argue the overwrite can never destroy unread data.
Demonstrate that the equal-index self-copy is a no-op you branch around only when a write is genuinely expensive, and that the pass costs writes proportional to the tail after the first hole, not to the number of drops.
Frame written invariants as what makes single-pass in-place code reviewable at all: a reviewer who is handed the invariant checks two branches instead of simulating the loop in their head.
## The loop and its two indices The pattern is a single forward sweep with two indices over the same array. `read` visits every slot in turn. `write` marks where the next kept element belongs. On a keep, the element is copied to `a[write]` and `write` moves on; on a drop, `write` stays and the next keep will land on the hole. Picture the concrete setting: a fixed frame buffer on a memory-constrained device, and a pass that must discard corrupt frames without allocating a second buffer, because there is no second buffer to allocate. ## The invariant, stated properly At the top of every iteration: 1. `0 <= write <= read <= n` — the write index never overtakes the read index. 2. `[0, write)` contains **exactly** the valid frames among `a[0 .. read-1]`, in their original relative order. 3. `[read, n)` is untouched — still exactly as the caller supplied it. Part 1 is what makes the overwrite safe. Part 2 is what makes the result correct *and* order-preserving. Part 3 is what makes part 1 matter: because the unread suffix is pristine, and the write index is inside the already-read prefix, no assignment can ever clobber an element that has not been classified yet. ## Why part 1 holds It is a two-line induction. Initially `write == read == 0`. Each iteration advances `read` by one, and advances `write` by at most one. A quantity that grows by at most one can never overtake a quantity that grows by exactly one, given they started equal. So `write <= read` is preserved forever. There is no case analysis to do and no clever ordering of statements to get right — the inequality is structural. ## The self-copy, and the branch people add for the wrong reason Until the first frame is dropped, `write == read`, so `a[write] = a[read]` writes a value onto itself. It is a no-op in effect, not a bug, and the invariant does not care. Engineers sometimes add `if write != read` and describe it as a correctness guard; it is not. It is an optimisation, and whether it pays depends entirely on what a write costs: - **Small elements** — the branch is often more expensive than the copy, and the predictor has to learn a data-dependent pattern. Skip the guard. - **Large elements, or writes with real cost** — copying a fat record, dirtying a page that will have to be written back, or triggering a write barrier. Then guarding is worth it. A sharper version of the same optimisation: scan forward until the first drop, and only then start the trailing write index. Everything before the first hole is already in place, so you pay zero writes for it. ## Cost One pass: `n` reads, at most `n` writes, `O(n)` time, `O(1)` auxiliary space. Note that the write count does not depend on how many elements are dropped — dropping one element out of a million still costs a near-full sweep of copies (unless you use the first-hole trick above). That is the price of order preservation, and it is the reason a cheaper, order-destroying alternative exists at all. ## The mirrored version When you must compact toward the *end* of the array — for instance when merging a second sequence into spare capacity at the tail — the whole thing mirrors. Both indices walk downward, the invariant becomes `write >= read`, and the survivors accumulate in `[write, n)`. The reasoning is identical: the write index sits inside the region already consumed, so it cannot destroy anything still pending. Choosing the direction is exactly the question of which side has the slack. ## Common ways the invariant gets stated wrong - "`[0, read)` holds the survivors" — no, that region holds survivors *and* the holes left by drops; only `[0, write)` is dense. - "You need a temporary copy of the array" — that abandons the `O(1)` space constraint that motivated the pattern. - "`write` could pass `read` if many elements are kept" — keeping every element makes them equal, never crossed. - "The order among survivors might change" — it cannot; copies move elements strictly leftward, and never past one another. ## In an interview State the invariant out loud before writing the loop, then check it against the two branches. That is the whole difference between a candidate who simulates the loop on paper hoping it works and one who argues it correct in two sentences.
- Is the self-copy when the two indices are equal worth branching around?For correctness, never — writing a value onto itself changes nothing. It is purely an optimisation, and it pays only when a write is expensive: fat records, a dirtied page that must be written back, a write barrier. For small elements the data-dependent branch usually costs more than the copy. A better variant is to skip forward to the first dropped element and only then start the trailing index.
- How does the invariant change if you compact toward the end of the array instead?It mirrors. Both indices walk downward, the relation becomes `write >= read`, and the survivors accumulate in the suffix `[write, n)` rather than the prefix. The safety argument is identical — the write index sits inside the region already consumed, so nothing pending gets clobbered. You pick the direction based on which end has the spare capacity.
- How many element writes does the pass cost when only one element is dropped?Nearly `n` — every element after the single hole gets copied one slot left. The write count tracks the position of the first drop, not the number of drops. Starting the write index at the first hole avoids the wasted self-copies before it, but everything after still moves. That asymmetry is exactly why an order-destroying removal can be attractive.
saying these in an interview costs you the question
- Claims a temporary second array is required
- Thinks the write index can overtake the read index
- Guards write == read believing correctness demands it
- States the dense region as [0, read) rather than [0, write)
- Expects survivor order to change during the sweep