# 283. Move Zeros

## Problem

• Given an array nums, write a func to move all 0 s to the end of it while keeping the relative order of the non-zero elements
• Must do this in-place without making a copy of array
• Minimize the total number of operations

## Thought Process

• Loop through the whole array
• filter out non-zeros
• fill the first part of the array with non-zeros
• fill the rest with 0

## White Board

Below is the white board:

## Code

class Solution:

def moveZeros(self, nums):
k = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[k] = nums[i]
k += 1

for j in range(k, len(nums)):
nums[j] = 0

def test_moveZeros():
mz = Solution()
nums = [0] * 5 + list(range(5))
import random
random.shuffle(nums)
print("Before Move Zeros: ")
print(nums)
mz.moveZeros(nums)
print("After Move Zeros: ")
print(nums)

test_moveZeros()

Before Move Zeros:
[2, 0, 0, 3, 1, 4, 0, 0, 0, 0]
After Move Zeros:
[2, 3, 1, 4, 0, 0, 0, 0, 0, 0]


## Complexity

• Time complexity is O(n), as a single for loop iteration is used
• Space complexity is O(1), as it’s inplace, no extra space was created

## Optimization

Here the 2nd half of the solution: fill the rest nums with 0, is kinda unnecessary. I could have just swapped non-zero and zero items while looping thru the list.

class Solution2:

def moveZeros2(self, nums):
k = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[k], nums[i] = nums[i], nums[k] #swap non-zero and zero
k += 1

def test_moveZeros2():
mz = Solution2()
nums = [0] * 5 + list(range(5))
import random
random.shuffle(nums)
print("Before Move Zeros: ")
print(nums)
mz.moveZeros2(nums)
print("After Move Zeros: ")
print(nums)

test_moveZeros2()

Before Move Zeros:
[3, 0, 0, 0, 0, 1, 2, 4, 0, 0]
After Move Zeros:
[3, 1, 2, 4, 0, 0, 0, 0, 0, 0]