Beginner

555. Move All Zeroes to the End of the Array

Problem Statement:

Given an array of random numbers, move all the zeros to the end of the array while maintaining the relative order of the non-zero elements.

Example 1:

```Input: {0, 1, 0, 3, 12}
Output: {1, 3, 12, 0, 0}
```

Example 2:

```Input: {1, 2, 0, 0, 3, 4}
Output: {1, 2, 3, 4, 0, 0}
```

Example 3:

```Input: {0, 0, 0, 0}
Output: {0, 0, 0, 0}
```

Naive Solution:

• Create a new result array of the same length as the input array.
• Iterate through the input array and place each non-zero element in the result array.
• Leave the zeroes at the end by default, as the uninitialized values in the result array are zeroes.

Time Complexity: O(N), Space Complexity: O(N)

Output

```[0, 1, 0, 3, 12]
[1, 3, 12, 0, 0]
```

Better Solution:

• Use a pointer (or counter) to track the position of non-zero elements.
• Iterate through the array and shift all non-zero elements to the front.
• Fill the remaining spaces with zeroes.

Time Complexity: O(N), Space Complexity: O(1)

Output

```Input: [1, 2, 0, 0, 3, 4]
Output: [1, 2, 3, 4, 0, 0]
```