Close

Moving zeroes to the end of array

Given an array of elements which contains some zeros in between, we have to write a program to move all zeros to the end without disturbing the original order of the elements.

For example if the input is {0, 6, 2, 0, 0, 3, 1, 0, 4, 5, 0}, the output should be {6, 2, 3, 1, 4, 5, 0, 0, 0, 0, 0}

The algorithm is simple, we take two  indices , one to loop through the entire array, and another to keep track of the non-zero elements. Once we loop through all the elements, we can fill the remaining spaces with zeros.

This algorithm scans the input array only once and hence runs in O(n) time and does not take any extra space O(1).

Here is the Java code to do this.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/13/13
* Time: 9:56 PM
* To change this template use File | Settings | File Templates.
*/
public class MoveZerosDemo {
public static void main(String[] args)
{
int[] array = {6,0,1,0,0,4,3,0,5,2};
moveZerosToEnd( array );
for( int i = 0; i < array.length; i++ )
{
System.out.print( array[i] + " ");
}
}
public static void moveZerosToEnd(int[] array)
{
int resInd = 0;// to keep track of non-zero elements in the final array
int i;
for( i = 0; i < array.length; i++ )
{
if( array[i] > 0 )
{
if( i != resInd ) //Avoid self copy
array[resInd] = array[i];
resInd++;
}
}
//Fill the remaining entries with 0
while( resInd < array.length )
{
array[resInd] = 0;
resInd++;
}
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *