Arrays: Practice Problems III

A correct result preserves order as well as moving every zero

For [0, 5, 0, 2, 8, 0], the transformation has two requirements. Indices 0-2 must contain 5, 2, and 8 in that order, and indices 3-5 must contain zeros. The result is therefore [5, 2, 8, 0, 0, 0]. Moving every zero to the end is not enough if the nonzero values change order.

A tempting approach swaps each zero with the rightmost nonzero value. For example, the zero at index 0 could be swapped with 8 at index 4, giving [8, 5, 0, 2, 0, 0]. Swapping the remaining zero with 2 can produce [8, 5, 2, 0, 0, 0]. All zeros are at the end, but the nonzero values now appear as 8, 5, 2 instead of 5, 2, 8. This violates the order requirement.

One write index can collect every nonzero value in order

Use a read index to inspect every position from left to right, and a write index to mark the next position where a nonzero value belongs. Start write at 0. When read finds 5, 2, or 8, copy that value to array[write], then increase write. When read finds zero, do nothing to write. The nonzero values are copied in the same order in which the scan encounters them.

int[] array = {0, 5, 0, 2, 8, 0};
int write = 0;

for (int read = 0; read < array.length; read++) {
    if (array[read] != 0) {
        array[write] = array[read];
        write++;
    }
}

The first pass does not try to finish the whole array. It builds a prefix containing the ordered nonzero values. After the scan of [0, 5, 0, 2, 8, 0], that prefix is [5, 2, 8], and write is 3. The positions from write to the end still need to be filled with zeros.

Temporary duplicates do not damage unread values

During the scan, a copy can leave the same nonzero value in two positions for a while. After copying 5, the array is [5, 5, 0, 2, 8, 0]. After copying 2, it is [5, 2, 0, 2, 8, 0]. After copying 8, it is [5, 2, 8, 2, 8, 0]. These duplicates are temporary. The later zero-filling pass removes the values left in the unfinished suffix.

The safety rule is write <= read. The write index starts at 0, and it advances only when the current read position contains a nonzero value. Therefore, every assignment is made at the current read position or somewhere to its left. The assignment never changes a position that the left-to-right scan has not examined yet, so unread values remain available.

array[write] = array[read];
write++;

Filling from write to the end completes the transformation

After the scan, write equals 3, and indices 0-2 already contain the ordered nonzero values 5, 2, and 8. A second loop assigns zero to indices 3, 4, and 5. This replaces the temporary suffix values and produces [5, 2, 8, 0, 0, 0].

for (int i = write; i < array.length; i++) {
    array[i] = 0;
}

The read pass examines each of the 6 positions once, and the zero-filling pass visits each position from 3 through 5. Together they take linear time, written as O(n), because the amount of work grows in proportion to the array length. The method uses only read, write, and the loop variables besides the existing array, so its extra storage is constant, O(1).