Home » Data Structure » Array Data Structure

Move all zeroes to the end of the array

C++ implementation to move all zeroes to the end of the array using multiple approaches.
Submitted by Vikneshwar GK, on March 04, 2022

Consider an integer array, of size n. The task at hand is to move all the zeroes to the end of the array while maintaining the order of other elements of the array.

Example

Input:
array[]= {1, 2, 0, 0, 3, 0, 4, 0, 5}

Output:
array[] = {1, 2, 3, 4, 5, 0, 0, 0, 0}

Input:
array[]= {10, 9, 0, 8, 0, 7, 0, 6}

Output:
array[] = {10, 9, 8, 7, 6, 0, 0, 0}

Solution 1: Moving non-zero elements using a Counter

This method involves iterating through the array twice, where the first iteration involves moving the non-zero elements to the left side and the second iteration places the zeros at the end of the array. It is a simple, yet efficient approach that won't involve using an additional array. It involves the following steps:

• Initialize counter = 0
• Iterate the array and check if the element is not zero
• If true, place that element at the counter's position, i.e., array[counter] = array[i] and increment the counter
• Iterate through the array from counter to n, where n is the length of the array, and set array to zero, i.e., array[counter] = 0 and increment the counter

C++ Implementation

#include <iostream>
using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
    // set counter to zero
    int count = 0;

    // place non zero elements first
    for (int i = 0; i < length; i++)
        if (array[i] != 0)
            array[count++] = array[i];

    // place zeros at last
    while (count < length)
        array[count++] = 0;
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Main function
int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 2
Enter element 2: 0
Enter element 3: 4
Enter element 4: 0
Enter element 5: 0
Enter element 6: 7
2 4 7 0 0 0 

Time Complexity: O(n), where n is the length of the array.

Solution 2: Using an Additional Array

This method involves using an extra array, which is initialized with zeros. Iterate through the array and place only the non-zero elements at the beginning of the new array.

C++ Implementation

#include <iostream>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
    // initialize new array
    int newArray[length] = { 0 }, counter = 0;
    for (int i = 0; i < length; i++) {
        // place non zeros in the beginning
        // in new array
        if (array[i] != 0) {
            newArray[counter++] = array[i];
        }
    }
    printArray(newArray, length);
}

// Main function
int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 0
Enter element 2: 1
Enter element 3: 4
Enter element 4: 0
Enter element 5: 5
1 4 5 0 0

Time Complexity: O(n), where n is the length of the array.