Same-Direction Pointers

Remove every duplicate from a sorted array — but you’re not allowed to allocate a second array. The instinct is “filter into a new list,” costing O(n) extra memory. Same-direction two pointers does it with zero extra space: a read cursor that visits everything and a write cursor that only advances when an element survives the filter, overwriting the input in place. One loop, O(1) space, and it’s the exact shape behind Move Zeroes, partition, and Dutch National Flag.

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.

Recall the two lines that are the read/write contract — keep the survivor, then advance the write head:

python · fill in the blanks0/2 hints

def remove_duplicates(nums):
  if not nums: return 0
  write = 1
  for read in range(1, len(nums)):
      if nums[read] != nums[write - 1]:   # differs from last KEPT value
          # ??? write the survivor and advance the write head
          # ??? write the survivor and advance the write head
  return write

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.

Predict first

Dutch flag: when nums[m] == 0 you swap it to the front (l) and advance BOTH l and m. When nums[m] == 2 you swap it to the back (r) and advance only r — NOT m. Why the asymmetry?

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?

Same-direction pointers walk a single array at two speeds tied to a write decision. The last flavor ties two speeds to geometry instead: fast and slow pointers — Floyd’s cycle detection, linked-list midpoint, and finding a duplicate without extra space.

Opposite-Ends Pointers Fast and Slow Pointers

Finished this page?