Problem
I am completing the CodingBat exercises for Java, and, having learnt from the answers to the previous one, I completed the one that follows:
Return a version of the given array where all the
10s have been removed. The remaining elements should shift left towards the start of the array as needed, and the empty spaces a the end of the array should be0. So{1, 10, 10, 2}yields{1, 2, 0, 0}. You may modify and return the given array or make a new array.
Here is my code:
public int[] withoutTen(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 10) {
nums[slow] = nums[fast];
slow++;
}
if (fast == nums.length-1) {
for (int i = fast; i >= slow; i--) {
nums[i] = 0;
}
}
}
return nums;
}
Please bear in mind I am doing these 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.
I was taking influence from the comments I received on the previous question, by using a fast and slow variable for looping through the array, and limiting the code to one main for loop, for the sake of making my code generally better and putting efficiency into practice.
How could this be optimised? Is it ok to begin another loop only for the circumstance of fast reaching the last element in the array? It feels like I am repeating myself by saying “if we get to the last element…” because we absolutely will do anyway.
I played around with setting fast outside the loops, so that the second for loop can begin after the first (as opposed to nesting it). At that point, fast would be set to the last value anyway from having completed the previous loop, but more and more values would be set outside the loops. Which way makes more sense?
Solution
First, I would give slow the same scope as fast – give them both loop scope:
for (int slow = 0, fast = 0; fast < nums.length; ++fast) {
Second, rather than creating a new variable i and iterating backwards, I would write my second loop like this:
for (; slow < nums.length; ++slow) {
nums[slow] = 0;
}
Instead of creating a new variable int i = fast and iterating backward until it is equal to slow to set the remaining elements of the array to 0, I just start with the variable in slow and iterate until the end of the array is reached. This will work because the outer loop has finished iterating anyway because once fast == nums.length - 1, we exit the outer loop.
Third, put spaces around your mathematical operator(s) to make it easy to read:
if (fast == nums.length - 1) {
Otherwise, I see nothing wrong with your code, you use reasonable variable names, you use braces around your ifs and loops, and you indent your code nicely.
It’s extraordinarily confusing to have if (fast == nums.length - 1) as a conditional within a loop that continues while fast < nums.count returns true. This is the last part of the loop, and it only executes on the last iteration of the loop… so why is it even in the loop at all?
A couple of comments in our code can help us out. We have two distinct parts:
- Shuffling the non-tens to the front.
- Zero-ing out the tens.
So let’s use comments to mark these in distinct blocks. And, let’s move the second part to its own loop.
And while we’re at it, let’s make the method more generic to replace any number with another given number.
public int[] replaceNum(int[] nums, int eliminationNum, int replaceNum) {
int nextMoveIndex = 0;
// shuffle non-elims to the front
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != eliminationNum) {
nums[nextMoveIndex++] = nums[i];
}
}
// zero out the elimination number
while (nextMoveIndex < nums.length) {
nums[nextMoveIndex++] = replaceNum;
}
return nums;
}
I think you did pretty good job on the algorithm here, as all array elements are checked and only nr-of-10 zeros are appended to the “good” numbers.
The one optimization I would add is to put the if code outside the first loop, so it is not repeated for all array numbers but run only one time after first loop is done. The if check itself is not needed anymore as condition is checked in for loop. In code it will look like below:
public int[] withoutTen(int[] nums) {
int slow = 0;
// put "good" numbers in array head
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 10) {
nums[slow] = nums[fast];
slow++;
}
}
// here we need to zero out array tail
for (int i = slow; i < nums.length; i++) {
nums[i] = 0;
}
return nums;
}
Here is DEMO
To me, the signature of the method and its name implies that it returns a new array.
public int[] withoutTen(int[] numbers)
If the intent is to modify the provided array I would rename it and make it return void.
public void removeTen(int[] numbers)
If we go ahead with the with the non-modifying approach we get a very simple pure function:
public int[] withoutTen(int[] numbers) {
int[] result = new int[numbers.length];
int resultIndex = 0;
for(int number : numbers) {
if(number != 10) {
result[resultIndex++] = number;
}
}
return result;
}
Here’s my solution. I have two solutions, but the first one is better because it doesn’t waste resources.
public int[] withoutTen(int[] nums) {
//Create an ArrayList to add the iterations where ten is.
ArrayList<Integer> tenPlaces = new ArrayList<Integer>();
//Get the place where the tens
//Create a return array to manipulate, set initally to nums.
int[] ret = nums;
for (int i = 0; i < ret.length; i++)
{
//If we find a number that is not a ten, we add it's place to the ArrayList
if (ret[i] != 10)
{
tenPlaces.add(i);
}
//Otherwise, if it is ten, we change it to zero.
else
{
ret[i] = 0;
}
}
//Sort the return array by using the ArrayList.
for (int i = 0; i < tenPlaces.size(); i++)
{
int temp = ret[i];
ret[i] = ret[tenPlaces.get(i)];
ret[tenPlaces.get(i)] = temp;
}
//Finally return ret;
return ret;
/*
Other Solution
int size = nums.length;
int tenAmt = 0;
ArrayList<Integer> foo = new ArrayList<Integer>();
for (int i = 0; i < size; i++)
{
if (nums[i] == 10)
{
tenAmt++;
}
else
{
foo.add(nums[i]);
}
}
int amtLeft = size - tenAmt + 1;
for (int i = 0; i < amtLeft; i++)
{
foo.add(0);
}
int[] ret = new int[size];
for (int i = 0; i < size; i++)
{
ret[i] = foo.get(i);
}
return ret;
*/
}