Push zero-quantity fills to the end

Question

A fill array contains some zero-quantity placeholders. Move every zero to the end while keeping the non-zero quantities in their original relative order. Do it in place.

qtys = [0, 3, 0, 5, 2]
-> [3, 5, 2, 0, 0]

Rearrange in place so all non-zeros keep order and zeros trail. Aim for $O(n)$ time, $O(1)$ space.

Accepted Answer

Keep a write pointer w marking where the next non-zero should go. Scan with a read pointer r; whenever qtys[r] is non-zero, swap it into position w and advance w. Every non-zero lands compactly at the front in order, and the zeros are pushed to the tail by the swaps. Tracing [0, 3, 0, 5, 2]: 3 swaps to index 0, 5 to index 1, 2 to index 2, leaving [3, 5, 2, 0, 0]. Time O(n), space O(1). Because w never runs ahead of r, each swap either moves a non-zero forward or is a no-op swap with itself; relative order of non-zeros is preserved. Edge cases: all-zero and no-zero arrays both come back correc…

Push zero-quantity fills to the end

Your answer

More Coding questions