When is swap-with-last array removal wrong despite costing only O(1) per element?
answer
- what lands in the hole
- cheap for whom, costly for whom
- who downstream assumed an order
- a search that quietly returns wrong
- order-destroying versus order-preserving removal
basics
~20 sSwap-with-last removal teleports the final live element into the hole, destroying the relative order of what remains. It is wrong whenever a consumer depends on that order — an arrival-ordered log, or any downstream search assuming sortedness.
solid answer
~40 sDeleting by swapping the doomed element with the last live one and shrinking the count is `O(1)` per removal, genuinely attractive when removals are rare. What it silently costs is order: the last element lands in the hole, so an array that arrived sorted is no longer sorted. That breaks anything downstream that assumed the ordering — a binary search over the array, a consumer paging through an audit trail expecting chronological order. The order-preserving alternative is a compaction sweep, which costs `O(n)` writes for the whole pass no matter how many elements go, not per removal. So the decision is not cost versus cost; it is whether the container is documented as unordered. If it is, swap-with-last is cheap and correct. If not, the sweep is the only honest option.
go deeper
Recall that swapping the doomed element with the last live one and shrinking the count is cheap, and that it changes the order of whatever remains.
Compare the per-removal cost of swap-with-last against a single order-preserving sweep, and be clear that the sweep's linear cost is for the whole pass rather than per deletion.
Bring the specification into it: identify the consumers that depend on order, name a concrete silent failure such as a search over data that only looks sorted, and choose from the requirement rather than the cost.
Own the rule for the codebase: order-destroying removal is permitted only where the container's contract says it is unordered, because otherwise no reviewer can tell a correct delete from a broken one.
## Two removal strategies, two different contracts Removing elements from an array in place comes in two flavours, and they differ in what they promise, not just in what they cost. **Order-destroying (swap-with-last).** To delete the element at index `i`, swap it with the element at the last live index, then decrement the live count. Each removal is `O(1)`: one swap, one decrement, no shifting. Nothing after `i` moves. **Order-preserving (compaction sweep).** Walk the array once with a write index that advances only on survivors, copying each survivor down to where it belongs. Survivors come out in exactly their original relative order. The pass is `O(n)`, and — this is the part people state wrongly — that `O(n)` is for the *whole pass*, not per removal. Dropping three elements out of a million costs one sweep, not three. ## What order preservation is actually protecting Consider an append-only audit trail held in a fixed buffer, ordered by the moment each entry arrived, with a retention job that purges entries matching a policy. Use swap-with-last and the purge is fast and correct in the sense that the right entries are gone. But the most recent entry has been dropped into the middle of the buffer. Now: - A consumer that renders the trail in buffer order shows events out of sequence, and nobody will notice until an incident review depends on it. - Any binary search over the buffer — for the first entry after a timestamp, say — is now searching an array that only *looks* sorted. Binary search on unsorted data does not error; it returns a wrong answer confidently. - A comparison against another ordered source produces a diff full of phantom moves. None of these fail loudly. That is what makes the choice a judgment call rather than a micro-optimisation: the cheap option's cost is paid somewhere else, later, by someone else. ## The forward-scan bug Even where swap-with-last is legitimate, there is a boundary bug that shows up constantly in review. If you scan forward and delete at index `i` by swapping in the last live element, you must **not** advance to `i+1` — the element that just landed at `i` has not been tested yet. The loop must re-examine `i` and only advance when the element there survives. And the live end must shrink first, so you never swap in an element that was itself already deleted. A loop that advances unconditionally silently keeps some elements it was told to remove; the mirror bug (never advancing) hangs. ## Choosing, and the hybrid A workable decision procedure: 1. **Is the container documented as unordered?** If yes, swap-with-last, and say so in a comment at the removal site so the next reader does not "fix" it. Sets of live entities, free lists, and pools of interchangeable objects are the natural home for it. 2. **Does anything downstream depend on order — sortedness, arrival sequence, an index into a parallel array?** Then compaction, full stop; the `O(n)` sweep is not the expensive part of your system. 3. **Are removals frequent and the array huge?** Consider marking entries dead and running one compaction sweep when the dead fraction crosses a threshold. You pay `O(1)` per removal *and* keep order, at the cost of readers having to skip dead entries and of choosing the threshold. One more refinement of the sweep worth knowing: scan forward until the first removed element before starting the write index. Everything before the first hole is already in the right place, so you pay writes only for the suffix after it. Removing an element near the end of a large array then costs almost nothing, which narrows the gap that made swap-with-last attractive in the first place. ## Cost summary | Strategy | Per removal | Whole pass, k removals | Order kept | |---|---|---|---| | Swap-with-last | `O(1)` | `O(k)` moves | no | | Compaction sweep | — (batched) | `O(n)` moves, `O(n)` time | yes | | Mark dead, sweep later | `O(1)` | one `O(n)` sweep per threshold crossing | yes | All three are `O(1)` in auxiliary space. ## What the interviewer is checking Not whether you know the trick — everyone knows the trick. Whether you ask what the array's ordering contract is before choosing, whether you can state the failure as "a downstream binary search returns a wrong answer" rather than "the order looks weird", and whether you get the re-examine-the-swapped-slot boundary right when you describe the loop.
- If you use swap-with-last while scanning forward, what is the classic boundary bug?Advancing the index after the swap. The element just moved into the current slot has never been tested, so the loop must re-examine that slot and advance only when the element there survives. The live end must also shrink before the swap, so you never pull in an element that was already deleted. Advancing unconditionally silently keeps elements you were told to drop.
- Two records out of ten million must go, and order matters. What do you do?One order-preserving sweep, but start the write index at the first removed position — everything before the first hole is already correct and costs zero writes. If purges are frequent enough that even that hurts, mark entries dead and run a single compaction when the dead fraction crosses a threshold, so removal stays constant-time and order survives.
- How would you keep the next engineer from swapping in a wrong strategy?Make the ordering contract explicit rather than implied. Name the type or the field for what it guarantees, state at the removal site why the order-destroying delete is legal there, and test the property that matters — that survivors come out in arrival order — rather than testing which elements remain. A reviewer cannot spot the bug in a strategy whose contract is unwritten.
It is like filling a gap in a shelved row of files by grabbing the last file on the shelf: quick, and nothing else has to move, but the row is no longer in order and anyone who searches it by position is now looking in the wrong place.
saying these in an interview costs you the question
- Says swap-with-last is always the better removal
- Forgets that the last element teleports into the gap
- Advances the index after swapping in the last element
- Assumes a downstream binary search still works after reordering
- Claims order-preserving removal costs O(n) per deletion