Command Palette

Search for a command to run...

Hectal

Lesson 6.2 · Two Pointers

Read and Write Pointers

Filter an array in place: the read pointer visits every element, the write pointer marks where the next kept element goes.

10 min

Think of it like this

Clearing out a bookshelf from left to right: your right hand picks up each book (read). Books you keep go back on the shelf at the leftmost free spot (write). At the end, the kept books are packed together at the left, in their original order.

1.The template

write starts at 0. For each read from 0 to n − 1, if the element should be kept, copy it to a[write] and increment write. At the end, a[0..write−1] holds the kept elements in order, and write is the new length.

write never passes read, so you never overwrite an element you haven't read yet.

▶ Dry run: Removing every 3a = [3, 2, 2, 3, 4], remove 3
3
0
↑w↑r
2
1
2
2
3
3
4
4

Step 1/5a[0] = 3: skip it. Only r moves.

Remember

  • Read every element; write only the kept ones.
  • Order is preserved and the extra space is O(1).
  • The final write is the new length.

Common mistakes

  • Incrementing write for skipped elements.
  • Expecting the array beyond write to be cleaned up (it holds leftovers).