In-place array tricks
In one line
Solve array problems with O(1) extra space by swapping, reversing, and using the array's own indexes and signs as storage.
What it is
An in-place algorithm transforms its input using only a constant amount of extra memory, instead of building a copy. The output overwrites the input.
A handful of tricks cover most interview questions: swapping with two indexes, reversing segments (to rotate), placing each value at the index it belongs to (cyclic sort), and using the array itself as a hash map by marking positions, for example by flipping a value's sign when the values are known to lie in 1..n.
Why interviewers ask
'Can you do it in O(1) extra space?' is one of the most common follow-ups after a hash-map solution. Interviewers want to see that you can spot the constraint that makes it possible (values in 1..n, sorted input, order not mattering) and that you handle the risks of in-place work: overwriting data you still need and modifying the caller's input.
How it works
- 1Swap: exchange two positions without extra storage beyond a temporary (in Python, a, b = b, a).
- 2Reverse a segment: swap the ends and move inward until they meet. O(length) time, O(1) space.
- 3Rotate right by k: normalise k = k % n, reverse the whole array, reverse the first k elements, then reverse the rest.
- 4Index as hash (sign marking): if values lie in 1..n, value v 'owns' index v - 1. Mark v as seen by making nums[v - 1] negative; read the original value with abs(). Afterwards, positive positions are the missing values.
- 5Cyclic sort: if values are 1..n, repeatedly swap nums[i] into index nums[i] - 1 until position i holds the right value or a duplicate. Each swap fixes one value, so it is O(n) overall.
- 6Write from the back: when merging or expanding inside the same array, fill from the end so you never overwrite values you have not read yet.
Worked example · Rotate [1, 2, 3, 4, 5, 6, 7] right by k = 3, then find missing numbers
- Target result: the last 3 elements move to the front: [5, 6, 7, 1, 2, 3, 4].
- Reverse all: [7, 6, 5, 4, 3, 2, 1].
- Reverse the first k = 3: [5, 6, 7, 4, 3, 2, 1].
- Reverse the remaining 4: [5, 6, 7, 1, 2, 3, 4]. Done, using only swaps.
- Second problem: nums = [4, 3, 2, 7, 8, 2, 3, 1], values in 1..8. Which values are missing?
- For each x, negate nums[abs(x) - 1] if it is positive. x = 4 negates index 3, x = 3 negates index 2, x = 2 negates index 1, x = 7 negates index 6, x = 8 negates index 7, the second 2 and 3 find their indexes already negative, x = 1 negates index 0.
- Result: [-4, -3, -2, -7, 8, 2, -3, -1]. Indexes 4 and 5 are still positive, so values 5 and 6 are missing. O(n) time, O(1) extra space.
Picture it
It is like rearranging books on a full shelf with no table beside you: you cannot lay them out elsewhere, so you swap pairs, flip whole sections, or use a sticky note on a book's spine (the sign flip) to remember something about it without needing a separate notebook.
Reference code
def rotate_right(nums, k):
n = len(nums)
if n == 0:
return
k %= n
def reverse(lo, hi):
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
reverse(0, n - 1) # whole array
reverse(0, k - 1) # first k
reverse(k, n - 1) # the rest
def find_missing(nums):
# values are in 1..n; mark value v as seen by negating nums[v - 1]
for x in nums:
i = abs(x) - 1
if nums[i] > 0:
nums[i] = -nums[i]
return [i + 1 for i, x in enumerate(nums) if x > 0]
rotate_right moves the last k elements to the front using three reversals, O(n) time and O(1) space; k %= n handles k larger than the array. find_missing marks each value v as seen by negating nums[v - 1], using abs() to read values that may already be negative, and returns positions still positive. Both modify the input list.
Key patterns
Reverse to rotate
When: Rotate an array or string by k positions in O(1) space
How: Three reversals: whole, first part, second part (order depends on left or right rotation).
Sign marking (array as hash set)
When: Values in 1..n; find missing or duplicate numbers in O(1) space
How: Negate nums[abs(v) - 1] to mark v; positive positions are missing, an already-negative position means a duplicate.
Cyclic sort
When: Values in 1..n (or 0..n - 1); find first missing positive, duplicates, misplaced items
How: Swap each value to index value - 1 until it is there or a duplicate blocks it; then scan for the first index i with nums[i] != i + 1.
Fill from the back
When: Merging into a buffer with spare space at the end, or expanding characters in place
How: Write pointer starts at the last slot and moves left, so writes never overwrite unread data.
Output array does not count
When: Product of array except self in O(1) extra space
How: Build prefix products in the output array, then multiply in suffix products with a single running variable.
Real-world use
Standard library sorting
C++ std::sort (introsort) and heapsort rearrange elements inside the array with swaps rather than allocating a second array, which matters when sorting gigabytes of data or running on devices with little memory.
Shuffling
Python's random.shuffle and Java's Collections.shuffle use the Fisher-Yates algorithm, which walks the array once and swaps each position with a random earlier one, producing a uniform shuffle in place in O(n).
NumPy in-place operations
Writing a += 1 or np.add(a, b, out=a) updates the existing buffer instead of allocating a new array, which avoids doubling memory use on large data such as image stacks or model weights.
Embedded and firmware code
Microcontrollers often have only tens of kilobytes of RAM, so signal-processing code (for example in-place FFTs on audio buffers) transforms data inside the same buffer it was captured into.
In a project
A firmware team's audio device keeps a 4,096-sample ring buffer and must present it as a linear array (oldest sample first) to a filter, but there is not enough RAM for a second 4,096-sample copy.
- Note that the buffer is the linear array rotated by the write index w: the oldest sample sits at index w.
- Rotate left by w in place with three reversals: reverse [0, w - 1], reverse [w, n - 1], then reverse the whole buffer.
- Run the filter directly on the rotated buffer, then continue writing new samples from index 0.
- Unit-test the rotation against a copy-based version on a desktop build for every w from 0 to n - 1.
Impact: The feature fits in the existing RAM without a hardware change, saving 8 KB (4,096 16-bit samples) per buffer, and the rotation costs a single O(n) pass per frame.
Trade-offs
Use it when
- The problem asks for O(1) extra space
- Memory is genuinely tight (embedded, huge arrays)
- Values have a known range such as 1..n that can double as indexes
Avoid it when
- The caller still needs the original input; copy it or use a hash set
- Values are arbitrary (negative, huge, or not tied to indexes), so sign marking and cyclic sort do not apply
- Clarity matters more than memory; a hash set version is easier to read and review
Cost: Reverse and rotate: O(n) time, O(1) space. Sign marking and cyclic sort: O(n) time, O(1) extra space.
Common mistakes
- Forgetting k %= n when rotating, so k larger than n breaks the reversal bounds (and n = 0 must be handled first).
- Reading nums[x - 1] instead of nums[abs(x) - 1] after earlier steps made x negative.
- Overwriting a value before it is read, for example merging from the front into the same array.
- Mutating the caller's input without saying so; mention it and offer to restore signs afterwards.
- Writing cyclic sort with a for-loop that swaps once per index instead of a while-loop that keeps swapping until position i is settled.
Interview questions
Quick revision
- In place = O(1) extra space; the input is overwritten.
- Rotate right by k: k %= n; reverse all, reverse first k, reverse rest.
- Values in 1..n? Index v - 1 can store a flag about v.
- Sign marking: negate nums[abs(v) - 1]; positive index i means i + 1 is missing.
- Cyclic sort: while nums[i] is not at nums[i] - 1, swap it there.
- Merging into the same buffer: write from the back.
- The output array usually does not count as extra space.
- Always say that the input is mutated.
Check yourself
1. Rotating [1, 2, 3, 4, 5] right by k = 2 with three reversals gives which array after the first step (reverse all)?
2. Why does sign marking use abs(x) when computing the index?
3. Which condition makes sign marking and cyclic sort possible?
4. What is the time complexity of rotating an array of length n by k using reversals?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.