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.

---