Zeros to the End

Write a method that moves all zeros in an array to its end. You should maintain the order of all other elements. Here's an example:

zerosToEnd([1, 0, 2, 0, 4, 0])
// [1, 2, 4, 0, 0, 0]

Here's another one:

zerosToEnd([1, 0, 2, 0, 4, 0])
// [1, 2, 4, 0, 0, 0]

Fill in the following function signature:

function zerosToEnd(nums) {
  return;
};

Can you do this without instantiating a new array?

Constraints

• Length of the array <= 100000
• The array will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

```js
function zerosToEnd(nums) {
  // Fill in this method
  return nums;
}

console.log(zerosToEnd([1, 0, 2, 0, 4, 0]));
```

Always start by running through some examples to get a feel for the problem. With [1, 0, 2, 0, 4, 0], let's walk through the steps-- in this case, it may be best to work backwards.

We want to end up with [1, 2, 4, 0, 0, 0]. To do that, it seems like we need to separate out [1, 2, 4] and [0, 0, 0], so there's 3 things to consider.

We need to do these 3 things:

1. Separate the 0s and non-0s.
2. Find out where the non-0s need to be index-wise
3. Keeping track of the number of 0s

We have a potential brute force solution! This could be our pseudocode.

```
temp = []
zero_count = 0
iterate through array:
  if nonzero, push to new temp
  if zero, increment count
for zero_count times:
  push to temp
return temp
```

We can do better.

The above snippet would get the job done, but requires extra space with the new temp array.

Without a temp array, we'll need to change the position of elements in the array in-place. This means that we'll need to mutate the array's elements directly. This requires us to keep track of indexes.

```js
const arr = [1, 0, 2, 0, 4, 0];
const nonZeros = [1, 2, 4]
```

Here's a thought exercise.

Perhaps we can try to simplify-- what if we just kept track of one index?

Then, what if we used multiple trackers? Would it be beneficial to know about multiple positions at once, in the context of this problem?

Multiple pointers is key.

Because we don't need or care about what is in the array after non-zero elements, we can simply keep a separate pointer of where to start the zeros. This extra pointer will prevent us from having to store a separate temp array, with the intuition being that we know what we need to fill after (exclusively 0s!).

Despite having two loops, the time complexity simplifies to O(n). However, the space complexity is constant since we're using the same array.

Follow the below illustration for more guidance:

One Pager Cheat Sheet

• Write a function zerosToEnd which moves all zeros in an array to its end, while maintaining the order of all other elements, within O(n) time and O(1) space complexity constraints.
• Run through examples and separate the [1, 2, 4] from the [0, 0, 0] to achieve [1, 2, 4, 0, 0, 0].
• We need to separate the 0s and non-0s, find out where the non-0s need to be index-wise, and keep track of the number of 0s in order to solve this problem using a potential brute force solution.
• We can do better by changing the position of elements in the array in-place, which requires us to mutate and keep track of indexes.
• Try simplifying the problem by only keeping track of one index, or use multiple trackers to know about multiple positions at once.
• Multiple pointers are key for efficiently moving all zeros to the end of an array in O(n) time complexity and constant space complexity.