A picker belt records SKU ids in the slots they arrived in. 0 means an empty slot that must slide to the end so live ids keep their relative order before the packer reads the line. The intern collected every non-zero into a new list and padded zeros. A short belt was fine. The board then forbade the extra list: same array, live order preserved, zeros only in the tail.

Move Zeroes asks you to push every 0 to the end, live order kept. An array already gives nums[i] for free. Copying live values into a second buffer uses that and still allocates n. Swapping a zero with whatever non-zero you see next can scramble the order the packer needs.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here one index scans, and a second index is only a write head: the next slot a live value should occupy.

The problem

Given an int[] nums, move every 0 to the end while keeping the relative order of every non-zero. Mutate nums. Do not allocate a second array of n.

[0, 4, 0, 2, 9]  →  [4, 2, 9, 0, 0]
[0]              →  [0]
[8, 0, 8]        →  [8, 8, 0]

Note: Stability of non-zeros is required. Equal live values keep their arrival order. Zeros may trade places with each other; nobody asked you to preserve empty slots. Values other than 0 are all “live” — do not special-case signs or duplicates.

Extra list of the live values

Walk once, copy every non-zero into a new array, then copy that array back (the leftover tail is already 0). Correct. Linear. You paid O(n) extra slots for a question the original array can answer with a write index.

void moveZeroesExtra(int[] nums) {
    int n = nums.length;
    int[] tmp = new int[n];
    int w = 0;
    for (int x : nums) {
        if (x != 0) {
            tmp[w++] = x;
        }
    }
    System.arraycopy(tmp, 0, nums, 0, n);
}

At n = 20 this is a rounding error. The complaint is the extra buffer. A write head in nums already answers: where does the next live value land?

Write head: compact, then paint

w is the next slot a non-zero should occupy. Scan left to right. Each live value is written at w, then w advances. Zeros are skipped. When the scan ends, every live value sits in 0 .. w-1 in original order. The leftover tail still holds stale copies; overwrite it with 0.

[0, 4, 0, 2, 9]   w=0

0  skip                         [0, 4, 0, 2, 9]
4  write at w, w=1              [4, 4, 0, 2, 9]
0  skip                         [4, 4, 0, 2, 9]
2  write at w, w=2              [4, 2, 0, 2, 9]
9  write at w, w=3              [4, 2, 9, 2, 9]
fill zeros from w               [4, 2, 9, 0, 0]

The Java is that walk:

void moveZeroes(int[] nums) {
    int w = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[w++] = nums[i];
        }
    }
    while (w < nums.length) {
        nums[w++] = 0;
    }
}

Time is O(n) — one scan to compact, one fill of the tail. Extra space is O(1) — the write index. The extra list is the same time bill and the space they rejected; say so, then compact in place.

Note: Paint the stale tail. [4, 2, 9, 2, 9] is not the answer. Paint from w. A swap of the first zero with the last non-zero ([9, 4, 0, 2, 0]) is also wrong: it moved zeros and reordered live ids.

What interviewers usually poke next

  • Swap instead of two fills. if (nums[i] != 0) swap(w++, i) is one pass and still stable: nums[w] is a zero once w < i. Name it if they want fewer writes; the compact-then-paint is easier to defend.
  • Order of zeros does not matter, order of live values does not matter. Then it is a two-value partition, not this prompt. Do not start a Sort Colors lecture unless they drop the stability requirement.
  • Move zeros to the front. Write head from the right, or compact the zeros left and paint the live tail. Same idea, flipped.
  • All zeros, or none. w stays 0 and the fill rewrites the whole array, or w reaches n and the fill is a no-op.

You are done with this problem when you can walk [0, 4, 0, 2, 9] with a write head on a whiteboard, and you can say out loud why the extra list is honest extra space, why a blind swap scrambles order, and why the tail still needs to be painted.