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.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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++; | |
} | |
} | |
} |