Move Zeros Code Challenge
Tags: 100daysofcode, javascript, algorithms, techinterview
Published: 2020-11-25 15:44:01

There are usually two variations of this challenge, the only difference being if the zeroes need to be moved to the end  (right) or start (left ) of the array. Below is the challenge as copied from the **[geeksforgeeks](https://www.geeksforgeeks.org/move-zeroes-end-array/)** website:

***Given an array of random numbers, push all the zero’s of a given array to the end of the array.*** 

***For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, 
it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}.*** 

***The order of all other elements should be same. 
Expected time complexity is O(n) and extra space is O(1).***

We will cover two ways of solving for this, the first a  [brute force](#brute-force-first-solution)  or a first best guess on a working solution, then we will tackle  [the recommended way](#optimized-solution-recommended-one)  to have a point of comparison.

## Video here 
{%youtube CC8edj19Uiw %}

## Brute Force - First solution
My first intuition could be broken down into the steps below:
1. Get the size of the current array
2. Create a second array the size of the first one and fill with zeroes
3. Filter out all zeroes from the first array which will maintain the order of the non zero items
4. Take the difference of lengths between the first array and the filtered array to get the offset index
5. If the zeroes need to be on the end of the array, fill the holder array from the start to the length of filtered array
6. If the zeroes need to be at the start, replace the items starting from the offset to the end.
7. Return the holder array

Now that we have the steps, let's look it with code and hopefully make it easy to register. Let's start with the function declaration:
```javascript
const moveZeroes = ( arr, dir = 'end') => {
    // body of function here
}
```
Our function expects a well formed array of digits and an optional direction parameter that defaults to 'end'. Now on to the steps for the body of the function:
* Get the size of the current array
```javascript
const size = arr.length;
```
* Create a second array the size of the first one and fill with zeroes
```javascript
let holder = Array.from({ length: size}, () => 0);
```
* Filter out all zeroes from the first array which will maintain the order of the non zero items
```javascript
let filtered = arr.filter( v => v !== 0);
```
* Take the difference of lengths between the first array and the filtered array to get the offset index
```javascript
let offset = size - filtered.length;
```
* If the zeroes need to be on the end of the array, fill the holder array from the start to the length the filtered array
```javascript
if( dir === 'end' ) {
    filtered.forEach( (v, i) => holder[i] = v );   
}
```
* If the zeroes need to be at the start, replace the items starting from the offset to the end.
```javascript
if( dir === 'start' ) {
    filtered.forEach( (v, i) => holder[ i + offset] = v );
}
```
* Return the holder array

*Au final*, we get the code below as our brute force solution:
```javascript
const moveZeroes = ( arr, dir = 'end') => {
    const size = arr.length;
    let holder = Array.from({ length: size}, () => 0);
    
    const filtered = arr.filter( v => v !== 0);
    const offset = size - filtered.length;

    if( dir === 'end' ) {
        filtered.forEach( (v, i) => holder[i] = v );
    }

    if ( dir === 'start' ) {
        filtered.forEach( (v, i) => holder[ i + offset] = v )
    }
    
    return holder;
}
```
And we can test it with:
```javascript
let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('Zeroes to end: ', moveZeroes(arr));
console.log('Zeroes to start: ', moveZeroes(arr, 'start'));
```
Which outputs
```
Zeroes to end   :   [1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0]
Zeroes to start :   [0, 0, 0, 0, 1, 9, 8, 4, 2, 7, 6]
```
This satisfies the expected output of the challenge but, we should run an auto critique and see the many things that make our solution not so optimized:

* First we are creating a second array to hold the the filtered items
* Second we create a third array then fill it with zeroes, each of those steps is an additional computation step and increase the execution time as the array grows in size
* Lastly, we iterate and change the newly created array to place our filtered items and respect the order of the items

So the big question is can we achieve the same with only the one array passed and not to have to create all this new ones and how do we swap the zeroes to an end without affecting the order.

The answer is of course yes and like the first solution we will start with a breakdown of the logic of the solution to hopefully help with understanding

## Optimized solution - recommended one
We will operate within only one array and keep track of two indexes: a **read index** and a **write index** which both start at the same position.

We will use the **readIndex** to scan the array from end to end and skip any cell that contains a zero. 

When we encounter a **non-zero**, we update the value at the **writeIndex** with the **non-zero** value then we decrement or increment the **writeIndex** based on which side we need to move the zeroes to.

If your head is spinning from reading the above steps, I have put up a visualization that might help you understand it quickly. This below shows the step by step of moving the zeroes to the left

![0-viz-move-zeroes](https://dev-to-uploads.s3.amazonaws.com/i/9vf17g6s5gdc1ne2vzvq.gif)

Let's translate that into code with two separate functions this time starting with the zeroes to the left.

### [Optimized] Move Zeroes Left
As always we start with the function declaration
```javascript
const moveZeroesLeft = function(arr) {

}
```
Then we declare two local variables to hold a **writeIndex** and a **start** position
```javascript
let writeIndex = arr.length - 1;
let start = writeIndex;
```
Both indexes start at the end of the array.

You might've guessed from the visualization that we will run two internal loops. 

The first loop will scan for non-zeroes with a **readIndex** and put the value found at the **writeIndex**. 
The **writeIndex** will decrement every time after such an operation
```javascript
for(let readIndex = start; readIndex >= 0; readIndex-- ) {
    if( arr[readIndex] !== 0) {
        arr[writeIndex] = arr[readIndex];
        writeIndex--;
    }
}
``` 
The second loop will start at the beginning now and swap each value with a zero up until it reaches the **writeIndex** cell which also will get a zero value
```javascript
for (let j = 0; j <= writeIndex; j++) {
    arr[j] = 0;
}
```
To finish, we can now simply return the updated array
```javascript
return arr;
```
The complete code:
```javascript
const moveZeroesLeft = function(arr) {
    let writeIndex = arr.length - 1;
    let start = writeIndex;

    for(let readIndex = start; readIndex >= 0; readIndex-- ) {
        if( arr[readIndex] !== 0) {
            arr[writeIndex] = arr[readIndex];
            writeIndex--;
        }
    }

    for (let j = 0; j <= writeIndex; j++) {
        arr[j] = 0;
    }

    return arr;
}
```
We can verify that this works with the statements and the output below:
```javascript
let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes left --------\n');
console.log(moveZeroesLeft(arr));
// outputs to console
[0, 0, 0, 0, 1, 9, 8, 4, 2, 7, 6]
```
### [Optimized] Move Zeroes Right
The code to have the zeroes at the right is following the same logic as the previous one. 

The main difference is that the **readIndex** and **writeIndex** will start at the beginning of the array instead of the end. 

No need for a step by step then, here is the finished code:
```javascript
const moveZeroesRight = function(arr) {
    let writeIndex = 0;
    const size = arr.length;

    for(let readIndex = 0; readIndex < size; readIndex++) {
        if(arr[readIndex] !== 0) {
            arr[writeIndex] = arr[readIndex];
            writeIndex++;
        }
    }

    for(let j = writeIndex; j < size; j++) {
        arr[j] = 0;
    }

    return arr;
}
```
We can expect and verify the zeroes to be moved to end of the array with the below statements again:
```javascript
let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes right --------\n');
console.log(moveZeroesRight(arr));
// outputs to console
[1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0]
```
## Conclusion
I tried to be thorough in showing you multiple ways to solve this fun challenge. 

I hope you enjoyed the [long] read and more importantly understand both approaches and why one is a better option than the other.