Read & write pointers (in-place)
In one line
One pointer reads every element while a second marks where the next kept element goes, so you filter or compact an array in place in a single O(n) pass.
What it is
Both pointers move left to right. The read pointer visits every element once. The write pointer only moves when an element is kept, so everything before it is the finished output. Because write never gets ahead of read, you never overwrite something you still need to read.
This is how you remove an element, drop duplicates from a sorted array, move zeros to the end or compress characters without a second array. The function usually returns the new logical length, and anything after it is ignored.
Why interviewers ask
These are some of the most common warm-up questions, and they test whether you can keep a clear invariant ('nums[:write] is the answer so far') instead of deleting inside a loop, which is O(n^2). Interviewers also check edge cases: empty arrays, all elements kept, none kept, and whether relative order must be preserved.
How it works
- 1Set write = 0 (or 1 if the first element is always kept, as in removing duplicates from a sorted array).
- 2For read from left to right: decide whether nums[read] belongs in the output.
- 3If it does, copy it to nums[write] (or swap, if the dropped values must be kept at the end) and increase write.
- 4Invariant: after each step, nums[:write] holds exactly the kept elements seen so far, in their original order.
- 5At the end, return write as the new length. Each element is read once and written at most once: O(n) time, O(1) extra space.
- 6Variant 'allow at most k copies' in a sorted array: keep nums[read] if write < k or nums[read] != nums[write - k].
Worked example · Remove duplicates from sorted [1, 1, 2, 3, 3]
- nums[0] = 1 is always kept, so write = 1. Kept part: [1].
- read = 1: nums[1] = 1 equals the last kept nums[0] = 1. Skip. write stays 1.
- read = 2: nums[2] = 2 differs from 1. Copy to nums[1]; array [1, 2, 2, 3, 3], write = 2.
- read = 3: nums[3] = 3 differs from nums[1] = 2. Copy to nums[2]; array [1, 2, 3, 3, 3], write = 3.
- read = 4: nums[4] = 3 equals nums[2] = 3. Skip.
- Return 3. The first 3 slots are [1, 2, 3]; the leftover 3s after index 2 do not matter.
Picture it
Sorting returned library books on a cart: you pick up each book in turn (read), and only the ones that stay go back onto the shelf in the next free spot (write). Damaged books are skipped, the shelf fills from the left, and you never need a second cart.
Reference code
def remove_duplicates(nums):
# nums is sorted; keep one copy of each value, return new length
if not nums:
return 0
write = 1 # nums[:write] is the kept part
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
def move_zeroes(nums):
# keep non-zero order, push zeros to the end
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
remove_duplicates keeps nums[read] only when it differs from the last kept value nums[write - 1], so nums[:write] is always the deduplicated prefix. move_zeroes swaps each non-zero value into the write slot, which keeps non-zero order and pushes zeros to the back. Both are O(n) time and O(1) extra space.
Key patterns
Filter in place
When: Remove all occurrences of a value, or keep elements meeting a condition
How: Copy each kept element to nums[write], write += 1; return write.
Dedupe sorted data
When: Sorted array or stream with repeated values
How: Keep nums[read] if it differs from nums[write - 1]. For 'at most k copies', compare with nums[write - k].
Stable partition by swapping
When: Move zeros to the end keeping non-zero order
How: Swap nums[read] with nums[write] when nums[read] is non-zero, then write += 1.
Run-length compression
When: Compress ['a','a','b','c','c','c'] to ['a','2','b','c','3'] in place
How: read scans a run, then write the character and its count digits at write; the output is never longer than the input.
Real-world use
C++ erase-remove idiom
std::remove and std::remove_if do exactly this: they shift kept elements forward with a write position and return the new logical end, and vector::erase then trims the tail.
Unix uniq
The uniq command drops repeated adjacent lines by comparing each line with the last one it kept, the same rule as removing duplicates from a sorted array, which is why it is usually run after sort.
Compacting garbage collectors
Sliding mark-compact collectors, such as the old-generation collectors in HotSpot's Serial and Parallel GCs, move live objects toward the start of the heap in address order and leave the free space as one block: a read pointer scans objects, a write pointer marks where the next live object goes.
Filtering in data pipelines
Numeric libraries filter arrays by computing which items to keep and packing them toward the front; NumPy's boolean masking and pandas filtering produce the same result as a read/write pass (into a new array).
In a project
A telemetry agent on IoT devices buffers 10,000 readings in a fixed array, and before upload it must drop invalid readings (sensor errors encoded as -1) and consecutive duplicates, without allocating another buffer.
- Use one pass with read and write pointers over the buffer.
- Keep a reading if it is not -1 and differs from the last kept reading (nums[write - 1]).
- Copy kept readings to nums[write] and advance write; upload only nums[:write].
- Unit-test edge cases: empty buffer, all invalid, all identical, no duplicates.
Impact: Upload size drops by the fraction of noise and repeats (often well over half for slow-changing sensors), saving cellular data costs and battery, with no extra memory on the device.
Trade-offs
Use it when
- You must filter, dedupe or compact an array in O(1) extra space
- The relative order of kept items must stay the same
- The caller can accept a new length instead of a shorter array
Avoid it when
- You can simply return a new list and memory is not a concern (a list comprehension is clearer)
- The input must not be modified
- Duplicates are not adjacent (unsorted data): sort first or use a hash set
Cost: O(n) time, O(1) extra space; each element is read once and written at most once.
Common mistakes
- Deleting elements inside a for-loop over the same list (list.remove or del), which skips elements and costs O(n^2).
- Comparing nums[read] with nums[read - 1] instead of the last kept value nums[write - 1]; they differ in the 'at most k copies' variants.
- Returning the array instead of the new length, or forgetting that elements after write are leftovers.
- Not handling an empty array when write starts at 1.
- Using a swap when a copy is enough (or vice versa) without checking what the problem says about the tail.
Interview questions
Quick revision
- read visits everything; write marks the next output slot.
- Invariant: nums[:write] is the finished output.
- write never passes read, so no unread data is overwritten.
- Dedupe sorted: keep if nums[read] != nums[write - 1].
- At most k copies: compare with nums[write - k].
- Move zeros: swap non-zeros forward.
- Return write (the new length). O(n) time, O(1) space.
Check yourself
1. After running remove_duplicates on [0, 0, 1, 1, 1, 2], what is returned?
2. What invariant does the write pointer maintain?
3. To allow at most two copies of each value in a sorted array, a new value nums[read] is kept when...
4. What is the time complexity of deleting each unwanted element with list.remove inside a loop?
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.