On this page
Description
In-place manipulation changes an array without building a second one. A read index walks every element, and a write index trails behind it, copying only what you keep. That's how Move Zeroes, Remove Duplicates and Remove Element run in O(1) extra space. Real code uses it to compact a buffer without allocating a new one.
We'll go from simple to more technical:
- The pattern: a read index and a trailing write index.
- Where the same compaction runs in production code.
- The two mistakes: moving the write index too often, and forgetting the tail.
- When saving the memory is worth the extra care.
The approach
The simplest way to filter an array is to build a new one with the elements you keep. That's easy to get right, but it needs a second array as big as the first. In place, you reuse the front of the same array instead. The read index looks at each element once. When an element is a keeper, copy it to the write index and move the write index forward. Skipped elements are simply passed over.
Remove every 3 from [3, 1, 3, 4, 2, 3]:
| Read | Value | Kept? | Array after the step | Write index |
|---|---|---|---|---|
| 0 | 3 | no | 3 1 3 4 2 3 | 0 |
| 1 | 1 | yes | 1 1 3 4 2 3 | 1 |
| 2 | 3 | no | 1 1 3 4 2 3 | 1 |
| 3 | 4 | yes | 1 4 3 4 2 3 | 2 |
| 4 | 2 | yes | 1 4 2 4 2 3 | 3 |
| 5 | 3 | no | 1 4 2 4 2 3 | 3 |
The first 3 positions now hold 1 4 2, in their original order. The tail 4 2 3 is leftover.
Java
int writeIndex = 0;
for (int readIndex = 0; readIndex < nums.length; readIndex++) {
if (shouldKeep(nums[readIndex])) {
nums[writeIndex] = nums[readIndex];
writeIndex++;
}
}
// anything from writeIndex..end is now "leftover" and can be overwritten/zeroed
Python
write_index = 0
for read_index in range(len(nums)):
if should_keep(nums[read_index]):
nums[write_index] = nums[read_index]
write_index += 1
# anything from write_index..end is now "leftover" and can be overwritten/zeroed
The write index never gets ahead of the read index. So writing to nums[writeIndex] never destroys a value you still need to read.
Where you'll see it
A fixed-size buffer of cache entries can drop the expired ones this way, without allocating a new buffer. A batch of records can be split into "valid" and "needs retry" the same way. It matters on hot paths where memory or garbage-collection pressure counts.
Which tool for which job?
| You need | Use |
|---|---|
| Keep some elements, in order, O(1) space | read and write indices |
| Keep some elements, order doesn't matter | swap the removed one with the last element |
| Group three kinds of value (0s, 1s, 2s) | Dutch national flag: three pointers |
| Rotate by k in place | reverse all, then reverse each part |
Remove from a Java ArrayList | removeIf |
| Filter a Python list the caller sees | nums[:] = [...] |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Moving the write index on every element | nothing is removed | move it only when you keep one |
| Forgetting the tail | old values stay after the kept part | fill or truncate it if the contract says so |
| Removing from a list while looping over it | elements are skipped (or a ConcurrentModificationException) | read/write indices, or build a new list |
nums = [...] inside a Python function | the caller's list is unchanged | nums[:] = [...] |
| Mutating the caller's array without saying so | surprise changes elsewhere | document it, or copy first |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A solution moves writeIndex forward on every loop step, not only when it keeps an element. What happens to the array?
Show answer
Nothing is filtered. The two indexes move together, so every element is copied onto itself. The array ends exactly as it started.
2. Why does "move zeroes to the end" need a step after the loop, when "remove duplicates and return the count" doesn't?
Show answer
"Move zeroes" cares what's in the tail: it must be all zeros. So after the loop you fill from writeIndex to the end with 0. "Remove duplicates" only promises that the first k elements are right, and says the rest doesn't matter.
3. Could the write index write into a separate output array instead of the input?
Show answer
Yes. A write cursor that trails the read cursor and moves only when something is kept works the same with a separate output. Writing into the input is a memory saving on top of that idea, not part of it.
Key takeaways
- The write index moves only when an element is kept.
- It never gets ahead of the read index, so overwriting
nums[writeIndex]is always safe. - The loop only builds the kept part at the front. Handle the tail separately if its contents matter.
- In place saves O(n) memory for a little extra care. It's worth it under real memory pressure, not by default.