Read & Write Pointers

Two Pointers, lesson 2 of 3

Read & Write Pointers

Filter, dedupe and partition an array in place with two pointers moving the same way.

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

The second shape has both pointers moving left to right, at different paces:

  • read visits every element, one by one
  • write marks where the next element you keep goes

Everything left of write is the finished answer. Because write never gets ahead of read, you only ever overwrite values you've already looked at.

remove every 3 from [3, 1, 3, 2, 4]

read val  action      list              write
0    3    skip        [3, 1, 3, 2, 4]   0
1    1    keep -> [0] [1, 1, 3, 2, 4]   1
2    3    skip        [1, 1, 3, 2, 4]   1
3    2    keep -> [1] [1, 2, 3, 2, 4]   2
4    4    keep -> [2] [1, 2, 4, 2, 4]   3

answer: the first 3 slots -> [1, 2, 4]
Example

Remove an element in place (with a trace)

The tail after k is leftover junk, and that's fine: in-place problems usually only look at the first k slots. Try removing 1 instead, or a value that isn't there.

Example

The classic bug

After the first remove, the second 0 slides into the slot the loop already visited, so it's never checked.

Quiz

What does this print?

The template and its common variations:

write = 0
for read in range(len(nums)):
    if keep(nums[read]):
        nums[write] = nums[read]
        write += 1
# nums[:write] is the answer
  • Swap instead of copy when the rejected values must survive, e.g. Move Zeroes: swap nums[write], nums[read] so the zeros drift to the end.
  • Dedupe a sorted array: keep nums[read] when it differs from the last kept value, nums[write - 1].
  • "At most twice": compare with nums[write - 2] instead.
Quiz

In the read/write template, which statement is always true?

Exercise

Remove duplicates from a sorted list

nums is sorted. Write remove_duplicates(nums) that rearranges it in place so the first k slots hold each distinct value once (in order), and returns k. What's after slot k doesn't matter.

For [1, 1, 2, 3, 3, 3] return 3, with the list starting [1, 2, 3, ...]. Don't build a new list.