To see the youtube video where I draw out how each algorithm works (recommended), please click here.
Problem Statement
Given an array of integers, move all zeroes to the end of the array. Ideally, use no extra space, and keep the nonzero elements stable (meaning the order is preserved).
Attempt #1: Keep Moving Zeroes To The Right  Stable  O(N^2) Time  O(1) Space
A simple algorithm is to go through the array from left to right, and every time you encounter a zero, you search the rest of the array for a nonzero to swap with. However, this approach has a bad Time complexity O(N^2) so it's not good.
Here's some pseudocode showing how you'd implement this:
Stable: Yes
Time: O(N^2) Space: O(1) Attempt #2: Place Elements Into New Array  Stable  O(N) Time  O(N) Space
An easy approach to this question is to create a new array, and place all nonzero elements into it. Then fill the remainder of the new array with zeroes. This approach takes O(N) extra space, so it's not ideal.
Here's some pseudocode showing how you'd implement this:
Stable: Yes
Time: O(N) Space: O(N) Attempt #3 (Best): Special Index Tracking  Stable  O(N) Time  O(1) Space
The ideal solution is a bit tricky. The idea is to go through the array and move all nonzero elements to the left. Where on the left do we write each nonzero element too? We'll keep track of that index basically by counting how many nonzeroes we saw so far. This is the ideal solution because the Time complexity is O(N) and the Space complexity is O(1).
Here's some C++ code for how you'd implement this:
Stable: Yes
Time: O(N) Space: O(1) Edge Cases
The complete code for this project can be found on my algorithm questions and answers repo on github here.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Comments are closed.

AuthorHi, I'm srcmake. I play video games and develop software. Protip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.
