# 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**:

```cpp
// 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**:

```cpp
// 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.

---