Compact in one forward pass
Updated
i runs 0..n-1 once. Keep → write at w and w++. Drop → skip. Never walk i backward. One pass is enough.
What to focus on
At the end i=n, [0, w) is the compacted prefix, a[w..] is leftover junk. No second scan.
Worked examples
zeros
a = [0, 1, 0, 9], keep nonzero- i=0 skip
- i=1 write 1 at 0, w=1
- i=2 skip
- i=3 write 9 at 1, w=2
Result: logical [1, 9], a = [1, 9, 0, 9]
drop 1s
a = [4, 1, 9, 1], keep ≠ 1- write 4, skip 1, write 9 at 1, skip 1
- w=2
Result: logical [4, 9], a = [4, 9, 9, 1]
already compact
a = [4, 1, 9], keep all- three writes, w follows i+1
- w=3
Result: logical [4, 1, 9], one pass
Try it
Write compactForward(a, keep). a is an array of integers. keep is a function that takes one value and returns true or false. i is the read index. w is the write index. i only increases. Return the logical prefix. On [0, 1, 0, 9] keep nonzeros. On [4, 1, 9, 1] keep ≠ 1. Also keep-all on [4, 1, 9].
a is nonempty. keep is a function from a value to true or false.