Arrays & Strings — In-Place Discipline

Review boundary and corrected contracts

Compaction preserves the relative order of retained values in nums[:write]; the suffix is unspecified unless the task explicitly fills it. Return a logical length rather than claiming the physical list shrank. Dutch-flag input is restricted to 0, 1 and 2.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for arrays, hashing & two pointers is in the 6-month plan: S023 — theory.

Learning objective: Master the read-pointer / write-pointer skeleton: overwrite an array in place while scanning it once, maintaining a precise invariant and testing boundary cases rather than promising a correct first attempt.

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

Prerequisites: L02 (Big-O; why pop(0) and shifting are expensive) and L03 (basic Python fluency). No prior pattern needed — this IS your first pattern.

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

This returns a fresh list; it is not the same return contract as a logical-length compactor. With the additional requirement "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.

Real: Imagine tidying a bookshelf without a second shelf. You scan left to right (the reader). Each book worth keeping, you slide leftward into the next open gap (the writer). Books you discard, you just skip. When you finish scanning, everything left of your "next gap" marker is the tidy shelf.

The reader visits every index. The writer points at the next slot for a kept element. Copy keepers to nums[write], advance write. After the pass, nums[:write] is the compacted result and write is its length.

Why not just delete in place?

# Correct filtering, but quadratic worst-case shifting: a cost counterexample.
def remove_by_pop(nums, val):
    i = 0
    while i < len(nums):
        if nums[i] == val:
            nums.pop(i)  # keep i: the next element shifted into this slot
        else:
            i += 1
    return nums

This loop is logically correct: it does not advance i after deletion. However, deleting n matching front elements shifts (n-1)+(n-2)+...+1 references, giving Θ(n²) worst-case work. End pops do not have this shifting cost, and length mutation is not inherently a correctness error. Read/write compaction avoids repeated shifting for stable filtering.

Why overwriting is safe. At the start of iteration read, 0 <= write <= read; the prefix [0, write) contains exactly the retained values from the original prefix [0, read), in order. The unread suffix [read, n) is intact. A rejected value changes only the reader’s next position. For a kept value, copying index read into write touches only an already-consumed slot or the current slot; then write increments. At the end of that iteration, write <= read+1, not necessarily write <= read. The next iteration restores the loop-entry relation. At termination, the prefix holds all survivors, and write is its logical length.

This assumes the predicate does not mutate the list or depend on already-overwritten list slots. For constant-cost predicates and bounded-cost elements, the pass is O(n) time and O(1) auxiliary space. Writing nums[:write] in an explanation denotes the valid region; actually evaluating that Python slice creates a new list. The algorithms return the index so a caller need not make that copy.

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)

Here s must be a mutable sequence such as a list of characters, not an immutable Python string. The function mutates it and returns None.

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

Reversal uses the same no-extra-array discipline, but it does not have a reader handing keepers to a writer: each swap finishes two end positions. For the keep/drop problems in Variants A and B, return to the different boundary that matters — the finished prefix grows only when an element is kept. The picture below describes that compaction invariant, not the reversal loop.

Name: Reader scouts, writer builds

Picture: Two fingers on one array. The reader finger sweeps left to right touching everything. The writer finger sits at the boundary of the finished part and only steps forward when the reader hands it a keeper. Left of the writer = done and compacted; from the reader onward = untouched.

• write starts at 0 (or 1 when the first element is always kept).

• Advance write ONLY when you keep an element.

• Copy nums[read] -> nums[write], never delete/pop.

• The answer length is the final write value; the answer is nums[:write].

Trigger: Prompt says 'in place', 'O(1) extra space', 'return the new length', or 'modify the array' for keep/drop/compact tasks.

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. The image helps remember the branch, but tests on empty input, all-kept and all-rejected inputs still matter.

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.

Misconception: in-place filtering must repeatedly delete matching elements. When the contract asks for a valid prefix and its length, overwriting is sufficient; the unspecified suffix and physical list length can remain unchanged. If the caller requires an actually shorter list, truncating after compaction is a separate operation with its own resizing/reference-release costs. Do not count that as part of a proven constant-workspace implementation without checking it.

Check: for original [3, 1, 3, 2] and a predicate keeping values other than 3, the valid prefix must be [1, 2] and length 2; the last two physical slots are unspecified. A test that demands one particular suffix would test a promise this contract never made.

What reviewers actually ask

These practice selections exercise different mutation contracts; they are not employer-frequency claims or a measured interview rubric:

• Remove Duplicates from Sorted Array (26) · Practice selection. (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) · Practice selection. (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) · Practice selection. (Easy) — probes: keep non-zeros with the writer, then fill the tail. Follow-up: "minimise total operations."
• Merge Sorted Array (88) · Practice selection. (Easy) — probes: write from the BACK to avoid overwriting unmerged values. Follow-up: "why back-to-front?"
• Reverse String (344) · Practice selection. (Easy) — probes: two-ends swap, O(1) space. Follow-up: "reverse words (151)."
• Sort Colors / Dutch National Flag (75) · Practice selection. (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 a reviewer 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 (skip self-writes). Swapping can leave zeros behind without a tail-fill pass. Skip write == read to avoid self-swaps. It is not universally fewer writes: each genuine swap assigns two slots, whereas the pack-and-fill version assigns exactly n slots.

def move_zeroes_swap(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            if write != read:
                nums[write], nums[read] = nums[read], nums[write]  # two slot writes
            write += 1
    return nums

Goal: Adapt the write-pointer skeleton.

Hint: Keep only elements STRICTLY greater than a threshold, in place; return the new length.

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)

Now change it to keep elements greater than the threshold and even. Only the if changes — the skeleton is fixed.

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

For sorted input and integer k >= 1, use write < k or x != nums[write-k]. When k == 0, return logical length 0 immediately; blindly substituting zero compares the current element with itself and is not a valid generalization. Negative limits are outside the contract.

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). A reviewer 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.

Invariant and termination: [0, low) contains only zeros; [low, mid) only ones; [mid, high] is unclassified; (high, n) only twos. With a zero, swapping into low brings either the same zero or a known one to mid, so both lower boundaries advance. A one advances mid. A two goes to high; the swapped-in value is unknown, so only high decreases. Every branch reduces the unclassified length high-mid+1 by exactly one, proving termination after n iterations. This relies on every value being 0, 1 or 2; the else branch is not validation for arbitrary input.

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

Follow-up. For integer colors in [0, k), counting then overwriting gives O(n+k) time and O(k) auxiliary counts. If k grows with the input, this is not an O(1)-space extension of the three-pointer method.

Decision: In-place write-pointer vs building a new array.

Name: In-place write pointer

Gain: O(1) extra space; exactly what 'in place' design review constraints demand.

Cost: Mutates the caller's array; slightly more index care.

Pick: When O(1) space is required, or the input may be reused/modified by design.

Name: Build a fresh list (comprehension)

Gain: Simplest to write and read; no mutation surprises.

Cost: O(n) extra memory; disallowed by 'in place' constraints.

Pick: When memory is ample and clarity beats space, or you must not mutate the input.

Name: Delete in place with pop/del

Gain: Feels direct.

Cost: O(n^2) from shifting; index bugs from changing length mid-loop.

Pick: A few deletions with actual shrinking required, or end pops where no suffix shifts; repeated arbitrary deletions remain a poor stable-compaction strategy.

Verdict: Use stable read/write compaction when a valid prefix suffices and mutation is allowed. Build a fresh list when preservation or clarity justifies its memory cost. Analyze the position and total movement of deletions rather than banning every pop loop.

Where this shows up in production

A fixed-buffer filter is a useful systems analogy: scan records, copy retained ones toward the front, then expose a smaller logical region. Real garbage collectors additionally handle object reachability, pointer relocation, metadata and sometimes concurrency; log compaction adds persistence and key/version semantics. This array exercise demonstrates stable filtering, not a complete implementation or complexity proof for those systems.

You can now…

• Recognise 'in place / O(1) space / return new length' as the write-pointer signal.

• Write the read/write skeleton and advance the writer only on keepers.

• Dedupe a sorted array by comparing to the last kept element.

• Generalise to 'at most k copies' with the write - k comparison.

• Explain the write <= read invariant that makes overwriting safe.

• Partition in one pass with three pointers (Dutch National Flag).

• Avoid the pop-in-a-loop O(n^2) anti-pattern.

Self-check (answer follows each question).

Recall check

Q: In the write-pointer skeleton, when exactly do you advance the write pointer?

A: Only when you keep an element (place nums[read] at nums[write], then write += 1). The reader advances every iteration; the writer earns a step only on keepers.

Q: Why is deleting elements with pop() inside the loop a bad idea?

A: Repeated front or middle deletions can shift Θ(n²) references. A carefully controlled while loop can remain logically correct; end pops are different because there is no suffix to shift. State which operation and loop are being analyzed.

Q: For Remove Duplicates from a sorted array, what do you compare each element to?

A: To nums[write-1], the last kept element; sorted order makes duplicates adjacent.

Q: What is the array's answer and its length after the pass finishes?

A: The valid prefix is [0, write), of logical length write. The list has not physically shrunk. Evaluating nums[:write] to inspect it creates a copy; that inspection is not the compactor’s workspace.

Q: In Sort Colors, why do you NOT advance mid after swapping a 2 to the high side?

A: The value swapped in from high is unexamined, so mid must re-inspect it before moving on.

Q: ★ Generalise Remove Duplicates to allow each value at most twice. What single change do you make?

A: Keep x if write < 2 or x != nums[write-2]. More generally use write < k or x != nums[write-k] for sorted input and k>=1; for k=0 return zero immediately.

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.

Next session (L05) introduces hashing — trading memory for time — the move that turns a quadratic pair-scan into a single pass, and the most common first optimisation in the whole track.

Corrective source notes

• 5. Data Structures — Python 3.14.8 documentation — list.copy returns a shallow copy; nested mutable elements may remain shared. Checked 2026-10-07.
• 9. Classes — Python 3.14.8 documentation — Multiple names can refer to the same object, so mutations and copied references must be distinguished. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.