Move 0's to end of array

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.


Two choices come to mind

  1. Create a new array of the same size, then Iterate over your current array and only populate the new array with values. Then fill the remaining entries in the new array with "zeros"

  2. Without creating a new array you can iterate over your current array backwards and when you encounter a "zero" swap it with the last element of your array. You'll need to keep a count of the number of "zero" elements swapped so that when you swap for a second time, you swap with the last-1 element, and so forth.

[Edit] 7 years after originally posting to address the "ordering" issue and "last element is zero" issues left in the comments

public class MyClass {

    public static void main(String[] args) {

        int[] elements = new int[] {1,0,2,0,3,0};

        int lastIndex = elements.length-1;

        // loop backwards looking for zeroes
        for(int i = lastIndex; i >=0; i--) {
            if(elements[i] == 0) {
                // found a zero, so loop forwards from here
                for(int j = i; j < lastIndex; j++) {
                    if(elements[j+1] == 0 || j == lastIndex) {
                        // either at the end of the array, or we've run into another zero near the end
                        break;
                    }
                    else {
                        // bubble up the zero we found one element at a time to push it to the end
                        int temp = elements[j+1];
                        elements[j+1] = elements[j];
                        elements[j] = temp;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(elements));
    }
}

Gives you...

[1, 2, 3, 0, 0, 0]

Basic solution is to establish an inductive hypothesis that the subarray can be kept solved. Then extend the subarray by one element and maintain the hypothesis. In that case there are two branches - if next element is zero, do nothing. If next element is non-zero, swap it with the first zero in the row.

Anyway, the solution (in C# though) after this idea is optimized looks like this:

void MoveZeros(int[] a)
{

    int i = 0;

    for (int j = 0; j < a.Length; j++)
        if (a[j] != 0)
            a[i++] = a[j];

    while (i < a.Length)
        a[i++] = 0;

}

There is a bit of thinking that leads to this solution, starting from the inductive solution which can be formally proven correct. If you're interested, the whole analysis is here: Moving Zero Values to the End of the Array

Tags:

Java

Arrays

Recent Posts