Move zeros at end of array

Move zeros to end of array

This is very commonly asked interview problem and requires bit comfort with array indixes to solve it. Problem statement is : given an array which contains random numbers, including zeros. We have to move zeros at the end of the array. For example input array is
move zeros at end

Output array is
move zeros at the end

Move zeros at the end of array

Basic idea is to scan through array, whenever we find a zero, move all successive elements accordingly. We wont be moving all elements every time we hit zero. Trick is similar to problem where we delete specific characters from a string. For complete explanation refer to this post.
For above example, at some point, below will be state of array and other variables

By the time we reach at the end of the array, we may have difference between the last element of the array and size of given input array. That will be the number of zeros in input array. Fill all those spots with zero.

Move zeros to end implementation

#define MAX_ELEM 10
void move_zeroes(int a[], int size){
    int i, dest = 0;

    for(i =0; i<size; i++){
        if(a[i] != 0){
            a[dest++] = a[i];
        }
    }
    for(i= dest; i<size; i++){
        a[i] = 0;
    }
    printf("\n");
    for(i= 0; i<size; i++){
        printf("%d ", a[i]);
    }
}

//Driver program
int main(){
    int a[] = {0,1,3,4,0,0,0,5,6,7};
    int size = sizeof(a)/sizeof(a[0]);
    move_zeroes(a, size);
    return 0;
}

Complexity of algorithm to move zeroes at end of array is O(N).
There is another problem which can be solved with same approach.
Problem is to delete consecutive duplicate elements except from the first in an array. For example, input array is {0,1,1,3,3,5,0,0,6,6} 
Output should be {0,1,3,5,0,6}

void remove_duplicates(int a[], int size){
    int i=0, dest =-1;

    while(i < size-1){
        if(a[i] != a[i+1]){
            if(dest != -1)
            a[dest++] = a[i+1];
        }
        else{
            if(dest == -1)
            dest = i+1;
        }
        i++;
    }
    for(i= 0; i<dest; i++){
        printf("%d ", a[i]);
    }
}

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.

  • mayur

    for(i=0;i<size;i++)
    {
    if(a[i]!=a[i+1]){ temp[i]=a[i]} else
    {

    temp[i]=a[i];i++;
    }}

  • http://www.codinghelmet.com Zoran Horvat

    The solution for moving zeros to the end of the array is optimized and it is often hard for newcomers to understand it.

    You can reach the same solution by starting with inductive hypothesis that subarray can be kept solved at all time, and then extending the subarray one element at the time and preserving the correct state. Later on, the inductive hypothesis can be relaxed and let the array be brought back into correct state after the whole operation.

    You can find the analysis and intermediate solutions here: http://www.codinghelmet.com/?path=exercises/moving-zeros-to-end-of-array

  • Hafeez

    public class RemoveConsecutiveDuplicates {

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

    public static void main(String[] args) {

    // TODO Auto-generated method stub

    int dest = 1;

    for (int i = 1; i < a.length; i++) {

    if (a[i] != a[i-1])

    a[dest++] = a[i];

    }

    for (int i = 0; i < dest; i++) {

    System.out.print(a[i] + " ");

    }

    }

    }