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]

Super Brute Force Approach

Just create a new array. Then copy over the non-zero elements in order and done.

def moveZeroes(self, nums: List[int]) -> List[int]:
    n = len(nums)
    if n == 0:
        return
    
    copy_array = [0 for i in range(n)]
    
    non_zero_index = 0
    for ele in nums:
        if ele != 0:
            copy_array[non_zero_index] = ele
            non_zero_index += 1

    return copy_array

The time complexity is $O(n)$. The space complexity is also $O(n)$.

Brute Force Approach

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

Brute Force Code

Version1: Swapping zeroes to the end

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++;
    }
}

Version 2: Swapping non-zero elements to the front

def moveZeroes(nums: List[int]) -> None:

  n = len(nums) 

  if n == 0:
      return 

  for i in range(n):
      if nums[i] != 0:
          swap_to_front(nums, i)
    
def swap_to_front(nums: List[int], i: int) -> None:

  while i > 0 and nums[i-1] == 0:
      swap(nums, i, i-1)
      i -= 1

def swap(nums: List[int], i: int, j: int) -> None: 
  temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp

Slower with $O(n^2)$ time but in place

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;
    }
}

Alternative Approach

We can do something similar to first approach but have to swap. Swap after the last non-zero element with a single scan.

def moveZeroes(self, nums: List[int]) -> None:

    n = len(nums) 
    
    if n == 0:
        return 
    
    last = 0
    
    for i in range(n):
        if nums[i] != 0:
            # swap after the last non-zero element 
            swap(nums, i, last)
            last += 1 

$O(n)$ time with $O(1)$ space

Proof sketch

Assume there is a dummy non-zero element before the list. Every element has 2 cases, zero or non-zero. For zero, we can simply ignore them. For non-zero, if it gets swapped right after the previous non-zero element, then the relative ordering is kept and there is no zeroes between the non-zero elements. Non-zero element will never get swapped with another non-zero element because if a non-zero element appears right after another non-zero element then it will just swap with itself. If a non-zero element does not appear right after another non-zero element, then that means there must be some zeroes between them and swapping with zeroes is fine in that sense that we don't have to keep a relative ordering of the zeroes.