Move all zeros to the end in O(n) time and O(1) space.

Problem. Move all 0s to the end of an array in place while keeping the relative order of the non-zero elements, in O(n) time and O(1) space. [0,1,0,3,12] → [1,3,12,0,0].

Brute force — O(n) time, but O(n) space

Collect non-zeros, then pad with zeros:

void moveZerosExtra(int[] a) {
    int[] out = new int[a.length];
    int idx = 0;
    for (int x : a) if (x != 0) out[idx++] = x;
    System.arraycopy(out, 0, a, 0, a.length);
}

Correct and stable, but allocates a second array. The interviewer explicitly wants O(1) space.

Optimal — O(n) time, O(1) space (fast/slow two pointers)

A slow write pointer marks where the next non-zero belongs; a fast read pointer scans. When the reader finds a non-zero, swap it into the write slot and advance both. Swapping (rather than overwriting then padding) means the zeros bubble to the tail automatically, in one pass:

public void moveZeroes(int[] a) {
    int write = 0;                       // next slot for a non-zero
    for (int read = 0; read < a.length; read++) {
        if (a[read] != 0) {
            int tmp = a[write];
            a[write] = a[read];
            a[read] = tmp;
            write++;
        }
    }
}

Stability is preserved because non-zeros are placed in the exact order they're encountered. The swap is safe even when read == write (it's a no-op self-swap during the prefix with no zeros yet). Each index is visited once → O(n) time, O(1) space, and at most one swap per element.