Moving zeros to the end of an array while maintaining the order of nonzero 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 twopointers technique.
Solution 1: Brute Force Approach (using a Temp Array)
This method involves creating an auxiliary array to store the nonzero elements and then filling the original array with these elements followed by zeros.
Implementation:
// Solution1: Brute Force Approach (Using a Temp Array)
// Time Complexity: O(n) + O(x) + O(nx) ~ O(2n)
// n = total number of elements
// x = number of nonzero elements
// nx = total number of zeros
// Space Complexity: O(n)
// In the worst case, all elements can be nonzero.
void moveAllZerosToEnd(vector<int> &arr, int n)
{
vector<int> temp;
// Push nonzero elements to the temp vector.
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
{
temp.push_back(arr[i]);
}
}
// Number of nonzero elements
int nz = temp.size();
// Copy all nonzeros 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:
Push NonZeros to Temp: Traverse the array and push all nonzero elements to a temporary array.
Copy NonZeros Back: Copy the elements from the temporary array back to the original array.
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 nonzero elements. In the worst case, all elements can be nonzero.
Example:
Input:
arr = [0, 1, 0, 3, 12]
,n = 5
Output:
arr = [1, 3, 12, 0, 0]
Explanation: Nonzero elements are moved to the front and zeros to the end.
Solution 2: Optimal Approach (TwoPointers Technique)
This method uses two pointers to efficiently rearrange the array inplace without using extra space.
Implementation:
// Solution2: 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 nozeros, return
if (j == 1)
{
return;
}
// If nonzero 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:
Find First Zero: Find the index of the first zero.
Swap NonZero Elements: Traverse the array and swap each nonzero element with the element at the found zero index
j
.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: Nonzero 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.
Additional Notes
Efficiency: The twopointers method is more spaceefficient, making it preferable for large arrays.
Practicality: Both methods handle the problem efficiently but the choice depends on space constraints.
Conclusion
Moving zeros to the end of an array can be efficiently achieved using either a temporary array or an inplace twopointers technique. The optimal choice depends on the specific constraints and requirements of the problem.
Top comments (0)