C/C++ Coding Exercise – Move Zeros

This is a leetcode puzzle: You can submit your solutions to this URL: https://leetcode.com/problems/move-zeroes/

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].

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

O(n^2) solution

The following O(n2) solution has runtime 72ms, which passes 21 test cases on the judge server. The idea is to check each number for the right-to-left directory. If it is zero, then move the next numbers 1 position to the left and move the zero the the right.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return;
        for (int j = len - 1; j >= 0; j --) { // checking for the tail
            if (nums[j] == 0) {
                int i = j;
                for (; (i < len - 1) && (nums[i + 1] != 0); i ++) { // move 1 number to the left
                    nums[i] = nums[i + 1];
                }
                nums[i] = 0; // move zero to the right
            }
        }
    }
};

The idea is simple, and it is a O(n2) algorithm, so it is not optimal.

leetcode-move-zeros-o-n-2-solution

O(n) solution

We can have 1 pointer (indexing pointer). It points to the current non-zero element to be filled, by scanning from the left to the right only filling non-zero elements gives a O(n) solution.

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

However, we would need a second O(n) loop) to fill the zeros to the end of the array.

We can further reduce to only 1 single O(n) loop by swapping the zeros with the non-zeros (making nonzero numbers jumping to the left).

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int j = 0; 
        for (int i = 0; i < len; i ++) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j ++]);
            }
        }
    }
};

leetcode-move-zeros-o-n-solution

This is a O(n) loop and simply cannot be optimized further.

–EOF (The Ultimate Computing & Technology Blog) —