Solving: moveZerosToEnd
In this article, I’ll be breaking down the moveZerosToEnd problem in a few different ways in Javascript. I’ll walk through my process of solving the problem and discuss its BigO.
Let’s begin!
Question
Given a static-sized array of integers arr, move all zeroes in the array to the end of the array. You should preserve the relative order of items in the array.
We should implement a solution that is more efficient than a naive brute force.
Examples:
input: arr = [1, 10, 0, 2, 8, 3, 0, 0, 6, 4, 0, 5, 7, 0]
output: [1, 10, 2, 8, 3, 6, 4, 5, 7, 0, 0, 0, 0, 0]Constraints:
- [time limit] 5000ms
- [input] array.integer
arr→ 0 ≤ arr.length ≤ 20 - [output] array.integer
Let's analyze the problem. What we’re doing is pretty simple in concept, if there is a zero value before a non-zero value move the zero value behind it while keeping the relative order of the non-zero values.
Let's think of a few approaches:
Approach 1:
One thought would be to loop through the array and push any non-zero value into a nonZero array and any zero value into an onlyZeros array. Then to spread both of the arrays within a new array with the nonZero array being spread first.
Approach 2:
Another thought would be to loop through the array and when we hit a zero to pause and then continue to search through the array until we hit a non-zero. At this point, we can swap the two values and eventually return an array with all the zeroes at the end.
Let’s see how these two approaches could compare:
Approach 1
Through lines 37 — 47 we can see the nonZeros and zeroes arrays being instantiated and filled through a simple forLoop with an if statement filtering the values into the two arrays.
On line 48 we create a new array combining the two arrays with the spread operator.
Lastly, since we want to return the same array that was given to us, we loop through the given argument again and replace each value with the corresponding value given the index.
The time complexity boils down to O(n) while the space complexity does the same.
If you came up with this approach — well done! Simple and effective!
Approach 2
We see here immediately that we have a nested loop. The first loop iterates through the array checking each value to see if it is equal to 0. If so, we enter another iteration starting at i+1 a.k.a the next value a.k.a ‘j’. If the next value is also zero, the loop will continue until it meets a non-zero value or ends the rest of the loop. Once j hits an index with a non-zero value, we store those values in iVal and jVal respectively and swap the values at the i index and j index.
Now the logic behind this is sound. We’re looping through, pausing at a zero value, and searching for the next non-zero value and swapping their positions.
So if you found this solution that’s great. Nothing wrong there.
However, it currently runs at O(n²)… How can we make it more efficient?
Well, we clearly want to get rid of the nested loop. So let's see what the loops are really doing here.
The first loop pauses at zero values. The second loop pauses at non-zero values.
So the essential pieces we really need to know are the indices of the current zero value (first loop) and the next non-zero value (nested loop).
How do we do that?
Introducing ‘Pointers’.
We can create variables that will ‘point’ to the indices we are concerned with and allow us to swap the values at those indices to get the desired results. While escaping the nested loop!
Approach 2 — Optimized
This approach uses ideas similar to quickSelect by partitioning the array by non-zero-ness. What we’ll do is, iterate through the array and when we meet a non-zero value, increase the ‘write’ pointer as well as the ‘read’ pointer, if we do not hit a non-zero value, we will continue to increase the ‘read’ pointer, and the ‘write’ pointer will stay at the most left-handed zero’s index. Therefore, tracking the indices with a zero value as we continue to read the array’s value. As we hit non-zero values, we will swap the values for the ‘read’ and ‘write’ indices.
It’ll look something like this:
Notice that for indices 0–2 the values for arr[read] and arr[write] will be the same, so when you ‘swap’ them you’re just replacing the same value to the array’s index.
Once we hit a zero value, the write pointer stays pointing to the value’s index. While the read pointer continues.
Once the read pointer hits a non-zero value, it will swap the value at its index with the value at the index stored in the write pointer.
Now that we’ve visualized it a bit. Let's look at the code.
We can see here that we’ve simplified the first version of this approach to a single loop with a single if statement to check if the read value is non-zero.
By declaring the write pointer and incrementing only during non-zero values we’ve replaced the need for a nested loop, and can instead simply continue reading the values and wait until we find an index with a non-zero value to swap the values of the indices.
The time complexity simplifies from O(n²) to O(n) while the space complexity stays at a lovely constant time of O(1) since no additional space is required but the pointers read and write.
Conclusion
I think it's helpful to see how different approaches can still provide usable results, and I hope this breakdown also illustrates that regardless of what logic you use to solve the problem, there is still a way to employ that logic in an inefficient/naive manner — meaning, if you’ve followed your logic and landed on a not-so-efficient piece of code, chances are that there is a more efficient way to write it out using the same logic. So it's not your sense of logic! It's just your first draft of a solution and it’ll get more refined with each pass!
Hope this helps!
