Before each iteration, [0,write) is the correct output derived from items before read. After inspecting a[read], optionally write it at a[write] and advance write.
Recognition signals
The task requests in-place removal, deduplication, or movement.
The output is a stable subsequence of the input.
One pointer consumes new data while another marks the next output slot.
The valid answer length may shrink, and trailing storage is irrelevant.
False friends
Signal
Why it is different
Contiguous window constraint
If left is a window boundary that repeatedly shrinks, use sliding-window semantics.
Arbitrary reordering allowed
Swapping with the tail may use fewer writes; stable read-write is not always necessary.
Core invariant
After processing a[0:read], a[0:write] is exactly its correct stable filtered output, with write no farther than read+1.
State, transition, and processing order
Item
Definition
State
read, write, current value, and the small summary required to decide retention.
Transition
read advances every round; when the item is retained, store it at a[write] and increment write.
Frontier / order
[0,write) is final output, [write,read) may be overwritten, and [read,n) remains unread input.
Python skeleton
def stable_filter(values, keep):
write = 0
for read, value in enumerate(values):
if keep(value):
values[write] = value
write += 1
return write # valid output is values[:write]
Correctness sketch
The empty prefix is initially correct.
Discarding leaves the correct output unchanged; retaining appends exactly the next stable item at write.
Induction through read=n gives all and only retained items in the prefix, with write as its length.
Complexity
Time
Space
Parameters
O(n)
O(1)
n is input length; each item is read once and written at most once.
Edge cases
Empty input returns zero.
When every item is kept, read and write may coincide.
When every item is removed, write stays zero.
If keep depends on the previous retained item, inspect values[write-1], not the previous read position.
Error patterns
Pattern
Why it fails / fix
Returning the whole array
The tail contains unspecified old values; only [:write] is valid.
Incrementing write unconditionally
That preserves holes for items meant to be removed.
Reading overwritten storage
Maintain write behind read and base summaries on the valid prefix.
Selection and exclusion rules
Use read-write pointers for a stable filtered subsequence.
If order may be destroyed and removals are rare, tail swaps can reduce writes.
For linked storage, translate writes into next rewiring.
Related templates
Relation
Template
Boundary
Original micro-example
Part
Detail
Result
write=3 and the valid prefix is [4,6,8].
Setup
Retain even values in [4,1,6,3,8] in place.
Trace
read scans; 4 writes at 0, 6 at 1, and 8 at 2.
Recall prompts
How do you describe [0,write) in one sentence?
Why is the tail outside the returned result?
During deduplication, should comparison use the previous read item or previous retained item?