# Move Zeroes

ArrayTwo Pointers

## # Solution

### # Two Pointers

The fast pointer i iterates nums. The slow pointer non_zero points to next position of non-zero element.

When nums has many zeros, the latter loop incurs too many operations.

Complexity

time: $O(n)$
space: $O(1)$

def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
non_zero = 0
for i in range(n):
if nums[i] != 0:
# if non-zero
nums[non_zero] = nums[i]
non_zero += 1
# set the remaining to 0
for i in range(non_zero, n):
nums[i] = 0

1
2
3
4
5
6
7
8
9
10
11

Could you minimize the total number of operations done?

### # Improved Two Pointers

We maintain the following invariants:

1. All elements in nums[:non_zero] are non-zeroes
2. All elements in nums[non_zero:i] are zeroes

Thus, rather than setting elements after non_zero to 0, we could simply swap the zero at non-zero and nonzero at i.

Complexity

time: $O(n)$
space: $O(1)$

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

1
2
3
4
5
6
7