Read and Write Pointers: Remove Duplicates and Move Zeros
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some tasks change a list as you read it: remove cancelled orders, drop duplicates, push zeros to the back. Two pointers that move in the same direction do it in one pass without a second list.
Read and write pointers
Read and write pointers are two indexes that move in the same direction. Read looks at every item and write marks where the next kept item goes, so a list is filtered in place with O(1) extra space.
Orders are marked -1 when cancelled. Remove them without making a second list. A read pointer visits every item. A write pointer marks where the next kept item goes.
orders = [120, -1, 40, -1, 75]write = 0for read in range(len(orders)): if orders[read] != -1: orders[write] = orders[read] write += 1print(orders[:write])Example 1 · Filter with a comprehension
orders = [120, -1, 40, -1, 75]kept = [amount for amount in orders if amount != -1]print(kept)print(orders)[120, 40, 75] [120, -1, 40, -1, 75]
What this code does
- This is the Python way when a new list is fine, but it uses O(n) extra space.
- The original list is untouched. The pointer version changes the list itself.
The write pointer never gets ahead of the read pointer, so no unread value is overwritten. Everything before write is the answer.
Remove duplicates from a sorted list
In a sorted list, equal values sit side by side. A value is new when it differs from the last value kept, which is at write - 1. Copy new values forward.
def remove_duplicates(nums): if not nums: return 0 write = 1 for read in range(1, len(nums)): if nums[read] != nums[write - 1]: nums[write] = nums[read] write += 1 return write
marks = [1, 1, 2, 2, 2, 3, 4, 4]count = remove_duplicates(marks)print(count, marks[:count])Example 2 · Watch read and write
nums = [1, 1, 2, 2, 3]write = 1for read in range(1, len(nums)): if nums[read] != nums[write - 1]: nums[write] = nums[read] write += 1 print(read, write, nums)1 1 [1, 1, 2, 2, 3] 2 2 [1, 2, 2, 2, 3] 3 2 [1, 2, 2, 2, 3] 4 3 [1, 2, 3, 2, 3]
What this code does
- Printing after each step shows the first cells settling on the answer.
- Cells after
writekeep stale values, so onlynums[:write]is meaningful.
The first item is always kept, so write starts at 1. The function returns how many values to keep. Time is O(n), space is O(1).
Move zeros to the end
Stock counts have zeros mixed in. Keep the order of the non-zero values and push the zeros to the back. Swap each non-zero value into the write position.
def move_zeros(nums): write = 0 for read in range(len(nums)): if nums[read] != 0: nums[write], nums[read] = nums[read], nums[write] write += 1
stock = [0, 1, 0, 3, 12]move_zeros(stock)print(stock)Example 3 · Move zeros with swaps
def move_zeros(nums): write = 0 for read in range(len(nums)): if nums[read] != 0: nums[write], nums[read] = nums[read], nums[write] write += 1
stock = [4, 0, 0, 7, 0, 2]move_zeros(stock)print(stock)[4, 7, 2, 0, 0, 0]
What this code does
- Each non-zero value is swapped forward to
write. - The order 4, 7, 2 is unchanged, and the zeros gather at the end.
Example 4 · Move zeros with a fill
stock = [4, 0, 0, 7, 0, 2]write = 0for read in range(len(stock)): if stock[read] != 0: stock[write] = stock[read] write += 1for i in range(write, len(stock)): stock[i] = 0print(stock)[4, 7, 2, 0, 0, 0]
What this code does
- The first loop copies non-zero values forward. The second loop fills the rest with zeros.
- It does fewer writes than swapping when there are many zeros.
Every non-zero value moves forward once and the zeros end up behind write. Order of non-zero values is kept, and it is one pass.
Python shortcuts and when to use them
A comprehension or dict.fromkeys is shorter and fine for real work. It builds a new list, so it uses O(n) space. Interviews ask for the in-place version to see if you can move pointers.
stock = [0, 1, 0, 3, 12]same_list = stockstock[:] = [x for x in stock if x != 0] + [0] * stock.count(0)print(stock, same_list is stock)print(list(dict.fromkeys([4, 1, 4, 2, 1])))Example 5 · Keep at most two copies
def keep_two(nums): write = 0 for value in nums: if write < 2 or value != nums[write - 2]: nums[write] = value write += 1 return write
data = [1, 1, 1, 2, 2, 3, 3, 3, 3]count = keep_two(data)print(count, data[:count])6 [1, 1, 2, 2, 3, 3]
What this code does
- A value is kept when fewer than two are kept, or it differs from the value two places back.
- Changing 2 to k gives the general rule for any number of allowed copies.
Slice assignment stock[:] = ... changes the same list object. Plain stock = ... would only rename a new list.
Next step
Check your understanding
11 quick questions