Arrays & Strings
Write in place
Why it matters
Some problems forbid a second array. You have to rearrange the input where it already sits, using O(1) extra memory. The constraint is real outside interviews too: when a buffer holds millions of records, copying it to drop deleted ones doubles the memory you need. The result must preserve the kept records in order without allocating another buffer.
Example
Move Zeroes
Given an integer array nums, move all 0s to the end while keeping the relative order of the rest. Modify the array in place and return it.
- Input
- nums = [0, 1, 0, 3, 12]
- Output
- [1, 3, 12, 0, 0]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Move Zeroes
nums = [0, 1, 0, 3, 12]→[1, 3, 12, 0, 0]
The baseline, Copy, then write back, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
Instead of copying [1, 3, 12] into a second list, pack those values into the front of nums as read scans [0, 1, 0, 3, 12]. Each swap fills the next write slot and moves a zero behind it.
On nums = [0, 1, 0, 3, 12], read visits each slot while write marks where the next nonzero value belongs. After read processes 3, the array is [1, 3, 0, 0, 12]: everything left of write is finished and still in its original order.
The zeros between write and read are safe to replace. The values from read onward are unexplored. When read finds 12, swapping it into write sends a zero backward without touching any unread value. Because write never passes read, the in-place update cannot erase future work.
Visual anchor
Move Zeroes
nums
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.