MoveZeroes.md

Move Zeroes

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.

Solution signature: void moveZeroes(int[] nums)

Try it on LeetCode.

Strategy

We'll need to scan the input array while keeping track of first "free" index where we can insert the next non zero element we encounter. In this context, free is where a zero elements used to be.

When we're done scanning the array the range [0,index) will contain all the non zero elements. Therefore, we can fill the range [index, end) with zeros to end up with an array where all the zero elements have been moved to the end.

(Leet)Code

Following is a top voted solution from LeetCode:

public void moveZeroes(int[] nums) {
  int i = 0;
  for (int n : nums) {
    if (n != 0) {
      nums[i++] = n;
    }	         
  }
  while (i < nums.length) {
    nums[i++] = 0;
  }
}

It's clean indeed, but could use a little structure.

(Clean)Code

public void moveZeroes(int[] nums) {  
  int nonZeroBoundary = moveNonZeroesToStart(nums); // check
  fillZeroes(nonZeroBoundary, nums); // mate
}

moveNonZeroesToStart takes care of moving all non zero integers to the start of the array, and returning the first index after the last non zero integer:

private int moveNonZeroesToStart(int[] nums) {
  int nonZeroIndex = 0;
  for (int num : nums) {
    if (num != 0) {
      nums[nonZeroIndex++] = num;
    }
  }
  return nonZeroIndex;
}

fillZeroes makes sure to fill the remainder of the array with zeros, like so:

private void fillZeroes(int start, int[] nums) {
  for (int i = start; i < nums.length; i++) {
    nums[i] = 0;
  }
}

Separation of concerns vs. Efficiency

A keen reader may find somewhat of an inefficiency in the above code, as it may end up scanning the input array twice, when potentially once could have sufficed. If we are willing to trade off separation of concerns for efficiency, the following code would do the trick:

public void moveZeroes(int[] nums) {
  int writeIndex = 0;
  for(int i = 0; i < nums.length; i++) {
    if(nums[i] != 0) {
      swap(nums, writeIndex++, i);
    }
  }
}

private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}