Codingbat challenge: zeroFront Stream API Solution

Question

Given the task zeroFront notAlone from CodingBat:

Return an array that contains the exact same numbers as the given array, but rearranged so that all the zeros are grouped at the start of the array.

The order of the non-zero numbers does not matter. So {1, 0, 0, 1} becomes {0 ,0, 1, 1}. You may modify and return the given array or make a new array.

zeroFront([1, 0, 0, 1])      →   [0, 0, 1, 1]
zeroFront([0, 1, 1, 0, 1])   →   [0, 0, 1, 1, 1]
zeroFront([1, 0])            →   [0, 1]

My solution to this problem throws an ArrayIndexOutOfBoundsException in some cases:

public int[] zeroFront(int[] nums) {
  if (nums.length == 0) {
    return nums;
  }
  
  int[] zeroFront = new int[nums.length];
  int zeroCounter = 0;
  
  for (int i = 0; i < zeroFront.length; i++) {
    if (nums[i] == 0) {
      zeroCounter++;
    }
  }
  
  for (int i = 0; i < zeroCounter; i++) {
    zeroFront[i] = 0;
  }
  
   
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] != 0) {
      zeroFront[zeroCounter + i] = nums[i];
    }
  }
  
  return zeroFront;
}

My questions are the following:

What can be done in order to fix my solution?

How is it possible to solve this task using Stream API ?

Answer 1

The index of zeroFront is incorrect. It should not be zeroCounter + i, but rather zeroCounter + nonZeroCounter, where nonZeroCounter is the number of non-zeroes seen so far. Note that this is no equal to i, which is the total number of all zeroes and non-zeroes seen so far.

To fix it, just keep another count of the non-zeroes:

int nonZeroCount = 0;
for (int num : nums) {
    if (num != 0) {
        zeroFront[zeroCounter + nonZeroCount++] = num;
    }
}

Also note that the loop to set the first nonZeroCounter elements of zeroFront to 0 is not necessary. The elements of an int array are initialised to 0 automatically.

For the stream solution, you can make use of the fact that false is ordered before true, and sort the array by x != 0:

public static int[] zeroFrontStreams(int[] nums) {
    return Arrays.stream(nums).boxed().sorted(Comparator.comparing(x -> x != 0)).mapToInt(x -> x).toArray();
}

But note that since this involves sorting, its time complexity is worse compared to your O(n) solution. There is also much boxing/unboxing involved.

Alternatively, if you just want to use streams somewhere in your code, you can use it to separate the array into zeroes and non-zeroes, then copy the non-zeroes to the tail of zeroFront in some other way:

public static int[] zeroFrontStreams(int[] nums) {
    var partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(x -> x == 0));
    int[] zeroFront = new int[nums.length];
    int[] nonZeros = partitions.get(false).stream().mapToInt(x -> x).toArray();
    int zeroCounter = partitions.get(true).size();
    System.arraycopy(nonZeros, 0, zeroFront, zeroCounter, nonZeros.length);
    return zeroFront;
}

Without (un)boxing, but with some code duplication of Arrays.stream(nums).filter:

public static int[] zeroFront(int[] nums) {
    int[] zeroFront = new int[nums.length];
    long zeroCounter = Arrays.stream(nums).filter(x -> x == 0).count();
    int[] nonZeros = Arrays.stream(nums).filter(x -> x != 0).toArray();
    System.arraycopy(nonZeros, 0, zeroFront, (int)zeroCounter, nonZeros.length);
    return zeroFront;
}