Problem 283. Move Zeroes [Easy]

Description

Given an integer array nums, write an algorithm to move all 0’s to the end of the array while maintaining the relative order of the non-zero elements.

You must do this in-place without making a copy of the array.

My First Attempt [Time: O(n²), Space O(n)]

def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        zeroes = []
        i = 0
        while i < n:
            if nums[i] == 0:
                zeroes.append(nums[i])
                nums.remove(0)
                n -=1
            else:
                i += 1 
        nums.extend(zeroes)

First attempt is not optimal. Time complexity of this algorithm is O(n²) in worst case because of the nested loop from using nums.remove(0). This operation must scan the array for a zero, so has O(n) runtime and is inside the while loop giving O(n²).

Using a separate list zeroes to store the zeroes before appending gives O(n) space complexity in the worst case (all nums entries are zero).

Two Pointers Solution [Time: O(n), Space: O(1)]

def moveZeroes(nums):
    insert_pos = 0
    for num in nums:
        if num != 0:
            nums[insert_pos] = num
            insert_pos += 1
    for i in range(insert_pos, len(nums)):
        nums[i] = 0

The optimal solution is another two pointers, same as yesterday. This solution is super neat.

It’s called a read-write pointer pattern. The first loop (“read pointer”), goes through each entry in nums and shifts non-zero entries to the front or if it’s already in the right place it overwrites it with itself - no issue. Then the second pointer fills everything at the end of list with the amount of zeroes there should be.

C++ Version

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