Move all zeros to the left with TDD approach

Question

The task

Given an integer array, move all elements that are equal to 0 to the left while maintaining the order of other elements in the array. Let's look at the following integer array.

After moving all zero elements to the left, the array should look like this. We need to maintain the order of non-zero elements.

0 0 0 1 10 20 59 63 88

My approach, I used TDD and hoped my solution would become just as good as the sample solution.

test('contains no element', () => {
  expect(moveZeroToLeft([])).toStrictEqual(undefined);
});

test('contains only a 0 element', () => {
  expect(moveZeroToLeft([0])).toStrictEqual([0]);
});

test('contains only a non 0 element', () => {
  expect(moveZeroToLeft([1])).toStrictEqual([1]);
});

test('contains more than one element with a 0', () => {
  expect(moveZeroToLeft([1, 0])).toStrictEqual([0, 1]);
});

test('contains more than one element without 0', () => {
  expect(moveZeroToLeft([1, 3])).toStrictEqual([1, 3]);
});

test('contains more than one element with a 0 somewhere in the middle', () => {
  expect(moveZeroToLeft([1, 0, 3])).toStrictEqual([0, 1, 3]);
});

test('contains random number of zeros and non-zero elements', () => {
  expect(moveZeroToLeft([1, 0, 3, 0, 0, 44, 1, 0, 2])).toStrictEqual([0, 0, 0, 0, 1, 3, 44, 1, 2]);
});

My solution

function moveZeroToLeft(arr) {
  if (arr.length < 2) {
    return arr;
  }
  if (arr.some(x => x === 0)) {
    let zeroCounter = 0;
    const res = arr.filter(el => {
      if (el !== 0) {
        return true;
      }
      zeroCounter++;
    });
    const leadingZeros = Array(zeroCounter).fill(0);
    return leadingZeros.concat(res);
  }
  return arr;
}

But the sample solution is much more elegant than mine:

let move_zeros_to_left = function(A) {
  if (A.length < 1) {
    return;
  }

  let lengthA = A.length;
  let write_index = lengthA - 1;
  let read_index = lengthA - 1;

  while (read_index >= 0) {
    if (A[read_index] != 0) {
      A[write_index] = A[read_index];
      write_index--;
    }

    read_index--;
  }

  while (write_index >= 0) {
    A[write_index] = 0;
    write_index--;
  }
};

How could I have come to the sample solution with a TDD approach?

Answer 1

TDD is not for finding "elegant" solutions, but for finding working solutions that cover all edge cases. Without edge cases, solutions are often too naive and in the end won't work.

You missed some edge cases; the task states: "order of other elements in the array" (that are integer). How about Infinity and -Infinity? Are they numbers? :) isNaN(Infinity)?

Another thing is, that beauty lies in the eye of the beholder. For me elegant code, is code, that is easy to grasp and not overly complex. Whenever a problem can be solved in such a generic way, that edge case do not need any special handling this is good code. :)

Speaking of which - your problem is clearly about transforming an array - with JavaScript you have a good set of Array.fns() at you disposal and fat arrow functions. Thus I'd intuitively never use loops, but only array functions.

The original problem sounds very constructed to me - I guess some stupid code interview stuff. I guess it is about thinking of how to find zeros in an array and move them around.

However the solution is quite trivial if you are thinking outside the box (which you are!), that with the elements being numbers, the solution is not about moving around zeros (and thus maintain their reference, if it where not zeros but objects), but in filtering and reconstructing them.

const move_zeros_to_left = function(unsortedArray) {
  const numberOfZeros = unsortedArray.filter(item => item === 0).length;
  const nonZeroArray = unsortedArray.filter(item => item !== 0);
  return [...Array.from({length: numberOfZeros}).fill(0), ...nonZeroArray];
}

Covers all the edge cases and is readable. Your provided sample solution is the worst of all solution, because it neglects the fact, that JavaScript has a rich set of Array functions and thus it is neither readable nor idiomatic and I'd say thus not elegant all. :)

Answer 2

Testing elegance

Testing ignores the method and only focuses on the result. If however you add testing that includes criteria that focus on what you may call the elegant parts of the solution this can help you create better solutions.

Personally elegance is a fit, performant and lean, in that order.

• Fit, it must pass all test.
• Performant it must be as fast and use as little memory as possible.
• Lean, the code must be as compact and neat as possible.

You can test all these and iterate to a more elegant solution. However the last point is subjective and this can be hard to test. Personally I measure lean as number of lines (including empty lines) and the number of tokens used.

The last to criteria are always comparative, one solution compared to another as they have no value in isolation.

The sample solution is in my book is far from elegant

• It is overly verbose, names too long, not using shorthand styles (short circuiting and decremented operators) contains redundant length check at start.
• Poor use of comparisons as it forces type checking for each comparison. >= should use !== 0 as its quicker.
• Has a wasted variable. There is no need for the variable lengthA

One can rewrite the function as

function bubbleDown(arr) {
    var wIdx = arr.length, rIdx = wIdx;
    while (rIdx--) { arr[rIdx] && (arr[--wIdx] = arr[rIdx]) }
    while (wIdx--) { arr[wIdx] = 0 }
}

Slightly faster by avoiding the type checks

function bubbleDown(arr) {
    var w = arr.length, r = w;
    while (r-- !== 0) { arr[r] !== 0 && (arr[--w] = arr[r]) }
    while (w-- !== 0) { arr[w] = 0 }
}

And slower but lean. Sucks that Array.fill is so much slower than a while loop.

function bubbleDown(arr) {
    var w = arr.length, r = w;
    while (r--) { arr[r] && (arr[--w] = arr[r]) }
    arr.fill(0, 0, w);
}

The first two are up to 10% faster (last 30% slower) and easier to read and maintain (if that was important as having passed all tests it never needs to be read or changed), and all 3 are elegant.