Why it works
- Left of write lie only the non-zero numbers met so far, in the order read met them. Each new one is put right after them, so the order cannot change.
- Between write and read lie only zeroes. So the swap always trades a zero for the number at read, and no non-zero number is lost or jumps over another.
- When read reaches the end, every non-zero number is left of write, and every cell from write onwards holds a zero.
Complexity
Time O(n): read passes the array once, and each step does at most one swap. Memory O(1): the numbers move inside the same array.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗