This problem is a fun exercise on arrays. Given an array, move all the zeros to the end of the array. Maintain the relative order of all other elements.
I have some familiarity with the C++ standard library, which includes algorithms similar-to-this (but without the relative order). In languages with very explicit memory-management, this is removing elements from the array “in spirit”. In C++, in fact, this is the solution:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
auto new_end = std::remove(std::begin(nums), std::end(nums), 0);
std::fill(new_end, std::end(nums), 0);
}
};
Really line 4 is the answer this problem is looking for. Really what happen is that remove “slides the contents down” to fill up the zeros. The new_end variable stores the end of the newly-shrunken array. However, the length of the original nums is unchanged — it’s up to the programmer (me) to really explicitly request that memory be freed, or otherwise messed with.
This also echoes, in a way even more directly, partitioning algorithms. We want to reorder the contents of nums such that one category of elements (those not equal to 0) are on one side, and the other category is at the other side. Again, C++ has this algorithm directly:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
std::stable_partition(std::begin(nums), std::end(nums), [](int n) { return n != 0;});
}
};
A common critique of code (which I agree with!) is “don’t get too clever with one-liners”. I’ll stress that the above solution, in my mind, is fine because it really is just using the fact that the algorithm is exactly what the problem is asking for. Akin to using the built-in sort method for a question that asks you to sort items. C++ is just a bit verbose.
Say, however, that we don’t have such a partition algorithm. Or that the problem is explicitly asking us to implement a partition algorithm. One trick we can do here is exploit that we know how to create new 0s. In contrast to when our array might container pointers or similar, we can just “remember how many zeros to add in later”. Here’s a Python version, basically of the first C++ solution:
class Solution(object):
def moveZeroes(self, nums):
nextWrite = 0
for nextRead in range(len(nums)):
x = nums[nextRead]
if x == 0:
continue
nums[nextWrite] = x
nextWrite += 1
for zeroOut in range(nextWrite, len(nums)):
nums[zeroOut] = 0
Basically nextWrite serves as new_end, the first for loop is remove, and the second for loop is fill.
Say, however, instead of an array of 0s, we have an array of objects, and we’ve been partitioning them based on whether their, I don’t know, books-checked-out-of-the-library-count was 0. We couldn’t really do the above approach because we couldn’t reconstruct a whole object after-the-fact. A nice sequel problem to consider, basically, how do we “really” implement partition.
PS: This problem can be found in codewars, too. I’d say related questions are collected under array questions, or sorting questions.
Tools and Takeaways
- Moving elements within an array is a common sort of “vocabulary” pattern. Remove, partition, etc., are often building blocks of larger algorithms.
- Sometimes we may break a for-loop up into multiple “ranges”. In our first approach, we go through the “tail” of the input array to zero-out those contents.
- Sometimes we can recreate the same values we care about, but later. We can do this when the values are integers. Sometimes we can’t get away with that, and have to do something more sophisticated.