# Move all zeros present in an array to the end

Posted in  Vinay Khatri
Last updated on December 4, 2023

We have given an integer array, and we need to move all the zeros present in it to the end. And the output array must maintain the relative order of its elements, which means the order of other elements (except 0) must be in the same order.

Example

```Input : [5,0,7,4,5,3,0,1,0,6]
Output: [5,7,4,5,3,1,6,0,0,0]```

Explanation In the output, you can see that all the zeros have been moved to the end of the array, and the order of the rest of the elements is the same.

## Approach 1

#### Optimized Algorithm

In this approach, we will use two loops to solve the problem. In the first traversal, we will traverse through the complete array, check if the current element is not zero, then place the element at the available position in the array. The idea is simple we will shift all the non-zero elements toward the left where elements zero are present. And in the second traversal, we will shift fill the remaining indices with 0.

### Algorithm

1. Initialize an identifier ``` pos=0 ``` that will represent the index value for the next available position.
2. Traverse through every array element using a loop.
3. Inside the loop, check if the element is a non-zero element.
4. If the element is a non-zero element, put the element at ``` arr[pos] ``` and increase the value of ``` pos ``` by 1 (this will shift all the non-zero elements toward the left).
5. Now run a loop from ``` pos ``` to the end of the array and fill the remaining ``` pos ``` indices with zeros.

#### C++ Programming

```#include <iostream>
using namespace std;

// function to move zeros
//at the end of the array
void move_zeros(int arr[],int n)
{
//pos will store the index value
//for the next available position
int pos =0;

//traverse through every element
for(int i=0; i<n;i++)
{
//check if the current element is non-zero
//put the element at the arr[pos]
if (arr[i]!=0)
{
arr[pos]=arr[i];
pos++;
}
}

//fill the remaining pos indices with zeros
for(int i=pos; i<n; i++)
{
arr[i]=0;
}

}

int main()
{	//given array
int arr[]={5,0,7,4,5,3,0,1,0,6};

//length of the array
int n = sizeof(arr) / sizeof(arr);

move_zeros(arr, n);
for(int i=0; i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
```

Output #### Python Programming

```def move_zeros(arr, n):
# pos will store the index value
# for the next available position
pos=0

# traverse through every element
for i in arr:
# check if the current element is non-zero
# put the element at the arr[pos]
if i:
arr[pos]=i
pos+=1
#fill the remaining pos indices with zeros
for i in range(pos, n):
arr[i]=0

if __name__=="__main__":
#given array
arr= [5,0,7,4,5,3,0,1,0,6 ]

#length of array
n = len(arr)

move_zeros(arr,n)
print(arr)

```

#### Output ### Complexity Analysis

• Time Complexity: O(N), is the time complexity of the above program.
• Space Complexity: The space complexity is O(1) because we did not use any extra array to store given array elements.

## Approach 2

### Using Quick Sort Pivot Logic

This problem can also be solved using the same quick sort algorithm partitioning logic. Here, we will use the 0 elements as a pivot element, traverse through the array, and swap every non-zero element with the first occurrence of the pivot (0 elements). With this, we will move all the non-zero elements toward the left side of the pivot element (0).

### Algorithm

1. Initialize a ``` pos ``` identifier with index value 0, that will store the index value for the available next zero position.
2. Create a loop that will traverse through every element of the array.
3. Inside the loop check if the element is non-zero.
4. If the element is non-zero swap the elements with arr[pos], and increment the value of pos by 1.

#### C++ Programming

```#include <iostream>
using namespace std;

// function to move zeros
//at the end of the array
void move_zeros(int arr[],int n)
{	// initialize position identifier
int pos=0;

// initialize temp variable for swapping
int temp;

//traverse through every element
for(int i=0; i<n; i++)
{
//check if the element is non-zero
//swap the element with arr[pos]
//increase the pos value by 1
if(arr[i]!=0)
{
temp = arr[i];
arr[i]= arr[pos];
arr[pos] = temp;
pos++;
}
}

}

int main()
{	//given array
int arr[]={5,0,7,4,5,3,0,1,0,6};

//length of the array
int n = sizeof(arr) / sizeof(arr);

move_zeros(arr, n);
for(int i=0; i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}

```

#### Output #### Python Programing

```def move_zeros(arr, n):
#initialize position identifier
pos= 0
for i in range(n):
# check if the element is non-zero
# swap the element with arr[pos]
# increase the pos value by 1
if arr[i]:
arr[i],arr[pos] = arr[pos], arr[i]
pos+=1

if __name__=="__main__":
#given array
arr= [5,0,7,4,5,3,0,1,0,6 ]

#length of array
n = len(arr)

move_zeros(arr,n)
print(arr)
```

#### Output ### Complexity Analysis

• Time Complexity: O(N ) is the time complexity of the above program.
• Space Complexity: O(1)

## Wrapping Up!

In this DSA tutorial, we learned two different algorithms to "Move all zeros present in an array to the end". We not only discuss the algorithms but also implement both the algorithms in C++ and Python programming languages. There are many other logic and algorithms we can use to solve this problem, but the above two are the most optimized and solve the problem in linear time complexity with Constant space complexity.