Move Zeroes at the end of array

Problem

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Examples

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Solution

Method 1 - Bubble Zeroes to the End

Here we keep note of the index, where we find the zero and bubble it out with not zero element.

Code

Java

public void moveZeroes(int[] nums) {
	int m = -1;

	for (int i = 0; i<nums.length; i++) {
		if (nums[i] == 0) {
			if (m == -1 || nums[m] != 0) {
				m = i;
			}
		} else {
			if (m != -1) {
				swap(nums, i, m);
				m++;
			}
		}
	}
}

Method 2 - Using Partition in Quicksort OR Two Pointer 🏆

Actually, we can use the similar code that is used to solve

• Remove duplicates from Sorted Array 1
• Remove duplicates from Sorted Array 2
• Remove Element Problem

We can use almost identical code to solve those problems!

Code

Java

public void moveZeroes(int[] nums) {
	int i = 0; // left pointer -> increment only for non -ve nums
	int j = 0; // right pointer

	while (j<nums.length) {
		if (nums[j] != 0) {
			swap(nums, i, j);
			i++;
		}
		j++;
	}
}