Given an arraynums
, write a function to move all0
'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 swapnums[i]
andnums[j]
- if
j
meets zeros, we keep moving onlyj
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