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]