Today I want to check out an algorithm that I’ve seen a lot of sites recommend people practice for potential technical interviews. Move Zeroes is listed as an easy problem on Leetcode but it definitely can be tricky, so let’s take a look.
The Problem
As pictured above, the prompt asks us to write a function that takes in an array and gives us back the same array, but with all the zeroes pushed to the back of the array. It also specifies that we must do this in-place, meaning we don’t create any extra objects to help us with this, thus maintaining a space complexity of O(1).
The space complexity makes this extra tricky, as creating a copy of the array via slice or other array methods would be a bit easier. So with that in mind, let's think about what we need to do to rearrange the array in-place.
A Solution
We will definitely some type of loop to iterate over the array in order to determine which element is a zero and what isn’t. But what happens when we find a zero? We need to keep track of how many zeros we find, so we know how many elements at the end of the array we need to rearrange, or reassign, as a zero. We also need to reassign any zero to the next non-zero adjacent number. So with that in mind, I believe it’s best to use a counter, which will keep track of all the non-zeroes we find. As we loop through the array, we will reassign each non-zero to the value of index seen at the last non-zero, and increment our counter as we go. Then, when we have finished our for loop, we will set up another one that will iterate over the array again, starting at the final value of counter, and changing each value from that index on to zero.
Our time complexity is an acceptable O(n+m) since it is dependant on two unnested loops, all while maintaining our important O(1) space complexity. I hope this comes in handy as you study your algos!
