# Move Zeroes

{% hint style="info" %}
Array, Two Pointers
{% endhint %}

Given an integer array `nums`, move all **0's** to the end of it while maintaining the relative order of the non-zero elements.

**Note** that you must do this in-place without making a copy of the array.

Example 1:

```
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
```

Example 2:

```
Input: nums = [0]
Output: [0]
```

### Solutions

The problem is asking to move all zeros in the given array to the end while maintaining the relative order of the non-zero elements. This means that the sequence of non-zero numbers in the array should remain the same after all the zeros have been moved to the end.

#### **Approach – Brute Force Technique**

In the brute force approach, we use a simple bubble sort algorithm to push the zeros to the end of the array.

**Steps**

1. **Get the length of the array:** The variable `n` is assigned the length of the `nums` array.
2. **Outer loop:** The outer loop runs from `i = 0` to `i = n - 1`. This loop iterates over each element in the array.
3. **Inner loop:** The inner loop runs from `j = 0` to `j = n - i - 2`. This loop compares each element with its next element.
4. **Check for zero:** If the current element `nums[j]` is zero, then it needs to be moved to the end.
5. **Swap elements:** If `nums[j]` is zero, it is swapped with the next element `nums[j + 1]`. This is done by creating a temporary variable `temp` to hold the value of `nums[j]`, then assigning `nums[j]` the value of `nums[j + 1]`, and finally assigning `nums[j + 1]` the value of `temp`.
6. **Repeat:** The process is repeated for all elements in the array until all zeros have been moved to the end.

```csharp
public class Solution
{

    public void MoveZeroes(int[] nums)
    {
        int n = nums.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (nums[j] == 0)
                {
                    // Swap nums[j] and nums[j + 1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}
```

> Complexity

* **Time Complexity:** O(n^2)
* **Auxiliary Space:** O(1)

#### **Approach – Two Pointers Technique**

In the optimized approach, we keep track of the last non-zero element found in the array. We then swap the current element with the last non-zero element if the current element is non-zero.

**Steps**

1. **Initialize a pointer:** The variable `lastNonZeroFoundAt` is initialized to `0`. This pointer will keep track of the position where the next non-zero element should be moved.
2. **Iterate through the array:** The first `for` loop runs from `i = 0` to `i = nums.Length - 1`. This loop iterates over each element in the array.
3. **Check if the current element is non-zero:** If the current element `nums[i]` is non-zero, then it needs to be moved to the position pointed by `lastNonZeroFoundAt`.
4. **Move non-zero elements to the front:** If `nums[i]` is non-zero, it is moved to the position `nums[lastNonZeroFoundAt]`, and then the `lastNonZeroFoundAt` pointer is incremented. This effectively moves all non-zero elements to the front of the array, while maintaining their relative order.
5. **Fill the rest of the array with zeros:** The second `for` loop runs from `i = lastNonZeroFoundAt` to `i = nums.Length - 1`. This loop sets all the remaining elements in the array to zero.

```csharp
public class Solution
{
 
    public void MoveZeroes(int[] nums)
    {
        int lastNonZeroFoundAt = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 0)
            {
                nums[lastNonZeroFoundAt++] = nums[i];
            }
        }
        for (int i = lastNonZeroFoundAt; i < nums.Length; i++)
        {
            nums[i] = 0;
        }
    }
}
```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(1)