Lesson 5 -- Two Pointers, Same Direction

~20 minutes · two pointers · Python · Day 3

Tonight's interview move is Move Zeroes: shift every zero to the end while keeping the non-zero numbers in the same order. The trap is doing lots of tiny shifts. The win is realizing you only need to know where the next useful value should be written.

The invariant

A write pointer chases a read pointer; each moves forward only, so the whole pass is O(n).

That is the whole shape. The read pointer scans every position exactly once. The write pointer marks the next slot where a non-zero value belongs. Because neither pointer ever moves backward, there is no hidden nested loop.

The shaded prefix is the part already compacted; read may be farther right, but write never jumps ahead.

Move Zeroes: the slow way first

The problem asks you to modify the array in-place without making a copy (LeetCode 283). A first idea is to bubble each zero rightward by adjacent swaps:

def move_zeroes_slow(nums):
    for _ in range(len(nums)):
        for i in range(len(nums) - 1):      # repeated full scans
            if nums[i] == 0 and nums[i + 1] != 0:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]

This is in-place, and it keeps order, but it is O(n²): every pass may only move a zero one step. If the array is long, repeated scans are the thing to avoid.

Move Zeroes: the two-pointer way

Instead, scan once. When read finds a non-zero value, swap it into the write slot, then advance write. Python's assignment statement can assign to list positions, so this swap mutates the same list rather than building a new one (Python docs: assignment statements).

def move_zeroes(nums):
    write = 0                         # next slot for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:           # read found useful data
            nums[write], nums[read] = nums[read], nums[write]
            write += 1                # next open slot moves right

Why the order stays intact: read sees non-zero values from left to right, and write places them from left to right. Zeros get swapped behind the written region as a side effect.

Transfer: same chase, new costume

Remove Duplicates from Sorted Array: keep one copy of each value in a sorted array, in-place, and return the length of the kept prefix.

Before reading the reveal: say what write means, what read scans, and when a value should be copied forward.

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

For duplicates, read asks "is this new?" and write extends the kept prefix only when the answer is yes.

What the trade buys you

The key is not the variable names. The key is the promise: both pointers only move forward.

Practice -- answer before you scroll past

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

Your move (tonight)

Solve Move Zeroes in your Notion tracker using predict → attempt → compare → encode:

1. Predict: state the brute force, the two-pointer invariant, and the complexity out loud.
2. Attempt: code it from a blank editor before reading any solution.
3. Compare: find the exact line where your reasoning differs from the source below.
4. Encode: write the invariant in your own words in the Notes column.

Stuck or curious? Ask your teacher (the agent) -- that's what it's for.