In-Place Manipulation
Reverse, rotate, and rearrange arrays using O(1) extra space, and why interviewers love the constraint.
On this page
"Do it in place, using O(1) extra space." Interviewers add that constraint constantly, because the obvious solution usually allocates a new array and they want to see if you can avoid it. In-place manipulation - rearranging an array by swapping within it - is a small set of reliable techniques.
Reverse: the fundamental in-place move
Reversing an array with two pointers is the building block for half of these problems - swap the ends and walk inward:
// reverse a[lo..hi] in place — O(1) extra space
void reverse(int[] a, int lo, int hi) {
while (lo < hi) {
int t = a[lo]; a[lo++] = a[hi]; a[hi--] = t;
}
}Rotation via three reversals
Rotating an array right by k looks like it needs a copy, but a classic trick does it in place with
three reversals: reverse the whole array, then reverse the first k, then reverse the rest.
// rotate right by k, in place — O(n) time, O(1) space
void rotate(int[] a, int k) {
int n = a.length;
k %= n;
reverse(a, 0, n - 1); // whole array
reverse(a, 0, k - 1); // first k
reverse(a, k, n - 1); // remaining
}Walk [1,2,3,4,5] with k=2: reverse all → [5,4,3,2,1], reverse first 2 → [4,5,3,2,1], reverse
rest → [4,5,1,2,3]. Rotated, no extra array.
Overwrite with a write pointer
Many "remove/move elements" problems use a write pointer: scan with a read pointer, and copy kept elements to the front using a separate, slower write index. Moving all zeros to the end:
// move zeros to the end, keep order, in place — O(n), O(1)
void moveZeroes(int[] a) {
int write = 0;
for (int read = 0; read < a.length; read++)
if (a[read] != 0) a[write++] = a[read]; // pack non-zeros to the front
while (write < a.length) a[write++] = 0; // fill the rest with zeros
}In place still costs time - and can corrupt data if careless
"In place" bounds space, not time - rotate is still O(n) time. And swapping within an array is
easy to get wrong: overwrite a value before you've read it and you lose data. Two-pointer and
write-pointer templates work precisely because they never overwrite an element they still need.
You're told to reorder a shelf of books but you have no table or spare shelf to stage them on - only the shelf itself. So you swap pairs directly: take two books, exchange their slots, repeat. It's slower to reason about than laying them all out, but it uses no extra space. In-place array work is exactly that discipline: every rearrangement happens by swapping within the one array you were given.
Rotate an array right by k positions using O(1) extra space. Explain the three-reversal trick and why it produces the rotation, and why you take k modulo n first.
How do you rotate an array right by k in place with O(1) extra space?
Key takeaways
- 'In place, O(1) space' means rearrange by swapping within the array - no new array.
- Reversing a range with two pointers is the fundamental in-place building block.
- Rotate an array in place with three reversals: whole, first k, then the rest (take k mod n first).
- A write pointer packs kept elements to the front for remove/move problems in one pass.
- In place bounds space, not time; use templates that never overwrite an element you still need.