Write a kept value then advance write
Updated
When a[i] is kept, a[w] ← a[i], then w++. The write commits the value and frees the next kept slot.
What to focus on
After the write, [0, w) includes the new value. w increased by exactly one. i has not moved yet, or moves in the same iteration after the write.
Worked examples
first keep
a = [0, 1, 0, 9], keep nonzero, i=1 w=0- a[1]=1 kept
- a[0] ← 1
- w 0→1
Result: a = [1, 1, 0, 9], w=1
second keep
a = [1, 1, 0, 9], keep nonzero, i=3 w=1- a[3]=9 kept
- a[1] ← 9
- w 1→2
Result: a = [1, 9, 0, 9], w=2
keep ≠ 1
a = [4, 1, 9, 1], keep ≠ 1, i=2 w=1- a[2]=9 kept
- a[1] ← 9
- w 1→2
Result: a = [4, 9, 9, 1], w=2
Try it
Write keepThenAdvance(a, i, w). a is an array of integers. i is the read index of a kept value. w is the write index with w ≤ i. Write a[i] to a[w], then w += 1. Print a and w after each write. Return nothing. On [0, 1, 0, 9] keep nonzeros: write at i=1 then at i=3. Repeat the keep ≠ 1 write at i=2 on [4, 1, 9, 1].
a is nonempty. a[i] is a kept value. w ≤ i.