## DEV Community

Mahbub Alam Masum

Posted on • Originally published at blog.masum.dev

# How to Move Zeros to the End of an Array

Moving zeros to the end of an array while maintaining the order of non-zero elements is a common problem in programming. In this article, we'll discuss two approaches to achieve this: one using a temporary array and another using a two-pointers technique.

### Solution 1: Brute Force Approach (using a Temp Array)

This method involves creating an auxiliary array to store the non-zero elements and then filling the original array with these elements followed by zeros.

Implementation:

``````// Solution-1: Brute Force Approach (Using a Temp Array)
// Time Complexity: O(n) + O(x) + O(n-x) ~ O(2n)
// n = total number of elements
// x = number of non-zero elements
// n-x = total number of zeros

// Space Complexity: O(n)
// In the worst case, all elements can be non-zero.
void moveAllZerosToEnd(vector<int> &arr, int n)
{
vector<int> temp;

// Push non-zero elements to the temp vector.
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
{
temp.push_back(arr[i]);
}
}

// Number of non-zero elements
int nz = temp.size();

// Copy all non-zeros to main vector
for (int i = 0; i < nz; i++)
{
arr[i] = temp[i];
}

// Fill the remaining elements of the main vector with zeros
for (int i = nz; i < n; i++)
{
arr[i] = 0;
}
}
``````

Logic:

1. Push Non-Zeros to Temp: Traverse the array and push all non-zero elements to a temporary array.

2. Copy Non-Zeros Back: Copy the elements from the temporary array back to the original array.

3. Fill Zeros: Fill the remaining elements of the original array with zeros.

Time Complexity: O(n)

• Explanation: The array is traversed twice.

Space Complexity: O(n)

• Explanation: An additional array is used to store non-zero elements. In the worst case, all elements can be non-zero.

Example:

• Input: `arr = [0, 1, 0, 3, 12]`, `n = 5`

• Output: `arr = [1, 3, 12, 0, 0]`

• Explanation: Non-zero elements are moved to the front and zeros to the end.

### Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to efficiently rearrange the array in-place without using extra space.

Implementation:

``````// Solution-2: Optimal Approach (Using Two Pointers)
// Time Complexity: O(n)
// Space Complexity: O(1)
void moveAllZerosToEnd(vector<int> &arr, int n)
{
int j = -1;
// Find the first zero (if any)
for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
{
j = i;
break;
}
}

// If no-zeros, return
if (j == -1)
{
return;
}

// If non-zero found, swap it with the element at index 'j'.
for (int i = j + 1; i < n; i++)
{
if (arr[i] != 0)
{
swap(arr[j], arr[i]);
j++;
}
}
}
``````

Logic:

1. Find First Zero: Find the index of the first zero.

2. Swap Non-Zero Elements: Traverse the array and swap each non-zero element with the element at the found zero index `j`.

3. Increment Zero Index: After each swap, increment the zero index `j`.

Time Complexity: O(n)

• Explanation: The array is traversed once.

Space Complexity: O(1)

• Explanation: The algorithm operates in place, using only a constant amount of extra space.

Example:

• Input: `arr = [0, 1, 0, 3, 12]`, `n = 5`

• Output: `arr = [1, 3, 12, 0, 0]`

• Explanation: Non-zero elements are moved to the front and zeros to the end.

### Comparison

• Temp Array Method:

• Pros: Simple and easy to understand.
• Cons: Uses additional space, which may not be efficient for large arrays.
• Two Pointers Method:

• Pros: Efficient with O(n) time complexity and O(1) space complexity.
• Cons: Slightly more complex to implement but highly efficient for large arrays.

### Edge Cases

• Empty Array: Returns immediately as there are no elements to move.

• All Zeros: The array remains unchanged.

• No Zeros: The array remains unchanged.