Two Pointers: Read/Write & Cyclic Sort

Both pointers move in the same direction. The read pointer visits every element; the write pointer only moves when you place something you want to keep. It's the standard way to filter, deduplicate or compress an array in place with $O(1)$ extra space. Cyclic sort is a close cousin: when values belong at known indices, swap each one home.

The idea#

Everything to the left of the write pointer is the finished answer. Everything between write and read has already been looked at and is free to overwrite. That invariant (a rule that stays true at every step) is why the trick is safe: you never overwrite a value you still need to read. Three rules keep it true:

The read pointer always moves forward, one step per iteration.
The write pointer moves only when you place a valid element.
At the end, the write pointer equals the length of the kept prefix.

Read/write pointers keep values in their original order. Cyclic sort solves a different in-place problem: it uses the values themselves as addresses. If the array should hold 1..n, then value v belongs at index v - 1. For each position there are three cases:

The number is already in its right position: move on.
The number is in the wrong position: swap it to its right position, and check the same index again (a new value just arrived there).
The number is out of range (<= 0 or > n): it has no home, so leave it and move on.

Each swap puts at least one value home for good, so there are at most $n$ swaps and the whole pass is $O(n)$ . Afterward, walk from the start; the first index whose value doesn't match is the answer.

How to spot it#

Both techniques answer "do it in place" questions, so the cues overlap. Look for these:

"Do it in place" or " $O(1)$ extra space" with a filter, dedupe or compress step.
"Return the new length k, and the first k slots must hold the answer."
Values lie in 1..n (or 0..n) and the question is about missing or duplicate numbers.
Moving certain values (zeros, a target) to one end while keeping the order of the rest.

Template#

The read/write loop has one decision: keep the value or skip it.

write = 0                        # items[:write] is the finished answer
for read from 0 to n - 1:
    if keep(items[read]):        # compare with items[write - 1] to dedupe
        items[write] = items[read]   # copy from read, never from write
        write += 1
return write                     # length of the kept prefix

Cyclic sort#

Cyclic sort turns the three cases from above into code. It uses a while loop, because the index advances only when nothing moves.

i = 0
while i < n:
    v = items[i]
    if v has a home and items[home(v)] != v:
        swap items[i] and items[home(v)]   # send v home, recheck i
    else:
        i += 1                   # already home, a duplicate, or no home
for each index i:
    if items[i] is not the value that belongs there:
        report i

The items[home(v)] != v check covers both "already home" and "a duplicate is already sitting there". Without it, two equal values would swap forever.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Read from the read pointer. Once the two pointers diverge, the value at write may be stale. Always copy from read.
Off-by-one on the returned length. Decide up front whether write is "next slot to fill" (return write) or "last filled slot" (return write + 1) and stick to it.
Cyclic sort must not advance after a swap. The value that arrived at index i hasn't been placed yet.
Cyclic sort needs a duplicate guard. Swap only when the destination doesn't already hold v.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Remove Element

Keep a write pointer at the slot to fill next. Whenever the read pointer finds a value other than val, copy it to the write slot and advance write.

Hint: Remove Duplicates from Sorted Array

The input is sorted, so equal values sit together. Start write at 1 and keep nums[read] when it differs from nums[write - 1], the last value you kept.

Hint: Move Zeroes

Use the same loop, but swap instead of copy. The zeros drift to the end, and the non-zeros keep their relative order.

Hint: String Compression

The read pointer walks to the end of a run of equal characters. Then the write pointer writes the character and, if the run is longer than 1, the digits of its length. Take the character from the read side (chars[read]), because the write position may already be overwritten.

Hint: First Missing Positive

This is cyclic sort with value v at home index v - 1. Values <= 0 or > n have no home, so leave them. After the pass, the first index i with nums[i] != i + 1 gives the answer i + 1; if none, the answer is n + 1.

Hint: Find the Duplicate Number

Read the values as pointers. With values in 1..n and length n + 1, i -> nums[i] defines a linked list with a cycle, and the duplicate is the cycle's entry. Use Floyd's fast/slow pointers; see Fast/Slow & Gap Pointers.

Key takeaways#

Read/write keeps the invariant "everything left of write is the final answer".
The read pointer always moves; the write pointer moves only when you keep something.
Cyclic sort sends each value v to index v - 1, then the first mismatch is the answer.
After a cyclic-sort swap, stay on the same index; guard against swapping a duplicate onto itself.
Values in 1..n can also be read as pointers, which turns a duplicate search into cycle detection.

Core idea#

Both pointers move in the same direction. The read pointer visits every element; the write pointer moves only when you keep a value. This filters, dedupes or compresses an array in place with $O(1)$ extra space.

Key points#

Invariant: everything left of write is the final answer.
The slots between write and read are already read, so you can overwrite them.
At the end, write is the length of the kept prefix.
Move Zeroes swaps instead of copying. The non-zeros keep their order.
Cyclic sort: value v in 1..n belongs at index v - 1. Swap it home, then recheck the same index.
Out-of-range values have no home. Leave them and move on.
Values in 1..n with length n + 1 form an implicit linked list. Find the Duplicate Number uses Floyd's cycle detection.
Spot it: "in place", " $O(1)$ extra space", "return the new length k", values in 1..n.

Template#

i = 0
while i < n:
    v = items[i]
    if v has a home and items[home(v)] != v:
        swap items[i] and items[home(v)]   # send v home, recheck i
    else:
        i += 1                   # already home, a duplicate, or no home
first index whose value does not belong there is the answer

The read/write shape: if items[read] is kept, copy it to items[write] and add 1 to write.

Pitfalls#

Copying from write. Its value may be stale. Always copy from read.
Off-by-one on the length. Decide if write is the next slot or the last filled slot.
Advancing after a cyclic-sort swap. The new value at i is not placed yet.
No duplicate guard. Without nums[v - 1] != v, two equal values swap forever.

Say it in an interview#

"Everything left of the write pointer is the answer, so the loop never overwrites a value I still need."
"Cyclic sort sends each value to index v minus one; the first mismatch is the answer."