Move Zeroes

1. Problem Description

Given an array nums, write a function to move all 0s to the end of the array while preserving the relative order of the non-zero elements.

2. Approach

1. Approach 1
   • Selection sort
   • Find a 0 from left to right, then find a non-zero element after it and swap them
2. Approach 2
   • Two pointers moving in the same direction. Move all non-zero elements to the front, then set the rest to 0

3. Implementation

3.1. Selection Sort

func moveZeroes(nums []int) {
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			continue
		}
		for j := i + 1; j < len(nums); j++ {
			if nums[j] != 0 {
				swap(nums, i, j)
				break
			}
		}
	}
}

3.2. Two Pointers

// Time: O(N)
// Space: O(1)
func moveZeroes2(nums []int) {
	if len(nums) == 0 {
		return
	}

	// Move all non-zero elements to the front
	j := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[j] = nums[i]
			j++
		}
	}

	// Set all remaining elements to 0
	for i := j; i < len(nums); i++ {
		nums[i] = 0
	}

}

4. References

• 283. Move Zeroes - LeetCode