Moving zeros

Last day I was thinking about all possible ways I could find to solve the following problem:

Given an array of random integers, move all the zeros in the array to the end of the array.

At first it seemed like a pretty simple problem, but the challenge also stated:

Try to keep this in O(n) time (or better)!

Ok. Things just got more interesting.

This challenge came from cassidoo's newsletter and every week, she post a new interview question. If you're not subscribed to it yet, I really encourage you to do so.

After taking some time to think about it, I came across several ways of solving the problem, going from procedural to functional styles. I thought it'd be interesting to share, so here we go:

Bubbling

This approach is based on the bubble sort algorithm and the idea is to "bubble up" zeros to the end of the array.

function moveZeros(input) {
  for (let i = 0, lastZeroIndex = -1; i < input.length; i++) {
    const n = input[i];

    if (n === 0 && lastZeroIndex < 0) {
      lastZeroIndex = i;
      continue;
    }

    if (n !== 0 && lastZeroIndex >= 0) {
      input[lastZeroIndex++] = n;
      input[i] = 0;
    }
  }

  return input;
}

We store variable lastZeroIndex which points to the last zero position. When we encounter a number which is non zero, we swap that value with the last position found.

This algorithm performs in O(n) time and is the most efficient I could came up with. It's written in procedural style and mutates the original array, but when talking about performance, mutation is usually the fastest option.

Recursion

Being a big fan of functional programming, this is my favorite one. The idea is to split input array into first and rest parts. If first item is zero, we move it to the end and delegate rest part to the next moveZeros call. If not, we just keep it at its current position.

function moveZeros([first = null, ...rest]) {
  switch (first) {
    case null:
      return [];
    case 0:
      return [...moveZeros(rest), first];
    default:
      return [first, ...moveZeros(rest)];
  }
}

Another version using pattern matching proposal:

const moveZeros = (input) => case (input) {
  when [] -> [];
  when [0, ...rest] -> [...moveZeros(rest), 0];
  when [number, ...rest] -> [number, ...moveZeros(rest)];
}

I'm obviously biased, but I find it the most readable solution of all of them. Performance is not the key point of this approach, as it creates lots of intermediate arrays in the process. Also recursion can be a problem with big arrays (though it can be solved using tail call optimization)

Grouping

This approach filters numbers in two arrays, zeros and non-zeros, then arrays are flattened into one, pushing zeros to the right:

function moveZeros(input) {
  input
    .reduce(
      (groups, number) => {
        const [nonZeros, zeros] = groups;

        if (number === 0) {
          zeros.push(0);
        } else {
          nonZeros.push(number);
        }

        return groups;
      },
      [[], []]
    )
    .flat();
}

Splice

Another one, this time using splice to insert numbers and zeros in their corresponding place. This method is partially based on how insertion sort algorithm works:

function moveZeros(input) {
  let output = [];
  let lastZeroIndex = 0;

  for (const number of input) {
    output.splice(number === 0 ? lastZeroIndex : lastZeroIndex++, 0, number);
  }

  return output;
}

Sort

And the last one, using sort. In the end moving zeros is nothing more than sorting numbers, right? Here we use a compare function that, when comparing a zero with another number, will put zero after the other number. Otherwise will preserve original order.

function moveZeros(input) {
  return input.sort((_, number) => (number === 0 ? -1 : 0));
}

This internally may use quick sort algorithm, which performs in O(n * log n)

Conclusion

One of the things I like the most about programming is the so many ways we have to solve a given problem. And with every solution, we learn new ways to approach future ones.