Same Direction Read Write

When To Use

Use this when compacting, filtering, overwriting, or partitioning in-place.

Template

write = 0
 
for read = 0; read < n; read++:
    if nums[read] should stay:
        nums[write] = nums[read]
        write++

Problems

Remove Duplicates from Sorted Array

Problem: keep one copy of each value in-place.

Pattern: write only the first occurrence of each value.

Applied pseudocode:

write = 0
 
for read = 0; read < n; read++:
    if read == 0 or nums[read] != nums[read - 1]:
        nums[write] = nums[read]
        write++
 
return write

Remove Element

Problem: remove all occurrences of val in-place.

Pattern: write values that are not val.

Move Zeroes

Problem: move all zeroes to the end while preserving nonzero order.

Pattern: write nonzero values, then fill the rest with zero.

Sort Colors

Problem: sort values 0, 1, and 2 in-place.

Pattern: can be read/write counting or three-way partition.