How to Move All Zeroes to End of Array?

Example to Understand

Let us look at examples to understand the problem well.

Input: {8, 4, 0, 2, 5, 0, 1, 0, 7, 0}

Output: {8, 4, 2, 5, 1, 7, 0, 0, 0, 0}

Input: {1,2}

Output: {1,2}

Input: {0, 0, 8, 2, 3, 0, 5}

Output: {8, 2, 3, 5, 0, 0, 0}

Here, all the non-zeros elements are moved in front, and zeros are moved to the end of the array.

Method 1: Using Pointers

We can think of an array as a set of two types of elements, zeros, and non-zero. We can make use of a pointer called count and a for loop that traverses the array.

We know that only non-zeros elements can be different and we are required to preserve their order. Zeros are all the same. Thus, as soon as we come across a non-zero element we insert it at the count position and increment count.

This way count will always be equal to or less than the current element's index and thus, there will be no data loss. Lastly, as we are done traversing the array, we start from count till N(total elements in the array) and insert zeros to move all zeros to end of array.

Approach

• Initialize count = 0.
• Use a for loop to traverse the array.
• If the current element is non-zero, insert the element at count and increment the value of count.
• Finally start a for loop from count till N where N is the total number of elements and insert zeros.

Implementation:

Output:

Complexity

Time Complexity: $O(N)$ as we are using only single for loop and no nested loops. Here, N is the total number of elements in the array.

Space Complexity: $O(1)$ No additional space is used in this method.

Method 2: Partitioning the Arrays

Here we will partition the array into pivot elements i.e. zero(0) and other elements. We use a for loop to traverse the array and for every non-pivot element we will swap the pivot with the element and increment the pivot index.

Approach

• Initialize j to the starting index.
• Use a for loop to traverse the array with i as iterator.
• If the element at i is not pivoted, swap it with the element at j and increment j.
• The array is rearranged as the required array.

Implementation:

Output:

Complexity

Time Complexity: $O(N)$ Here, N is the total number of elements in the array.

Space Complexity: $O(1)$ No additional space is required in this method.

Method 3: Using C++ STL

Instead of using a fixed-size array, we can also use a dynamic array such as a vector or ArrayList from C++ STL to move all zeros to end of array. We can traverse the array remove all the zeros from the dynamic array and keep a count of all the removed zeros. Lastly, add all the zeros at end of array equal to the count.

Approach

• Initialize count = 0;
• Use a for loop to traverse the array.
• Instead of deleting the zero we simply use that index to put other elements.
• After completion of the iteration, we will insert zeros at the end.

Implementation:

Output:

Complexity

Time Complexity: $O(N)$ As we are traversing the array only once.

Space Complexity: $O(1)$ No additional space is used in this method.

Method 4: Using Extra Space

We can also move all zeros to end of array using the brute force approach where we will be using an extra array. The time complexity of the approach will remain $O(N)$. We will initialize the rearranged array. Traverse the array and for every non-zero element, insert the element in the new array. Lastly, insert all the remaining positions with zero in the new array.

Approach

• Initialize a new array named rearranged of the same size.
• Initialize j with the starting index.
• Use a for loop to traverse the array.
• If the element is not equal to zero, then add the element to the rearranged array at index j and increment j.
• Lastly, start a loop from j to N and insert zeros to move all zeros to end of array.

Implementation:

Output:

Complexity

Time Complexity: $O(N)$ as we are using only a single for loop to traverse the array. Here, N is the total number of elements in the array.

Space Complexity: $O(N)$ We are using an additional array of the same size as the original array.