Rearrange an array so all zeros move to the end while the order of non-zero elements is preserved (e.g. [0,1,0,3,12] -> [1,3,12,0,0]).
Use a write pointer: scan the array, and each time you meet a non-zero element, place it at the write index and advance it. After the scan, fill the remaining positions with zeros. O(n) time, O(1) space — and stable for the non-zero order.
public static void moveZeros(int[] a) {
int w = 0;
for (int x : a) if (x != 0) a[w++] = x;
while (w < a.length) a[w++] = 0;
}function moveZeros(a) {
let w = 0;
for (const x of a) if (x !== 0) a[w++] = x;
while (w < a.length) a[w++] = 0;
return a;
}def move_zeros(a):
w = 0
for x in a:
if x != 0:
a[w] = x
w += 1
for i in range(w, len(a)):
a[i] = 0
return aStable partitioning (keep some items, push others aside, preserve order) is a reusable pattern for filtering and reordering data in place.
The interviewer stresses "preserve the relative order of non-zero elements." Does swapping zeros to the end break that?