Good C++ solutions to the "Bring all the zeros to the back of the array" interview challenge

Question

I had an interview for a Jr. development job and he asked me to write a procedure that takes an array of ints and shoves the zeroes to the back. Here are the constraints (which he didn't tell me at the beginning .... As often happens in programming interviews, I learned the constraints of the problem while I solved it lol):

• Have to do it in-place; no creating temporary arrays, new arrays, etc.
• Don't have to preserve the order of the nonzero numbers (I wish he would've told me this at the beginning)

Setup:

int arr[] = {0, -2, 4, 0, 19, 69}; 
/* Transform arr to {-2, 4, 19, 69, 0, 0} or {69, 4, -2, 19, 0, 0} 
   or anything that pushes all the nonzeros to the back and keeps
   all the nonzeros in front */

My answer:

bool f (int a, int b) {return a == 0;}
std::sort(arr, arr+sizeof(arr)/sizeof(int), f);

What are some other good answers?

Answer 1

Maybe the interviewer was looking for this answer:

#include <algorithm>
//...
std::partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

If the order needs to be preserved, then std::stable_partition should be used:

#include <algorithm>
//...
std::stable_partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

For pre C++11:

#include <functional>
#include <algorithm>
//...
std::partition(arr, arr + sizeof(arr)/sizeof(int), 
               std::bind1st(std::not_equal_to<int>(), 0));

Live Example

Basically, if the situation is that you need to move items that satisfy a condition to "one side" of a container, then the partition algorithm functions should be high up on the list of solutions to choose (if not the solution to use).

Answer 2

An approach that sorts is O(N*Log₂N). There is a linear solution that goes like this:

• Set up two pointers - readPtr and writePtr, initially pointing to the beginning of the array
• Make a loop that walks readPtr up the array to the end. If *readPtr is not zero, copy to *writePtr, and advance both pointers; otherwise, advance only readPtr.
• Once readPtr is at the end of the array, walk writePtr to the end of the array, while writing zeros to the remaining elements.