Removing one element from an array: when may you swap with the last instead of shifting?

## Two removals, two results Cancel a booking held at index `i` in an array of n bookings. The slot has to stop being part of the live data, and there are exactly two cheap ways to arrange that. **Shift-left.** Copy `i+1` into `i`, `i+2` into `i+1`, and so on up to the last used slot, then decrement the count. Elements move: `n − i − 1`. The surviving records keep the exact order they had, so a sorted array stays sorted and an insertion-ordered array stays insertion-ordered. Cost is Θ(n − i) — constant when you remove the last booking, linear when you remove the first. **Swap-with-last.** Copy the last used element into slot `i`, then decrement the count. Elements move: one, regardless of n and i. Cost Θ(1). Every surviving record is still present, but one of them has changed position, so the sequence is a *permutation* of what it was, not a subsequence of it. That difference — subsequence versus permutation — is the whole decision. It is not a performance tradeoff between two implementations of "remove"; it is two operations that happen to share a name. ## When order is not load-bearing Swap-with-last is safe when nothing downstream can observe the permutation. In practice that means checking four things about the array: 1. **Nothing renders it in stored order.** If cancelled-booking cleanup silently reshuffles the confirmation list a user is looking at, the bug shows up as "the rows jump around", which is reported late and diagnosed slowly. 2. **Nothing is kept sorted here.** If the array is maintained in start-time order so that scans can stop early, a single swap breaks the invariant that code relies on, and the failure appears far from the removal. 3. **No comparison or grouping depends on original order.** Any downstream step whose result differs when equal-ranking records swap places is order-dependent, even if nobody wrote that requirement down. 4. **No position is held elsewhere as a handle.** Both strategies invalidate stored positions, but differently, and that is worth stating precisely because it is where the O(1) claim most often quietly fails. ## The stored-position problem Suppose some other part of the system keeps "the booking at index 12" as a reference. After a **shift-left** at index 5, every index above 5 is off by one — every stored handle in the tail is now silently wrong, which is a catastrophic, wide invalidation. After a **swap-with-last**, exactly one handle is wrong: the one that pointed at the old final slot, whose record now lives at `i`. That narrowness is what makes the technique workable in systems that must track positions: a single handle can be repaired in constant time if you maintain a reverse mapping from record to position and update it on the swap. So the correct summary is not "shifting is safe and swapping is dangerous". It is that shifting preserves *order* and destroys *positions in bulk*, while swapping destroys *order* and disturbs exactly one position. Which of the two you can afford depends on what the rest of the system reads. ## Removing by identity, not by index A claim of O(1) removal assumes you already hold `i`. If the request is "cancel booking #4482" and you must scan the array to locate it, that scan costs Θ(n) and dominates whichever repair you pick — the constant-time swap saves nothing on the total. Interviewers probe here deliberately, because "removal is O(1)" stated without the precondition is the same error as claiming constant-time access after paying for a linear search to find the index. State the precondition before you state the cost. ## Capacity and the tail slot Neither removal shrinks the underlying array; a fixed-size array's capacity is a property of the allocation, not of how many slots are in use. Both strategies work by decrementing a live-count and leaving the trailing slot outside the live region. If the elements are references to larger objects, that abandoned slot may still be holding one alive; deliberately clearing the vacated tail slot is a small, cheap habit that avoids retaining data nobody can reach any more. ## Saying it correctly Say: shifting left is Θ(n − i) and preserves relative order; swap-with-last is Θ(1) and does not; choose by asking whether any reader of this array can observe order, and remember both costs assume the index is already known. Then name the one consequence a weaker answer leaves out — that stored positions are invalidated either way, broadly by the shift and narrowly by the swap.