Move 0's to end of array

Question

I need to move all 0's in an array to the end of the array.

Example: [1, 10, 0, 5, 7] should result in [1, 10, 5, 7, 0].

I am open to doing a reverse loop or a regular loop.

I cannot create a new array.

Here is what I have so far:

for (int i = arr.length; i <= 0; --i) {
    if (arr[i] != 0) {
        arr[i] = arr.length - 1;
    }
}

Thanks!

Answer 1

SIZE(n) where n = arr.size, retain ordering:

Create an array that is the same size as the initial array you need to remove 0s from. Iterate over the original array and add each element to the new array provided it is not 0. When you encounter a 0, count it. Now, when you've reached the end of the first array, simply add the counted number of 0s to the end of the array. And, even simpler, since Java initializes arrays to 0, you can forget about adding the zeroes at the end.

---

Edit

Since you have added the additional constraint of not being able to create a new array, we need to take a slightly different approach than the one I've suggested above.

SIZE(1)

I assume the array needs to remain in the same order as it was before the 0s were moved to the end. If this is not the case there is another trivial solution as detailed in Brads answer: initialize a "last zero" index to the last element of the array and then iterate backwards swapping any zeros with the index of the last zero which is decremented each time you perform a swap or see a zero.

SIZE(1), retain ordering:

To move the 0s to the end without duplicating the array and keeping the elements in the proper order, you can do exactly as I've suggested without duplicating the array but keeping two indices over the same array.

Start with two indices over the array. Instead of copying the element to the new array if it is not zero, leave it where it is and increment both indices. When you reach a zero, increment only one index. Now, if the two indices are not the same, and you are not looking at a 0, swap current element the location of the index that has fallen behind (due to encountered 0s). In both cases, increment the other index provided the current element is not 0.

It will look something like this:

int max = arr.length;
for (int i = 0, int j = 0; j < max; j++) {
  if (arr[j] != 0) {
    if (i < j) {
      swap(arr, i, j);
    }
    i++
  }
}

Running this on:

{ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 }

yeilds:

{ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0 }

I made a fully working version for anyone who's curious.