[Leetcode]283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Brute force

The brute force approach would be using one pointer to scan the input array and put non-zero elements into a new array. Then place zeros to fill the remaining positions. However, this would violate Note 1.

Two pointers – suboptimal

One of the in-place approaches would be using two pointers i and j, with j explores the array and i indicates the next position to hold non-zero items. Whenever j meets a non-zero item, we can put nums[j] to place i and move i to i+1.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[i] = nums[j]
                i += 1
        while i < len(nums):
            nums[i] = 0
            i += 1

This is suboptimal because the number of operations is the length of the input array.

Two pointers – optimal

We can achieve fewer operations, reducing the number of operations to the number of non-zero values. We would still use two pointers, with j explores the array and i indicates the first zero. The invariance in this approach is that all the values before i are non-zero and items between i and j are zeros. The way we main this is:

• if j meets non-zero items, we swap nums[i] and nums[j]
• if j meets zeros, we keep moving only j forward

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