Rearranging array elements depending on their indexes

Question

I am (still!) going through these CodingBat exercises for Java. Here is the one I have just done:

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.

And here is my code:

 public int[] zeroFront(int[] nums){
 int zeroCount = 0;
 int[] resultantArray = new int[nums.length];
 int[] noZerosArray = new int[nums.length];
 //Count zeros
 for (int i = 0; i < nums.length; i++) {
 if (nums[i] == 0) {
 zeroCount++;
 }
 }
 //Make an array without any zeros
 int j = 0;
 for (int i = 0; i < nums.length; i++) {
 if(nums[i] != 0){
 noZerosArray[j] = nums[i];
 j++;
 }
 }
 //To resultant array, add zeros first, then add remaining numbers of original
 for (int i = 0; i < resultantArray.length; i++) {
 if (i < zeroCount) {
 resultantArray[i] = 0;
 } else {
 resultantArray[i] = noZerosArray[i-zeroCount];
 }
 }
 return resultantArray;
}

Please bear in mind I am doing it without importing anything extra like java.util.Arrays etc., as , primarily, this is not accepted by the assessor and, secondarily, I want to get to grips with arrays without importing anything extra yet.

Regarding my code, I would like to know how this can be improved. Is this a good solution? It feels like it could be more efficient, bearing in mind I have three for loops and creating three extra arrays.

Even though this one seems trivial, I found it really difficult!

Answer 1

The trick you are missing here is a simple swap.

All you need to do is keep a "fast" and a "slow" index in the array. The "fast" index scans forwards looking for 0 values. The "slow" index is an insert-point for where the next 0 would belong.

Consider this loop:

public int[] zeroFront(int[] nums){
 int slow = 0; // next zero inserted here
 for (int fast = 0; fast < nums.length; fast++) {
 if (nums[fast] == 0) {
 nums[fast] = nums[slow];
 nums[slow] = 0;
 slow++;
 }
 }
 return nums;
}

That loop finds all zero values and then swaps non-zero values with them from the beginning of the loop, ending with a situation where the zeros are all at the front.

Sometimes, tricks like these are really hard to spot, but, when pointed out, make you think: Neat!

• alanbuchanan: This is so clever!

Answer 2

The swap method in the other answer is the approach I would use, however there is a similar answer that more resembles your approach so I thought it would be worth sharing.

The method will be to build the array of non-zero elements and fill in the rest after. The trick is that if we do it backwards we can get the correct output in-place.

int j = nums.length-1;
for(int i = nums.length-1; i >= 0; i--)
{
 if(nums[i] != 0)
 {
 nums[j--] = nums[i];
 }
}
for(; j >= 0; j--)
{
 nums[j] = 0;
}

Answer 3

Something that I noticed was that you had two separate loops, one for zeros and one for non-zeros, when you really only need one loop

//Count zeros
for (int i = 0; i < nums.length; i++) {
 if (nums[i] == 0) {
 zeroCount++;
 }
}
//Make an array without any zeros
int j = 0;
for (int i = 0; i < nums.length; i++) {
 if(nums[i] != 0){
 noZerosArray[j] = nums[i];
 j++;
 }
}

int j = 0;
for (int i = 0; i < nums.length; i++) {
 if (nums[i] == 0) {
 zeroCount++;
 } else {
 noZerosArray[j] = nums[i];
 j++;
 }
}