Array Deletion and Modification

What is this?

Picture a row of theater seats that's bolted to the floor — you can't yank a chair out and leave a gap, the seats don't move. So instead of "deleting" someone, you ask everyone you want to keep to slide down and fill the front rows neatly, then put up a sign saying "the show only uses the first N seats." That's the whole idea: you tidy the keepers into the front of the array and report how many there are, without ever needing a second room.

💡 Fun fact: This "two pointers, one slow and one fast" cleanup is the same core move that real databases like Cassandra and RocksDB run constantly under the hood, in a step called compaction — quietly rewriting their files to squeeze out stale and duplicate records so your queries stay fast.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: you can't truly delete from a fixed-size array — there's no hole to remove. So you overwrite in place using a write pointer that lags behind a read pointer, and report a new logical length. Master that one reflex and a whole family of "remove / compact / filter" problems collapses into a single clean pass.

1. What "in-place deletion" really means

An array is a contiguous block of memory of fixed size. There is no remove button that shrinks it — the slots don't go anywhere. "Deleting" really means rearranging the survivors into a clean prefix and telling the caller how long that prefix is. The garbage past it is left as scratch.

The engine is two indices walking the same array:

The read pointer inspects each element; the write pointer only advances when the read pointer finds something worth keeping. Because the write pointer can never overtake the read pointer, every survivor is copied at most once — so the whole compaction is a single O(n) sweep with O(1) extra space.

⚠️ The classic beginner trap is to "delete" by shifting the tail left every time you drop an element. That's O(n) work per deletion → O(n²) overall. Overwriting with a write pointer is the fix: leave the dead elements in place and march the survivors over them.

2. Where you'll actually meet this

In-place compaction is a hot inner loop in real infrastructure, not a worksheet exercise:

• LSM-tree compaction (Cassandra, RocksDB, LevelDB). Merging sorted SSTable runs writes out a compacted run, dropping superseded/duplicate keys as it streams — a read/write-pointer dance over sorted data.
• Kafka log compaction. A segment is rewritten keeping the latest record per key; obsolete copies are squeezed out during the rewrite.
• Columnar & vectorized analytics (Arrow, Parquet, DuckDB). Filtering or run-length encoding a column compacts surviving values into a dense output vector in place.
• Networking. Coalescing retransmitted, sequence-sorted packets or collapsing adjacent duplicate ACKs before handing data up the stack.
• Finance. Compacting a sorted tick/quote stream so the order-book builder sees each price level once.
• Retail / warehouse ops. Dedping a pick-list sorted by bin so a picker visits each location once.

If a problem says remove, delete in place, compact, filter out, keep only, move all X to the end, or return the new length — this chapter's toolkit applies.

3. The deletion toolkit (patterns to recognise)

1. Read/write two pointers. read scans; write marks where the next survivor lands. Copy nums[read] → nums[write] and bump write only when the element passes your keep-test. This is the spine of nearly every in-place removal.
2. Overwrite, never shift. Dropping an element costs nothing — you simply don't advance write. Avoid the O(n²) "shift the tail left" trap.
3. Return the length, not the array. The contract is a number k plus a valid prefix nums[0..k-1]. Everything after k is intentionally undefined.
4. Exploit structure to cheapen the keep-test. On a sorted array, "is this a duplicate?" becomes "is it equal to the previous survivor?" — one comparison, no hash set, O(1) space.

4. A 30-second worked example (compact a sorted run)

Buffer [2, 2, 2, 7, 7, 8]. Keep only the first copy of each run, in place.

No second buffer, no shifting — one walk, two pointers, a length out. That single reflex is the heart of the first problem in this chapter.

5. Problems in this chapter

▶ Remove Duplicates from Sorted Array

A sorted buffer arrives with consecutive repeats (think retried telemetry reports); collapse each run to one copy in place and return how many distinct values remain. Teaches the read/write two-pointer reflex, why sortedness kills the need for a hash set, and how overwriting beats shifting.
Pattern: lagging write pointer. Target: O(n) time, O(1) space.

(More modification problems — remove element, move zeroes, remove duplicates II — slot in here as the chapter grows; they all reuse tools #1–#3 above.)

6. Common pitfalls 🚫

• Shifting the tail on every delete — turns an O(n) sweep into O(n²). Overwrite with a write pointer instead.
• Returning the array instead of the length — the grader reads k slots; the tail is scratch and may legitimately hold stale values.
• Forgetting the empty array — guard len == 0 before touching nums[0].
• Reaching for a hash set on sorted input — that's O(n) space you don't need; adjacency already encodes "seen it."
• Advancing the write pointer unconditionally — it must move only when an element survives the keep-test, or you'll copy duplicates forward.

7. Key takeaways

1. You can't shrink a fixed array — deletion = compacting survivors into a prefix + returning its length.
2. The read/write two-pointer sweep does it in O(n) time, O(1) space, copying each survivor at most once.
3. Overwrite, don't shift — dropping an element is free; the O(n²) shift loop is the trap.
4. Lean on structure: a sorted array makes the keep-test a single neighbour comparison — no extra space.
5. The same lagging-pointer pattern generalises to remove element, move zeroes, and dedup II — and it's exactly how production compaction pipelines stream a cleaned result.