Module 04 · Two Pointers and In-Place Read/Write State

034. Remove a Target In Place

Foundation · Download this solution · All solutions and shared helpers

Problem

Remove every occurrence of target from a mutable integer list stably. Return the number k of retained values; only nums[:k] is meaningful afterward. The physical list length and tail values are unspecified.

Examples

Example 1

a = [3, 2, 2, 3]
(remove_target(a, 3), a[:2])
=> (2, [2, 2])

Only the first two cells are meaningful.

Example 2

remove_target([], 3)
=> 0

No values survive because none exist.

Example 3

remove_target([1, 1], 1)
=> 0

Every occurrence is rejected.

Reveal the worked solution and reasoning

Why this mechanism works

A read frontier examines all original values, while a write frontier advances only for accepted ones. This is stable filtering without allocation. It is the same compaction mechanism as deduplication, but acceptance now depends on a fixed predicate rather than the last committed value.

State and boundaries

write counts accepted values. The prefix before write contains exactly the consumed non-target values in order.

Protocol

Set write to zero.
Read each value.
If it differs from target, commit it at write.
Advance write only on a commit.
Return write.

Visualization

target=3
read:  [3,2,2,3]
keep:  [2,2 | ?,?]
k=2

Python implementation

def remove_target(nums, target):
    write = 0
    for value in nums:
        if value != target:
            nums[write] = value
            write += 1
    return write

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

(remove_target(a, 3), a[:2])

L2 remove_target: write = 0
nums=[3, 2, 2, 3]; target=3; write=0

L3 remove_target: for value in nums:
nums=[3, 2, 2, 3]; target=3; write=0; value=3

L3 remove_target: for value in nums:
nums=[3, 2, 2, 3]; target=3; write=0; value=2

L5 remove_target: nums[write] = value
nums=[2, 2, 2, 3]; target=3; write=0; value=2

L6 remove_target: write += 1
nums=[2, 2, 2, 3]; target=3; write=1; value=2

L6 remove_target: write += 1
nums=[2, 2, 2, 3]; target=3; write=2; value=2

L3 remove_target: for value in nums:
nums=[2, 2, 2, 3]; target=3; write=2; value=3

Result: (2, [2, 2]). Only the first two cells are meaningful.

remove_target([], 3)

L2 remove_target: write = 0
nums=[]; target=3; write=0

Result: 0. No values survive because none exist.

Why the solution is correct

Each accepted value is written once after all previously accepted values, preserving order. Rejected values contribute nothing. Because write never overtakes reading, the unread suffix stays intact, and the final prefix is exactly the stable filter.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Deleting cells while iterating shifts unread indices. Returning len(nums) ignores the logical output boundary.

Reasoning card

State: write counts accepted values. The prefix before write contains exactly the consumed non-target values in order.

Invariant: write is the next output slot.

Decision to rehearse: Write only values that survive.

Finish: Return write

Transfer exercise

Drop the stability requirement and remove by swapping with the final unread position. Compare write counts.