L04 · Arrays & Strings — In-Place Discipline

Series: LeetCode — From Basics to Interview-Ready · Session 4 / 65 · Phase 0 · Foundations

What this pattern IS — writing over yourself as you read

Many array problems ask you to keep some elements and drop others, then report the new length — remove duplicates, move zeros, remove a value. The naive instinct is to build a fresh list and copy the survivors:

def remove_val_naive(nums, val):
    result = [x for x in nums if x != val]   # O(n) extra memory
    return result

That works, but interviewers often add "do it in place, O(1) extra space." You cannot allocate a second array. You also cannot delete elements from the middle cheaply — list.pop(i) shifts everything after it, turning the loop into O(n^2).

The pattern that solves this cleanly: two indices walking the same array. A read pointer scans every element. A write pointer marks where the next kept element goes. When the reader finds a keeper, you copy it to the writer's slot and advance the writer. Everything before the write pointer is the finished, compacted answer.

Why not just delete in place?

# ANTI-PATTERN: deleting while iterating
i = 0
while i < len(nums):
    if nums[i] == val:
        nums.pop(i)          # O(n) shift EACH time -> O(n^2) total, and index bugs
    else:
        i += 1

pop(i) shifts every later element left by one — O(n) per removal, O(n^2) overall, and mutating length mid-loop is a classic off-by-one trap. The read/write skeleton avoids both: no deletions, no shifts, one clean pass.

The templates — annotated

Variant A — keep elements that pass a test

def compact(nums, keep):
    write = 0                        # next slot for a KEPT element
    for read in range(len(nums)):    # reader visits every index
        if keep(nums[read]):         # is this element a survivor?
            nums[write] = nums[read]  # place it at the writer
            write += 1               # advance the writer only for keepers
    return write                     # length of the compacted prefix nums[:write]

remove_element(nums, val) is keep = lambda x: x != val. move_zeroes keeps non-zeros then fills the tail with zeros. The whole family is one skeleton with a different keep.

Variant B — dedupe a SORTED array (compare to the last kept)

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1                        # first element is always kept
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # different from the last kept element?
            nums[write] = nums[read]        # keep it
            write += 1
    return write

Because the array is sorted, duplicates are adjacent, so comparing to nums[write-1] (the last thing we kept) is enough to skip runs.

Variant C — reverse / swap from both ends (foreshadows L07)

def reverse_in_place(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]  # swap ends, no temp
        left += 1
        right -= 1

Memory technique — "the writer only earns a step"

The one rule people forget is when to advance the write pointer. Peg it as a payday: the writer only earns a step when it is handed a keeper. The reader works every tick (it is in the for), but the writer is paid on results. If you keep this image, you will never advance write inside the wrong branch — the single most common bug in this pattern.

Reinforce it with the shape of the code: the skeleton is always for read: if keep: nums[write]=nums[read]; write += 1. Picture those two lines as a locked block that always move together. If you see write += 1 outside a keep branch, the bell rings.

What interviewers actually ask

In-place compaction is the warm-up round — the interviewer is checking your index discipline before the real question. These are the classics:

• Remove Duplicates from Sorted Array (26) · Microsoft, Facebook/Meta (Easy) — probes: compare-to-last-kept write pointer, return new length. Follow-up: allow each value at most twice (80) → compare to nums[write-2].
• Remove Element (27) · Amazon (Easy) — probes: keep-if-not-equal write pointer. Follow-up: "order does not matter — can you do fewer writes?" (swap from the end).
• Move Zeroes (283) · Amazon, Meta, Bloomberg (Easy) — probes: keep non-zeros with the writer, then fill the tail. Follow-up: "minimise total operations."
• Merge Sorted Array (88) · Microsoft, Amazon (Easy) — probes: write from the BACK to avoid overwriting unmerged values. Follow-up: "why back-to-front?"
• Reverse String (344) · Amazon, Microsoft (Easy) — probes: two-ends swap, O(1) space. Follow-up: "reverse words (151)."
• Sort Colors / Dutch National Flag (75) · Amazon, Microsoft, Meta (Medium) — probes: three pointers (low/mid/high) partitioning in one pass. Follow-up: "one pass, O(1) space — prove it terminates."

Worked example 1 — Move Zeroes

Problem in plain words: Move every 0 in nums to the end while keeping the order of the non-zero elements. Do it in place.

Brute + cost. Build a new list of the non-zeros, pad with zeros, copy back — O(n) time but O(n) extra space, and the interviewer wanted O(1).

Insight. Keep the non-zeros packed at the front with a write pointer (Variant A). Whatever slots remain after the last keeper must be zeros.

def move_zeroes(nums):
    write = 0                            # next slot for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:              # keeper?
            nums[write] = nums[read]     # pack it forward
            write += 1                   # writer earns a step
    for i in range(write, len(nums)):    # remaining slots -> zeros
        nums[i] = 0
    return nums
# Time O(n), space O(1).

Complexity. O(n) time, O(1) extra space. Two linear passes (pack, then fill) is still O(n).

Follow-up (fewer writes). Swap instead of overwrite, so you never touch a slot that is already correct:

def move_zeroes_swap(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]  # swap keeper into place
            write += 1
    return nums

def keep_above(nums, threshold):
    write = 0
    for read in range(len(nums)):
        if nums[read] > threshold:       # your keep-test here
            nums[write] = nums[read]
            write += 1
    return write
 
print(keep_above([1, 5, 2, 8, 3], 3))    # expect 2  (5 and 8 kept)

Worked example 2 — Remove Duplicates from Sorted Array

Problem in plain words: Given a sorted array, remove duplicates in place so each value appears once; return the new length.

Brute + cost. Convert to a set and back — loses O(1) space and the sorted order guarantee, and set iteration order is not the ask.

Insight. Sorted → duplicates are adjacent → compare each element to the last kept one (Variant B).

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1                            # nums[0] is always kept
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:  # new value, not a repeat of last kept
            nums[write] = nums[read]
            write += 1
    return write
# nums[:write] holds the unique values in order.  Time O(n), space O(1).

Complexity. O(n) time, O(1) space, single pass.

Follow-up (at most twice, problem 80). Allow each value to appear up to two times by comparing to the element two slots back:

def remove_duplicates_ii(nums):
    write = 0
    for x in nums:
        if write < 2 or x != nums[write - 2]:  # fewer than 2 kept, or x differs from 2-back
            nums[write] = x
            write += 1
    return write

That write - 2 generalises to "at most k copies" with write - k.

Worked example 3 — Sort Colors (Dutch National Flag)

Problem in plain words: Sort an array of 0s, 1s, and 2s in place in one pass.

Brute + cost. Count each color and overwrite (two passes), or sort O(n log n). The interviewer wants one pass, O(1) space.

Insight. Three pointers: low (boundary of the 0s), high (boundary of the 2s), mid scanning. Swap 0s down to low, 2s up to high, leave 1s in the middle.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]  # send 0 to the low region
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1                                      # 1 is already in the middle
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid] # send 2 to the high region
            high -= 1                                     # do NOT advance mid: recheck swapped-in value
    return nums
# Time O(n), space O(1), single pass.

Why mid does not advance after a 2-swap: the value swapped in from high is unexamined, so you must re-inspect it. Missing this is the classic bug.

Complexity. O(n) time, O(1) space, one pass.

Follow-up. "k colors instead of 3" → counting sort in O(n + k), since the three-pointer trick is specific to three partitions.

Where this shows up in production

The read/write two-pointer compaction is the same idea behind an in-place filter over a fixed buffer — for example, removing tombstoned entries from a memory buffer without allocating a second buffer, or compacting a slab of records after deletes. Garbage collectors and log compactors use exactly this "slide the survivors down, then truncate" move to reclaim space without a second array. The interview problem is a scaled-down version of a real memory-management technique, which is why it is a durable warm-up.

Practice queue

Grind easy→hard; force yourself to satisfy the in-place / O(1) space constraint.

• Remove Element (27) — Easy · basic write pointer. (spaced-repeat anchor: +7d)
• Remove Duplicates from Sorted Array (26) — Easy · compare to last kept.
• Move Zeroes (283) — Easy · pack then fill.
• Reverse String (344) — Easy · two-ends swap.
• Merge Sorted Array (88) — Easy · write from the back.
• Remove Duplicates from Sorted Array II (80) — Medium · at-most-twice. (spaced-repeat anchor: +21d)
• Sort Colors (75) — Medium · Dutch National Flag, three pointers.