Read and Write Pointers

Concepts covered: Two-Pointer, List Modification, Iteration

The second shape starts both pointers at index 0 and sends them the same way. read visits every element, 1 per iteration, with no exceptions. write marks the next slot of the output and advances only when the element under read deserves to be kept. write never passes read, so every slot it overwrites is one read has already left behind, which is what makes the rewrite safe to do in place. This is the loop behind removing duplicates, dropping a given value and compacting the non-zero entries of a list.

The input holds 8 values in 3 repeated runs. read passes the second 1 because it equals nums[write]. It reaches the first 2, which differs, so write steps to index 1 and receives the 2. The other 2s pass. The 3 and the first 4 each move write forward once more, the last 4 is skipped, and write finishes on index 3.

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

[1, 2, 3, 4]

The function returns write + 1, which is 4. The first 4 slots read [1, 2, 3, 4], and the slots after that still hold the leftovers [2, 3, 4, 4], which the caller is told to ignore. Say that out loud, because a candidate who claims the whole list is now clean has not watched the run, and the interviewer has.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 0                       # index of the last kept element
    for read in range(1, len(nums)):
        if nums[read] != nums[write]:
            write += 1
            nums[write] = nums[read]
    return write + 1                # count of kept elements

The animation started with 8 values, so there was nothing to guard. The function needs its first 2 lines all the same: on an empty list, write + 1 reports 1 unique element in a list that holds none. The invariant to narrate is "every element from index 0 through write is unique and in its final place". It holds before the loop because a single element is unique on its own, which is why read starts at 1 rather than 0.

Move zeroes, the swap variant

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

The swap rather than a plain copy is the detail that keeps the zeroes alive. A copy pushes nums[read] to the front and leaves a stale duplicate behind it, so a second pass would have to write zeroes over the tail. The swap moves the zero sitting at write out to the read position in the same statement, and the list is finished when the loop ends. When read and write are equal the swap exchanges a slot with itself. That does no harm, and saying so tells the interviewer you saw it.

The wrong turn at this band

Reaching for a set or a dict. list(set(nums)) throws away the order the sorted input arrived in, and list(dict.fromkeys(nums)) keeps it and is correct in 1 line, but either allocates a new container of up to n entries when the question said in place. Write it and the interviewer asks for the in-place version anyway, and now you're writing the loop with 4 minutes less. Mention the 1-liner as the production shortcut after the pointer version is on the screen, in the way the slice follows the palindrome loop.

About this lesson

This section is part of the Two Pointers: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.