Solutions

1. Extra Array

O(n) time | O(n) space

Intuition

We can iterate through the array with one loop copying the non-zero elements into a new array in the order we meet them.

Then fill the rest of the new array with zeroes, and copy the array back.

Algorithm

Create an empty array result.
Iterate through the loop from the first element to the last element, adding every element that is not 0 to result.
Add 0 to result until it has the same length as the original array.
Copy every element of result back into the original array.

01234

0 == 0, skip

1 / 8

Code

def moveZeroes(nums: list[int]) -> None:
    result = []
    for n in nums:
        if n != 0:
            result.append(n)
    while len(result) < len(nums):
        result.append(0)
    nums[:] = result

/**
 * @param {number[]} nums
 * @returns {void}
 */
var moveZeroes = function (nums) {
  const result = []
  for (const n of nums) {
    if (n !== 0) result.push(n)
  }
  while (result.length < nums.length) result.push(0)
  for (let i = 0; i < nums.length; i++) nums[i] = result[i]
}

class Solution {
    public void moveZeroes(int[] nums) {
        int[] result = new int[nums.length];
        int at = 0;
        for (int n : nums) {
            if (n != 0) result[at++] = n;
        }
        System.arraycopy(result, 0, nums, 0, nums.length);
    }
}

2. Two Pointers

O(n) time | O(1) space

Intuition

We can iterate through the array with one loop, keeping a j index pointing at the place where the next non-zero element has to go.

Every time we meet a non-zero element we swap it with the element on j and increase j by one. The swap puts the non-zero element in its final place and moves the zero closer to the end of the array.

Algorithm

Create a j index variable with initial value 0.
Iterate through the loop from the first element to the last element with i index.
If the element on i is not 0, swap the elements on j and i indexes and increase j by one.

01234

0 == 0, skip

1 / 6

Code

def moveZeroes(nums: list[int]) -> None:
    j = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[j], nums[i] = nums[i], nums[j]
            j += 1

/**
 * @param {number[]} nums
 * @returns {void}
 */
var moveZeroes = function (nums) {
  let j = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[j], nums[i]] = [nums[i], nums[j]]
      j++
    }
  }
}

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