Move Zeroes

Given an arraynums, write a function to move all0's to the end of it while maintaining the relative order of the non-zero elements.

For example, givennums = [0, 1, 0, 3, 12], after calling your function,numsshould be[1, 3, 12, 0, 0].

Note:

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

Brainstorm

My initial approach was to simply erase a 0 whenever we encounter it, append 0 to the end of the array, and update the range of the array we want to iterate. This seemed straightforward enough for a first approach.

Approach #1: Erase 0's and Append

We use the C++ vector's erase() function to help us remove elements and then append it to the end of the array. Note that we have to decrement the range of the array we want to iterate and the index of the iterator. Why? Using the example:

• [0, 1, 0, 3, 12], i = 0, size = 5: we want to move nums[0]] to the end
• [1, 0, 3, 12, 0]
  • size should be updated to 4 because we only want to process [1, 0, 3, 12] and not the 0 that we came across already.
  • i should be decremented so that on the next iteration it is kept at 0, because now nums[0] points to a new number, 1, that we shouldn't skip over (which would've happened if we incremented i).

void moveZeroes(vector<int>& nums) {
    int size = nums.size();
    for (int i = 0; i < size; i++) {
        if (nums[i] == 0) {
           nums.erase(nums.begin()+i);
           nums.push_back(0);
           size--;
           i--;  
        }
    }
}

Time complexity: $$O(n^2)$$

We erase 0's and append in one loop, however this isn't really O(n)! This is because of the erase() function we called inside the loop, which has a time complexity of O(n) in worst case. So a nested O(n) inside a O(n) loop yields a O(n^2) overall time complexity.

Space complexity: $$O(1)$$

While this approach does its job, the O(n^2) time complexity leaves a lot to be desired! The optimization to linear time took a while longer, but hopefully as I explain it in the following passage, I can polish my understanding of it.

Approach #2: Two Pointers

Instead of thinking about this problem as "push all 0's to the end", why not think about this way: "bring all non-0's to the front"? To form our solution in this approach, we will need two pointers: one "fast" pointer that runs ahead to find all the non-0's, and one "slow" pointer to stay behind and bring the non 0's to the front where they should be in relative order. The non-0's brought to the front will overwrite the 0's, but this is ok; where the slow "pointer" ends is where all the 0's go. Thus, at the end we just need to append 0's to all the remaining positions from the slow pointer. This process can be illustrated using the array from the example:

• [0, 1, 0, 3, 12]
• [1, 1, 0, 3, 12], we found nums[1] = 1, now bring it to the front to replace nums[0]
• [1, 3, 0, 3, 12], we found nums[3] = 3, now bring it to the front to replace nums[1]
• [1, 3, 12, 3, 12], we found nums[4] = 12, now bring to the front to replace nums[2]
• [1, 3, 12, 0, 0], done; starting from nums[3] and onwards, write 0's

void moveZeroes(vector<int>& nums) {
    int j = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[j] = nums[i];
            j++;
        }
    }
    for (int k = j; k < nums.size(); k++)
        nums[k] = 0;
}

Time complexity: $$O(n)$$

Now we are able to perform all of this within one loop, with constant time operations! This optimizes the time complexity to O(n).

Space complexity: $$O(1)$$