Same-Direction Pointers

The second flavor of two pointers. Both read and write walk forward through the array, but at different speeds: read visits every element, write advances only when something “passes” a filter.

The pattern shows up whenever you’d be tempted to write:

# tempting but wasteful
output = []
for x in arr:
    if passes_filter(x):
        output.append(x)
arr[:] = output

That’s O(n) time and O(n) extra space. Same-direction two pointers does the same thing in O(n) time and O(1) extra space — by writing the filtered output back into the same array, in place.

The template

write = 0
for read in 0 .. n - 1:
    if arr[read] passes the filter:
        arr[write] = arr[read]
        write += 1
# at the end, arr[0..write] is the filtered prefix; arr[write..n] is garbage
return write

That’s the entire pattern. The “filter” is problem-specific.

The key invariant: at every moment, arr[0..write) is the valid output we’ve built so far, and arr[read..n) is the unread portion. write <= read always — the write pointer can never lap the read pointer because it only advances on a successful filter, while read advances every step.

Worked example 1: Remove Duplicates from Sorted Array

Given a sorted array nums, remove duplicates in place such that each unique element appears once. Return the new length k; the first k elements of nums should hold the unique values.

The filter: “this element is different from the one we just wrote.”

Time: O(n). Space: O(1).

The “compare against nums[write - 1]” (the last kept value) is the key — we don’t compare against nums[read - 1] (the last read value), because consecutive duplicates would then fool us.

Worked example 2: Move Zeroes

Given an integer array nums, move all zeroes to the end while maintaining the relative order of the non-zero elements. Do it in place.

The filter: “this element is non-zero.” After the read loop finishes, fill the rest with zeroes.

Time: O(n). Space: O(1).

A subtle variant: swap instead of overwrite

If you swap instead of overwriting + back-filling, you do it in one pass with no post-loop fixup:

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[read], nums[write] = nums[write], nums[read]
            write += 1

Both are correct. Overwrite + backfill is conceptually simpler; swap is one pass and slightly fewer assignments when most elements are non-zero.

Worked example 3: Partition (the quicksort step)

Given an array and a pivot value p, partition the array so that elements < p come before elements >= p.

The filter: “this element is less than the pivot.” Swap into the write position to avoid losing the element at write.

This is the Lomuto partition — the simple variant used as the core step of quicksort. The Hoare partition is a different two-pointer pattern (opposite-ends, swap when both are misplaced). Both are correct; Lomuto is easier to write.

Worked example 4: Dutch National Flag

Given an array containing only 0s, 1s, and 2s, sort them in place in one pass.

The 0s and 2s want to be at the ends; the 1s sit in the middle. Three pointers instead of two:

l — write head for 0s.
m — read cursor.
r — write tail for 2s.

Invariants:

nums[0..l) are all 0.
nums[l..m) are all 1.
nums[m..r] are unknown.
nums[r+1..n) are all 2.

Time: O(n). Space: O(1).

⚠️

The tricky line: do NOT advance m after swapping with r. The value we just swapped in could be a 0 or a 1 or a 2 — we haven’t classified it yet. Advancing m would skip it. Contrast with the 0-swap branch, where we know the value at l was a 1 (already classified) so advancing m is safe.

Worked example 5: Remove Element

Given an array nums and a value val, remove all instances of val in place. Return the new length.

The filter: “this element is not val.”

Time: O(n). Space: O(1). The cleanest example of the template.

A summary table

Problem	Filter (`read` keeps if…)	Notes
Remove Duplicates Sorted	`nums[read] != nums[write - 1]`	Compare against last kept value
Remove Element	`nums[read] != val`	Cleanest template
Move Zeroes	`nums[read] != 0`	Backfill or swap
Lomuto Partition	`nums[read] < pivot`	Swap (don’t overwrite)
Dutch National Flag	three-way: 0 / 1 / 2	Three pointers, careful `m` advance
Squares of Sorted Array	two-pointer merge from both ends	Different pattern — see practice

Quick check

In Remove Duplicates from Sorted Array, we compare nums[read] against nums[write - 1], not nums[read - 1]. Why?

In Dutch National Flag, why don't we advance m after swapping nums[m] with nums[r]?

The same-direction template uses O(1) extra space. The 'append to a new list' alternative uses O(n) extra space. Why is the in-place version preferred?

Next: fast and slow pointers — Floyd’s cycle detection, linked-list midpoint, and finding the duplicate without using extra space.

Opposite-Ends Pointers Fast and Slow Pointers