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.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

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:

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

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.