Move Zeroes

Question (LC.283)

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example

Input: nums = [0, 1, 0, 3, 12]
Output: nums = [1, 3, 12, 0, 0]

Brute Force Approach

Scan from right to left
if detect a zero call swapToRight function - swap is an in-place operation

Brute Force Code

public int[] moveZeroes(int[] array) {
    if (array == null || array.length <= 1) {
        return array;
    }
    int size = array.length;
    for (int i = size - 1; i >= 0; i--) {
        if (array[i] == 0) {
            moveZero(array, i);
        }
    }
    return array;
}

/*
 * Swap the zero all the way to the right
 * Stop when reaches the end or reaches another 0
 */
private void moveZero(int[] array, int swapIndex) {
    int size = array.length;
    while (swapIndex + 1 < size && array[swapIndex + 1] != 0) {
        array[swapIndex] = array[swapIndex + 1];
        array[swapIndex + 1] = 0;
        swapIndex++;
    }
}

Better Approach

Store a count for zero shift every up then pad zeroes. The tricky park is how to count and shift.

Scan the array from left to right
if the element is not 0, shift it up by the number of zeroes we have so far
if it is 0, then increase the count of the 0s

Code

public void moveZeroes(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return;
    }
    int size = nums.length;
    int numOfZeroes = 0;
    // Step 1 Shift all elements to the zeroes before them
    for (int i = 0; i < size; i++) {
        if (nums[i] == 0) {
            numOfZeroes++;
        } else {
            nums[i - numOfZeroes] = nums[i];
        }
    }
    // Step 2 Pad zeroes in the end
    for (int j = size - numOfZeroes; j < size; j++) {
        nums[j] = 0;
    }
}