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 problem is with the final loop. You don't want to append the number of zeros to the current position, because this will obviously will result in an index of out bounds exception. You are traversing the whole array. What you can do is to increment zeroCounter as such:

public static 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 num : nums) {
        if (num != 0) {
            zeroFront[zeroCounter++] = num;
        }
    }

    return zeroFront;
}

If you want to use streams, you could do something like this:

public int[] zeroFront(int[] nums) {
    Map<Boolean, List<Integer>> partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(i -> i == 0));
    List<Integer> result = new ArrayList<>(partitions.get(true));
    result.addAll(partitions.get(false));
    return result.stream().mapToInt(i -> i).toArray();
}

As @Alexander Ivanchenko pointed out in the comments, this can be further optimised to get rid of the intermediate result list:

public static int[] zeroFrontStream(int[] nums) {
    Map<Boolean, List<Integer>> partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(i -> i == 0));
    return Stream.concat(partitions.get(true).stream(), partitions.get(false).stream()).mapToInt(i -> i).toArray();
}

Keep in mind, the solution with streams might not be as performant, since there is a lot boxing and unboxing going on. We also have to do conversion between collections and arrays.

Answer 2

This task can be fulfilled with Stream IPA in a single stream statement and without need to resort to sorting by using a custom collector.

To create a collector we can make use of the static method Collector.of(). We need to provide the mutable container that would be used internally by the collector, and specify also the way how elements of the stream should be added to the container and how to merge the two containers in case of the parallel execution.

In the code below, ArrayDeque is used as a mutable container. It's an array-backed collection that allows to insert a new element in constant time O(1) at the back and at the front.

Because we can't gain any advantage from parallel execution, combiner function is implemented to throw an AssertionError.

Finisher function transforms the underlying collection into an array.

This code passes all test on CodingBat:

public int[] zeroFront(int[] nums) {
    return Arrays.stream(nums)
        .boxed()
        .collect(Collector.of(
            ArrayDeque::new,
            (Deque<Integer> deque, Integer next) -> {
                if (next == 0) deque.addFirst(next);
                else deque.addLast(next);
            },
            (left, right) -> { throw new AssertionError("should not be processed in parallel"); },
            deque -> deque.stream().mapToInt(Integer::intValue).toArray()
        ));
}

To run this code on CodingBat you need to use the fully-qualified name java.util.stream.Collector.

Your mistake is rooted in the line zeroFront[zeroCounter + i] = nums[i];. Instead, you need to increment zeroCounter with each new assignment, as already shown in the answer by Ervin Szilagyi.

Also, for loop below is redundant because when an array int[] would be allocated memory all its elements will be initialized with the default value of 0:

for (int i = 0; i < zeroCounter; i++) {
    zeroFront[i] = 0;
}

Answer 3

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;
}

Answer 4

As other people have already pointed out your mistake, here's another way to solve this problem using streams with the teeing collector (this was added in java 12, not sure what version of java codingbat is running):

public int[] zeroFront(int[] nums) {
    return Arrays.stream(nums).boxed().collect(
            Collectors.teeing(
                    Collectors.filtering(n -> n == 0, Collectors.toList()),
                    Collectors.filtering(n -> n != 0, Collectors.toList()),
                    (zeros, nonZeros) -> Stream.concat(zeros.stream(), nonZeros.stream())
                            .mapToInt(Integer::intValue)
                            .toArray()
            ));
}