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 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 or a first best guess on a working solution, then we will tackle the recommended way to have a point of comparison.
Video here
Brute Force - First solution
My first intuition could be broken down into the steps below:
- Get the size of the current array
- Create a second array the size of the first one and fill with zeroes
- Filter out all zeroes from the first array which will maintain the order of the non zero items
- Take the difference of lengths between the first array and the filtered array to get the offset index
- 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
- If the zeroes need to be at the start, replace the items starting from the offset to the end.
- 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:
const moveZeroes = ( arr, dir = 'end') => {
}
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
const size = arr.length;
- Create a second array the size of the first one and fill with zeroes
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
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
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
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.
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:
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:
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
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
const moveZeroesLeft = function(arr) {
}
Then we declare two local variables to hold a writeIndex and a start position
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
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
for (let j = 0; j <= writeIndex; j++) {
arr[j] = 0;
}
To finish, we can now simply return the updated array
return arr;
The complete code:
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:
let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes left --------\n');
console.log(moveZeroesLeft(arr));
[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:
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:
let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes right --------\n');
console.log(moveZeroesRight(arr));
[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.
Share in the comments any feedback and alternate solutions and don't forget to stay tuned for more 😃
![[JavaScript] - How to craft intuitive and self-documenting code](/_next/image?url=https%3A%2F%2Fcdn.hashnode.com%2Fres%2Fhashnode%2Fimage%2Fupload%2Fv1560165621261%2Fe1O7D622C.jpeg&w=3840&q=75)