In-Place Operations
Scenario
You need to reverse a massive 10GB array of image data.
Do you allocate another 10GB array to hold the reversed copy, crashing the server, or can you just shuffle the data where it already sits?
Why it exists
Problem: Creating new arrays or data structures to hold the results of an operation (like reversing or filtering) doubles the memory footprint (O(n) space). At scale, RAM is expensive and allocations are slow.
Naive approach: To reverse an array, create an empty array of the same size, loop backwards through the original, and push elements into the new array.
Better idea: Modify the input array directly. Use pointers or indices to read and overwrite values in the existing memory block. This reduces auxiliary space complexity to O(1) and eliminates allocation overhead.
Mental model
Think of the array as a row of cubbies. Instead of buying a second row of cubbies to reorganize things, you just swap items between the existing cubbies.
In-place operations mean the algorithm does its work using only a constant amount of extra memory (like a few variables for indices or a temporary swap variable). The original data structure is mutated. This requires careful tracking of what data has been processed and what data is safe to overwrite. The classic technique is using two pointers (e.g., left and right, or slow and fast) to coordinate reading and writing within the same array.
Repeated decision: Can the current element be safely overwritten without destroying unprocessed data?
Explanation
An algorithm is 'in-place' if it requires O(1) extra space. This means the memory it needs does not grow with the size of the input.
To achieve this, you must overwrite the input array. The challenge is ensuring you don't overwrite data you still need.
Consider removing all zeros from an array while keeping the order of other elements. If you use a new array, it's trivial: loop and append non-zeros. To do it in-place, you use two pointers. A 'fast' pointer scans ahead looking for non-zeros. A 'slow' pointer tracks where the next non-zero should be written. When the fast pointer finds a non-zero, you copy it to the slow pointer's position and advance both. By the end, all non-zeros are packed at the front of the array, and you can fill the rest with zeros. Because the fast pointer is always ahead of or equal to the slow pointer, you never overwrite unread data.
Another classic is reversing an array. You put a left pointer at the start and a right pointer at the end. You swap their values, then move them towards the center. This uses exactly one temporary variable for the swap, making it perfectly in-place.
In-place operations are a favorite in interviews because they test your ability to manage state and pointers without relying on the crutch of throwing more memory at the problem.
Key points
- O(1) Space: The defining characteristic. You can use a few variables (pointers, a temp for swapping), but no new arrays or hash maps.
- Destructive: In-place operations mutate the input. In real-world software, mutating inputs can cause bugs if other parts of the system expect the original data, but in algorithmic problems, it's often the goal.
- Two-Pointer Technique: The most common mechanism for in-place array manipulation. Either left/right converging, or fast/slow moving in the same direction.
Pattern: Two Pointers (In-Place)
Recognition cues:
- The problem asks for O(1) space or explicitly says 'do not allocate extra space'.
- The task involves filtering, reversing, or reordering an array.
- You need to partition an array into two categories (e.g., evens and odds).
Failure signals
- You are initializing `res = []` or `new_arr = []`.
- You are using a hash map or set to keep track of elements.
- You are using recursion (the call stack uses O(n) space).
Engineering examples
Embedded Systems
Sorting sensor data on a microcontroller with 2KB of RAM.
Allocating a copy of the array would exhaust memory and crash the device. An in-place sort (like Quicksort or Heapsort) is mandatory.
Database Compaction
Removing deleted records from a page file.
In-place shifting is used to pack the live records together so the free space is contiguous.
When not to use
- Functional programming or concurrent systems: Mutating state is dangerous when multiple threads read the data. Pure functions (returning a new array) are safer.
- When the original data must be preserved: If the caller still needs the unreversed or unfiltered data for downstream logic, you must make a copy.
Common mistakes
- Overwriting data before reading it: If you copy arr[i] to arr[j] without saving arr[j] first, the original value at j is gone forever. Always use a temp variable or a simultaneous swap (like Python's a, b = b, a).
- Forgetting that strings are immutable in many languages: In Python and Java, you cannot modify a string in-place (e.g., `s[0] = 'a'`). You must convert it to a list/char array, do the in-place work, and join it back.
- Confusing O(1) extra space with O(1) time: In-place means space is O(1). The time complexity is usually still O(n) because you have to touch every element.
Glossary
- O(1) extra space
- A fixed, small amount of memory that doesn't increase even if the input gets huge.
- temporary swap variable
- A small placeholder memory spot used to safely exchange two values without losing either.
- simultaneous swap
- Exchanging two values at the exact same time so neither gets overwritten incorrectly.
Recall questions
- What is the space complexity of an in-place algorithm?
- What is the most common technique used to modify arrays in-place?
- Why might you avoid an in-place algorithm in a production codebase?
Questions & answers
Remove all instances of a specific value from an array in-place and return the new length.
Use a slow pointer and a fast pointer. The fast pointer scans every element. If it's NOT the target value, copy it to the slow pointer and increment slow.
Approach: Standard fast/slow pointer compaction.
Move all zeros to the end of an array while maintaining the relative order of the non-zero elements.
Similar to removal: use a slow pointer for the next non-zero write position. After the fast pointer finishes, fill the rest of the array from slow to the end with zeros.
Approach: Compaction followed by a fill.
Interesting facts
- Python's `list.sort()` sorts the list in-place and returns `None`, while `sorted(list)` returns a new list and leaves the original untouched. This API design explicitly signals whether mutation is happening.
Continue learning
Previous: Arrays & Memory
Next: Prefix Sums
Related: Arrays & Memory
Related: Two pointers