In this article, I will decompose the Move Zeroes Problem on LeetCode. C++ is a deep language with a lot to learn. Experimentation, projects and general development practice will catapult you forward. However, sometimes it is important to step back and review some basic computer science and coding challenges. Doing so has helped me think differently about solving problems and appreciate certain aspects of C++ that are easy to forget. This is a part of the reason why I have been practicing extensively on LeetCode.

The Problem

Click here to access the problem. Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Starter Code

    void moveZeroes(vector<int>& nums) {
        
    }

Breaking It Down

This is not a very difficult problem if you take it one step at a time. However, it is a great problem to practice using modern C++ features and the STL containers.

The goal is to append 0 to the end of the vector while deleting it from the sequence. Luckily we are using a vector which supports random read, write, insertion and deletion. Honestly, if this was a singly linked list it would probably be more difficult. The code below show this basic procedure.

If you are new to C++ then you may not be aware of the C++ STL (Standard Template Library). The STL is a number of in-built C++ function and containers that are important to understand. Included in the STL is a container called a vector. A vector is a resize-able array that gets used constantly in audio.

All STL containers have some standard functions that behave similarly. In the code below, I have used a few of these standard container functions on the vector nums:

  • nums.size() returns the size of the vector.
  • nums.erase() erases a value from a position. However, this position is not an index like nums[i]. This is given in the form of an iterator.
  • nums.begin() is an iterator that points to the beginning of the vector.
  • nums.insert() takes an iterator and a value to insert into the vector.
  • nums.end() is an iterator that points to the end of the vector.

An Initial Solution

    void moveZeroes(vector<int>& nums)
    {
        /*count the number of zeros...*/
        int zerosCount = 0;
        /*loop through vector...
        but the maximum loop point is a
        function of the zerosCount as
        the elements and loop index can
        be affected by the internal
        conditional statement...*/
        for(int i = 0; i < nums.size()-1-zerosCount; i++)
        {
            /*check if number is 0...*/
            if(nums[i] == 0)
            {
                /*erase number...*/
                nums.erase(nums.begin() + i);
                /*append zeros to end...*/
                nums.insert(nums.end(),0);
                /*increment zeros count...*/
                zerosCount += 1;
                /*decrement loop count...*/
                i -= 1;
            }
        }   
    }

Note that the if statement allows us to increment the zerosCount variable. As we have erased a value from the vector, all of the subsequent items have been brought backward by 1 element even though a 0 has been appended to the end. This means that 2 things must happen:

  1. i must be decremented to check if the value in the cell is still valid
  2. The maximum count number in our for loop must be changed. Not all languages allow for this, C++ does. For instance what if we had the following input vector:
[0 1 0]

After having erase the first 0, decremented i, and appending 0 to the end we then have.

[1 0 0]

Then we will look at 1 and then continue with the loop. If we did not make the maximum loop count a function of the zerosCount then we would be stuck in an infinite loop and get a timeout error. This solution seems fine and I do not get any timeout issues.

Remember that good code is an iterative process and it is likely that even this decent solution is not the best possible. In fact, I have seen greatly reduced solutions using a single lambda expression or other more advanced operations. This solution runs close to O(n^2) time and takes O(1) space. While the average test case may run in in less than that; the worst case runs close to O(n^2). Consider this:

[0 0 0 0 0 0 0 0]

Every 0 is moved to the end and the max loop count will decrement. However, every erase command will shift the trailing elements forward by 1. This is done in O(n) time according to the C++ documentation for the vector class. In this worst case scenario we approach O(n^2) time. *at least it seems to be this way to me*

So the question I hand to you is this:

Can we do better?

*most likely yes…*

A Better Solution

A better solution is a bit similar to the methodology of the previous example. Instead of using .erase() we will use .swap() which is another function within the STL that runs in constant time. In order to do this, we need two things:

  1. An index for our current value (looping through the vector…). I will call this the ordinary index.
  2. An index that gets stuck on 0’s and only increments when the ordinary index refers to a non-zero value.

Here is the solution in code:

    void moveZeroes(vector<int>& nums)
    {
        /*loop through vector like normal...*/
        for (int i = 0, j = 0; i < nums.size(); i++)
        {
            /*j is a slower index that only advances
            only when we find a non-zero element...*/
            /*if the current element is not a 0...*/
            if (nums[i] != 0)
            {
                /*swap the values...
                increment the index of j...
                continue with loop...*/
                swap(nums[j++], nums[i]);
            }
        }
    }

Here is what this code is doing…

Let us say that we have an input of:

[1,2,3,4]

In this example, there are no 0’s to swap. As a result, j will always increment in the loop and i will always increment at the end of the loop. It is true that this means that if the last element is non 0, then j will increment to 1 beyond the length of the vector but this is okay. Here is a print-out for the result of each loop:

j: 1  i: 0	nums[j]: 2  nums[i]: 1		1 2 3 4 
j: 2  i: 1	nums[j]: 3  nums[i]: 2		1 2 3 4 
j: 3  i: 2	nums[j]: 4  nums[i]: 3		1 2 3 4 
j: 4  i: 3	nums[j]: 0  nums[i]: 4		1 2 3 4 

Now, let us say that we have an input of:

[0,1,2,3,4]

In this example, j will not increment during the first cycle of the loop. During the second cycle, i is already 1 element ahead of j. But, j is looking at 0 still so we swap the values and increment j. Here is a print-out for the result of each loop:

j: 0  i: 0	nums[j]: 0  nums[i]: 0		0 1 2 3 4 
j: 1  i: 1	nums[j]: 0  nums[i]: 0		1 0 2 3 4 
j: 2  i: 2	nums[j]: 0  nums[i]: 0		1 2 0 3 4 
j: 3  i: 3	nums[j]: 0  nums[i]: 0		1 2 3 0 4 
j: 4  i: 4	nums[j]: 0  nums[i]: 0		1 2 3 4 0 

Now, let us say that we have an input of:

[0,0,1,2,3,4]

In this example, j will not increment during the first cycle of the loop. During the second cycle, i is already 1 element ahead of j but j will not increment. On the third cycle, i is looking at a value of 1 but j is still looking at that first 0. So, we swap the values and increment j. The fourth cycle, j is looking at the second 0 and i is looking at 2. Here is a print-out for the result of each loop:

j: 0  i: 0	nums[j]: 0  nums[i]: 0		0 0 1 2 3 4 
j: 0  i: 1	nums[j]: 0  nums[i]: 0		0 0 1 2 3 4 
j: 1  i: 2	nums[j]: 0  nums[i]: 0		1 0 0 2 3 4 
j: 2  i: 3	nums[j]: 0  nums[i]: 0		1 2 0 0 3 4 
j: 3  i: 4	nums[j]: 0  nums[i]: 0		1 2 3 0 0 4 
j: 4  i: 5	nums[j]: 0  nums[i]: 0		1 2 3 4 0 0 

Notice that this algorithm does not guarantee that the order of the 0’s is maintained while the initial solution did. The upside is that this solution has a space complexity of O(1) and a time complexity of O(n)

Conclusion

I know this was a brief article but I hope this helps new C++ developers understand how to use certain operations to move data around in a vector. It is fairly important when you want to make granular effects. I hope you take the chance to try this problem yourself and I hope you post your improved answer in the comments below.

When practicing, I suggest to use print statements to test your loop at every stage. Make sure your loops are doing what you think they should do and manually test them. If you decide to test this code yourself, feel free to use your own test values for the input vector. But also insert print statements to see what the loop does. Until then:

Be good to each other and take it easy…

-Will ☜(゚ヮ゚☜)


Will Fehlhaber is an Acoustics Engineer and Audio Programmer from the UK and Bay Area.


Related

Liked it? Take a second to support William Fehlhaber on Patreon!

Shopping cart

Subtotal
Shipping and discount codes are added at checkout.
Checkout

Sign up here to learn about our premium courses and more!

 

Thank you for being a part of The Audio Programmer Community!