Move Zeroes

Problem

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.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

• You must do this in-place without making a copy of the array.
• Minimize the total number of operations.

Solution

public class Solution {
    public void moveZeroes(int[] nums) {
        int lastNonZeroIndex = 0;
        for (int num : nums) {
            if (num != 0) nums[lastNonZeroIndex++] = num;
        }
        for (int i = lastNonZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

Optimal operations with just one loop

public class Solution {
    public void moveZeroes(int[] nums) {
        for (int i = 0, lastNonZeroIndex = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[lastNonZeroIndex];
                nums[lastNonZeroIndex++] = temp;
            }
        }
    }
}

Analysis

The problem can be divided into two parts
First we need to find out all non zeroes and move them to the beginnings
Then we have to fill 0 at the end
We use lastNonZeroIndex to record the index of last non zero element

In the second optimal solution
We just have one loop because we immediately swap when we meet non zero elements
We need to have two vars to record the two indices
Therefore, we don't have to use one more loop to fill the 0s cause we use swap

Complexity Analysis:

• time: O(n) for both solutions, but the second one will have less operations for case like [0,0,0,1]
• space: O(1) constant space for both solutions