# [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 Initiate a new array and put non-zero values in it first.

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

Subscribe
Notify of 