Wednesday, October 16, 2013

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.