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

Reimplemented this in Python:

Pythonic way:

lst = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]

for i, val in enumerate(lst):
  if lst[i] == 0:
    lst.pop(i)
    lst.append(0)

print("{}".format(lst))

@dcow's implementation in python:

lst = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]

i = 0                      # init the index value
for j in range(len(lst)):  # using the length of list as the range
  if lst[j] != 0:
    if i < j: 
      lst[i], lst[j] = lst[j], lst[i]  # swap the 2 elems.
  i += 1

 print("{}".format(lst))

Answer 2

Lets say, you have an array like

int a[] = {0,3,0,4,5,6,0};

Then you can sort it like,

   for(int i=0;i<a.length;i++){
    for(int j=i+1;j<a.length;j++){
    if(a[i]==0 && a[j]!=0){
    a[i]==a[j];
    a[j]=0;
    }
    }
    }

Answer 3

public void test1(){

    int [] arr = {0,1,0,4,0,3,2};   
    System.out.println("Lenght of array is " + arr.length);

    for(int i=0; i < arr.length; i++){

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

    for(int x = 0; x < arr.length; x++){
        System.out.println(arr[x]);
    }
}

Answer 4

/// <summary>
/// From a given array send al zeros to the end (C# solution)
/// </summary>
/// <param name="numbersArray">The array of numbers</param>
/// <returns>Array with zeros at the end</returns>
public static int[] SendZerosToEnd(int[] numbersArray)
{
    // Edge case if the array is null or is not long enough then we do
    // something in this case we return the same array with no changes
    // You can always decide to return an exception as well
    if (numbersArray == null ||
        numbersArray.Length < 2)
    {
        return numbersArray;
    }

    // We keep track of our second pointer and the last element index
    int secondIndex = numbersArray.Length - 2,
        lastIndex = secondIndex;

    for (int i = secondIndex; i >= 0; i--)
    {
        secondIndex = i;

        if (numbersArray[i] == 0)
        {
            // While our pointer reaches the end or the next element
            // is a zero we swap elements
            while (secondIndex != lastIndex ||
                numbersArray[secondIndex + 1] != 0)
            {
                numbersArray[secondIndex] = numbersArray[secondIndex + 1];
                numbersArray[secondIndex + 1] = 0;

                ++secondIndex;
            }
            // This solution is like having two pointers
            // Also if we look at the solution you do not pass more than 
            // 2 times actual array will be resume as O(N) complexity 
        }
    }
    // We return the same array with no new one created
    return numbersArray;
}

Answer 5

var size = 10;
var elemnts = [0, 0, 1, 4, 5, 0,-1];
var pos = 0;
for (var i = 0; i < elemnts.length; i++) {
    if (elemnts[i] != 0) {
        elemnts[pos] = elemnts[i];
        pos++;
        console.log(elemnts[i]);
    }
}
for (var i = pos; i < elemnts.length; i++) {
    elemnts[pos++] = 0;
    console.log(elemnts[pos]);
}

Answer 6

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.