Algorithms from zero
Working in place
You need to rearrange an array—reverse it, remove some elements, move zeros to the end. The easy way: build a new output array, O(n) space. The hard way: rearrange the original array’s cells directly, using only a few pointers and temporary variables. O(1) auxiliary space. The hard way is called in-place modification, and it matters when memory is scarce or the dataset is huge.
After this lesson you can explain what in-place means (rearrangement using O(1) auxiliary space), recognize problems that allow in-place solutions, code three core techniques (swapping, write-pointer compaction, and two-pointer reversal), understand the space-vs.-complexity tradeoff, and see why in-place algorithms destroy the original array.
In-place modification means rearranging an array by overwriting its own cells, using only O(1) extra memory (a few pointers and temporary variables). The alternative—building a new output array—costs O(n) extra space.
The contrast: naive vs. in-place
Suppose you want to remove all zeros from [1, 0, 2, 0, 3, 0, 4] and compact it.
Naive approach:
const result = [];
for (const x of arr) {
if (x !== 0) result.push(x);
}
// result = [1, 2, 3, 4], but we built a new array (O(n) space)In-place approach:
let write = 0; // Pointer: where to write the next kept element
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
arr[write] = arr[i]; // Overwrite in place
write++;
}
}
// arr[0..write-1] = [1, 2, 3, 4], no new array (O(1) space)Both produce the same logical result; one uses O(n) space, the other O(1).
Why does in-place matter?
- Large datasets: If you have a 1 GB array, allocating another 1 GB for output is expensive.
- Memory limits: Embedded systems or cloud functions with tight memory budgets.
- Input preservation: Sometimes you want to preserve the original and accept the space cost. In-place destroys it.
Three core in-place techniques
1. Swapping
Exchanging two cells directly:
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap in one lineUsed in: reversing an array, rearranging by parity (evens then odds), in-place sorting.
2. Write-pointer technique
A pointer (write) marks where the next kept element should go. A scan pointer (i) moves through the array. When scan finds a keeper, overwrite at write’s position and advance write.
let write = 0;
for (let i = 0; i < arr.length; i++) {
if (condition(arr[i])) {
arr[write] = arr[i];
write++;
}
}Used in: removing duplicates (from lesson 03), removing a target value, filtering.
3. Two-pointer reversal
Use opposite-end pointers (from lesson 03), swap endpoints, move inward:
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}Used in: reversing an array or string in place.
The cost: in-place destroys the input
An in-place algorithm modifies the original array. If you need both the original and the result, you must copy before calling the algorithm. This is the tradeoff: O(1) auxiliary space at the cost of destructive input.
Let us code three classic in-place problems.
1. Reverse an array in place (two-pointer swap):
function reverseInPlace(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}2. Remove a target value in place (write-pointer):
function removeValue(arr, val) {
let write = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== val) {
arr[write] = arr[i];
write++;
}
}
return write; // New length (elements to keep)
}3. Move all zeros to the end in place (write-pointer):
function moveZeros(arr) {
let write = 0;
// First pass: compact non-zeros to the front
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
arr[write] = arr[i];
write++;
}
}
// Second pass: fill the rest with zeros
while (write < arr.length) {
arr[write] = 0;
write++;
}
}Try these:
Let us trace remove value on [1, 0, 2, 0, 3, 0, 4] removing 0:
1
function removeValue(arr, val) {
2
let write = 0;
3
for (let i = 0; i < arr.length; i++) {
4
if (arr[i] !== val) {
5
arr[write] = arr[i];
6
write++;
7
}
8
}
9
return write;
10
}
Now trace reverse in place on [1, 2, 3, 4, 5]:
1
function reverseInPlace(arr) {
2
let left = 0, right = arr.length - 1;
3
while (left < right) {
4
[arr[left], arr[right]] = [arr[right], arr[left]];
5
left++;
6
right--;
7
}
8
}
| Problem | Time | Space (Input) | Space (Auxiliary) | Notes |
|---|---|---|---|---|
| Reverse array in place | O(n) | O(n) | O(1) | Two pointers swap; only left and right variables |
| Remove a value in place | O(n) | O(n) | O(1) | Write pointer + scan pointer; no new array |
| Move zeros to end in place | O(n) | O(n) | O(1) | Two passes: compact, then fill |
| Remove a value (build new array) | O(n) | O(n) | O(n) | Creates new output array (not in-place) |
Why is this better than the naive approach?
A naive array removal builds a fresh array (O(n) auxiliary space). An in-place removal overwrites the original, using only a write pointer (O(1) auxiliary space).
For small arrays, the difference is negligible. For a 1 GB array, allocating another 1 GB is prohibitive.
The space-time tradeoff:
- In-place: O(1) auxiliary space, but destroys the input.
- Naive (build new): O(n) auxiliary space, but input is safe.
Choose based on whether you can afford to lose the original.
Why does the in-place remove-value algorithm use a write pointer?
What is the auxiliary space complexity of reversing an array in place with two pointers?
After calling removeValue([1, 0, 2, 0, 3], 0), what length does the function return?
When you run an in-place algorithm, what happens to the original array?
The write-pointer technique is most useful when:
Common mistake
Forgetting that in-place algorithms destroy the input. You call removeValue(myArray, 5) thinking you can still use myArray afterward. But the algorithm modifies myArray directly. If you needed the original, you should have copied it first: const backup = [...myArray]; removeValue(myArray, 5);. This is a common gotcha in interviews and production code.
Edge cases
Empty or single-element arrays. If the array is empty, the loop never runs and write stays 0 (or the function returns 0). If the array has one element and you are reversing or removing a value, the pointers meet or pass immediately, and the array is unchanged. Both cases handle correctly.
What is the main advantage of an in-place algorithm compared to building a new output array?
In-place modification rearranges an array without building a new one, using only O(1) auxiliary space (a few pointers and variables).
Key facts:
-
Swapping: Direct cell exchange using
[a, b] = [b, a](or temp variable). Used in reversals and rearrangements. -
Write-pointer technique: A pointer marks where to write the next kept element. A scan pointer moves through the array. When scan finds a keeper, write it at write’s position and advance write. Used to filter, remove duplicates, and compact.
-
Two-pointer reversal: Opposite-end pointers swap and move inward. O(n) time, O(1) auxiliary space.
-
The tradeoff: In-place saves memory but destroys the original array. If you need both, copy first.
-
When it matters: Large datasets, memory limits, embedded systems. For small arrays, the space saving is negligible.
Next, you will see in-place ideas extended to linked lists (where the structure is already “in place”) and to sorting algorithms that promise O(log n) or O(1) auxiliary space.