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 =  * 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: [0, 1, 3, 0, 2, 0, 0, 4, 0, 0] After Move Zeros: [1, 3, 2, 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 =  * 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: [0, 4, 0, 2, 0, 3, 0, 0, 1, 0] After Move Zeros: [4, 2, 3, 1, 0, 0, 0, 0, 0, 0]