Arrays & Strings · Stage 2 of 3
In-Place Read & Write Pointers
Maintain a write boundary to filter or compact in O(1) space
Foundations
In the first lesson, you scanned an array from left to right while keeping a single running value in memory. Now, what if an interviewer asks you to remove duplicates or compact elements inside the original array, without allocating a new one?
Two terms set the rules. In place means you rearrange the slots of the array you were given instead of building a second one. O(1) extra space means your extra memory stays the same size however long the input is: a few integer variables are fine, a copy of the array is not. In interview language, a pointer is one of those integer variables, holding an index into the array.
Take nums = [7, 1, 5, 3, 6] and keep only the values greater than 4. A read pointer visits every index, left to right. A write pointer marks the slot where the next kept value belongs. When nums[read] passes the test, swap it into nums[write] and move write forward. The scan ends with [7, 5, 6, 3, 1]: the kept values fill slots 0 to 2 in their original order, and write = 3 counts them.
nums
read has passed index 2: 7 and 5 fill slots 0 and 1, the dropped 1 waits at write, and 3 and 6 are unread.Case Scenario
The problem
Move Zeroes
Given an integer array nums, move all 0s to the end while keeping the relative order of the rest. Modify the array in place and return it.
- Input
- nums = [0, 1, 0, 3, 12]
- Output
- [1, 3, 12, 0, 0]
Move Zeroes is that same filter with the test nums[read] != 0: keep 1, 3, and 12 in their original order, and let the zeros collect behind write, at the back of nums. The problem also rules out a second array, so every move has to happen inside nums itself.
The instinct is to copy: collect 1, 3, and 12 into a new list, pad it with two zeros, and write the result back. That is O(n) time, but the copy grows with the input, so it breaks the O(1) space rule. Staying in place by deleting each 0 and appending it at the end avoids the copy, but every delete shifts all later values left, which is O(n²). The read and write pointers above avoid both costs: one pass, and no second array.
Approach 1 · Brute force
Copy, then write back
Build the answer in a second list, then copy it over nums. It is one pass and O(n) time, but the second list holds up to n values, which the problem rules out.
Time O(n) · Space O(n)
- 1def moveZeroes(nums):
- 2 kept = [x for x in nums if x != 0]
- 3 zeros = len(nums) - len(kept)
- 4 nums[:] = kept + [0] * zeros
Approach 2 · Read and write pointers
Walkthrough
Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.
- 1.Set
writeto 0: the slot where the next kept value belongs. - 2.Walk
readacross every index, left to right, as in the first lesson. - 3.When
nums[read]is not 0, swap it withnums[write], then movewriteforward. - 4.When
readfinishes, every zero sits behind the kept values.
Python
Move Zeroes
- Input:
- nums = [0, 1, 0, 3, 12]
- Output:
- [1, 3, 12, 0, 0]
- 1def moveZeroes(nums):
- 2 write = 0
- 3 for read in range(len(nums)):
- 4 if nums[read] != 0:
- 5 nums[write], nums[read] = nums[read], nums[write]
- 6 write += 1
nums
write marks the slot where the next nonzero value belongs. Nothing is placed yet.
The Pattern
The invariant is three zones. As read advances, slots before write hold finished, kept values in their original order; slots from write up to read hold discarded zeros; slots from read onward are unexplored. Each kept value swaps into the write slot, and since write never passes read, no swap can touch an unexplored value.
From the trace
Move Zeroes
nums
[1, 3] is finished, the two zeros sit between the pointers, and 12 is still unexplored. write cannot cross read, so unread data stays safe.Check it against the walkthrough. After read passed index 3, nums was [1, 3, 0, 0, 12]: [1, 3] finished, two zeros between the pointers, and 12 unexplored. Swapping 12 into slot 2 sent a 0 back to slot 4, the slot read was standing on, so nothing unread was lost. The finished zone grew from [1, 3] to [1, 3, 12].
The keep-or-drop test is the only part tied to zeros: it was greater than 4 for [7, 1, 5, 3, 6], and it is nums[read] != 0 here. Change that one condition, and the same two pointers can drop any value or keep one copy of each run of equal values. write always ends at the count of kept values, the length many of these problems ask you to return.
Complexity
TimeO(n)
SpaceO(1)
read visits each of the n slots once, and each visit does at most one swap, so time is O(n). The only extra memory is two indexes, so space is O(1). The copy approach is O(n) time as well. What the pointers save is the second array.
Brute force
Copy, then write back
O(n) time
O(n) space
This technique
Read and write pointers
O(n) time
O(1) space
n=100
n=10,000
n=1,000,000
Extra memory in slots, log scale. Both run in O(n) time. Only the copy grows with the input.
When to use this in an interview
- The prompt says in place, modify the input, or
O(1)extra space, and asks you to remove, filter, or compact values. - The kept elements must stay in their original relative order.
- You return a length
k, and only the firstkslots of the array are checked. - A copy-based answer is easy, and the follow-up asks you to drop the extra array.
In production
Compaction without a second buffer
Mark-compact garbage collectors and in-memory tables that purge deleted rows face this constraint. Copying live entries into a fresh buffer would briefly double memory, which is exactly when a process gets killed for running out of it. Instead, they slide live entries toward the front of the same buffer, in their original order, tracking a couple of integer offsets. The zeros in nums play the deleted rows.
Where this breaks
Forward read and write pointers work only while writes never outrun reads. When the output grows, as when duplicating each zero or merging two arrays into one buffer, write from the back instead.
Your turn
Solve it yourself
You have watched two pointers compact an array in place. Write it yourself on Move Zeroes, then change only the keep rule to solve Remove Element and Remove Duplicates from Sorted Array.
- 1Solve it
Move Zeroes
Guided · the problem you traced above
- 2Remove ElementOn your own · same pattern, no walkthrough
- 3Remove Duplicates from Sorted ArrayOn your own · same pattern, no walkthrough