Move Zeroes

---

Move Zeroes: Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

---

Example 2:

Input: nums = [0]
Output: [0]

---

Constraints:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

---

Try this Problem on your own or check similar problems:

1. Remove Element
2. Apply Operations to an Array

Solution:

Java

public void moveZeroes(int[] nums) {
  int writer = 0;
  for(int i = 0; i < nums.length; ++i){
      if(nums[i] != 0){
          nums[writer++] = nums[i];
      }
  }
  while(writer < nums.length) nums[writer++] = 0;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let writer = 0;
  for (let i = 0; i < nums.length; ++i) {
    if (nums[i] !== 0) {
      nums[writer++] = nums[i];
    }
  }
  while (writer < nums.length) {
    nums[writer++] = 0;
  }
};

Python

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        writer = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[writer] = nums[i]
                writer += 1
        while writer < len(nums):
            nums[writer] = 0
            writer += 1

C++

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

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We traverse the whole input array leading to linear time complexity, and since we have to make the change in-place, without copying or creating new instance we have constant space complexity. Problems like this can be solved using two pointers/iterators, writer which actually is doing the changes to the array and iter in this case i in the for loop which is only going through array and reading values. Since we're only interested in non-zero value we only write those, incrementing writer every time we encounter non-zero value. We fill the rest of array with zeroes (all other non-zero values have been already written).