How to Move Zeros to the End of an Array

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.

Additional Notes

  • Efficiency: The two-pointers method is more space-efficient, 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 in-place two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.