Move all zero values in a big array to its front portion in a Time Efficiency way

0 votes
asked Jun 9, 2010 by didxga

You're given a big array with Integral type value, How do you move all zero values within it to the front portion of the array in a Time Efficiency way?

e.g. 0,1,72,3,0,5,9,0,6,51,0,3 ---> 0,0,0,0,1,72,3,5,9,6,51,3

Regards!

7 Answers

0 votes
answered Jun 9, 2010 by guffa

If you want to keep the order between the other items, loop backwards copying all non-zero items, then fill up with zero items at the beginning:

int source = arr.Length - 1;
int dest = arr.Length - 1;
while (source >= 0) {
  if (arr[source] != 0) {
    arr[dest--] = arr[source];
  }
  source--;
}
while (dest >= 0) arr[dest--] = 0;

If the order of the items is not important, you can simply swap zero items with items at the beginning of the array:

int dest = 0;
for (int source = 0; source < arr.Length; source++) {
  if (arr[source] == 0) {
    arr[source] = arr[dest];
    arr[dest++] = 0;
  }
}

Both algorithms are O(n).

(Examples in C#, but it should be close enough as it's mostly a question about algorithms...)

0 votes
answered Jun 9, 2010 by dty

If the final order is not important, then a simple sort will do the job too.

0 votes
answered Jun 20, 2013 by cshir

For the case when order is important, a minor optimization. You don't even need the second pass of the array; you can just zero out as you copy the non-zero items to the end. Something like:

int counter = 0;
for (int i = a.length-1; i >= 0; i--) {
    if (a[i] != 0){

    a[a.length-1-counter] = a[i];
    a[i] = 0;
    counter++;
    } 
}

Where a is the array. O(n), 1 pass.

0 votes
answered Jun 23, 2013 by joy-jedi

Although I see Guffa has already given the solution and mine is also essentially doing the same thing (1 pass O(n)). I am sharing it here since i too have written it.

int counter = arr.length - 1;        
int swapPosition = arr.length - 1;
while (counter >= 0) {
    if(arr[counter] != 0){
        swap(arr, counter, swapPosition);
        swapPosition--;
    }
    counter--;
}

swap(int[] arr, int indx1, int indx2){
    int t = arr[indx1];
    arr[indx1] = arr[indx2];
    arr[indx2] = t;
}
0 votes
answered Jun 28, 2014 by rajesh-kumar

We can move all zeros in order of o(n). The idea is to move all the number along with their corresponding positions and put zero after shifting the numbers on the newly available indexes.

   private static int[] reArrangeNonZeroElementInBack(int arr[]) {
            int count = arr.length - 1;
            int len = arr.length;
            if (len == 0)
                return arr;
            for (int i = len - 1; i >= 0; i--) {
                if (arr[i] != 0) {
                    arr[count--] = arr[i];

                }
            }
            for (; count >= 0;) {
                arr[count--] = 0;``

            }
            return arr;
        }
0 votes
answered Jun 14, 2015 by hiren-patel

I have done this way:

Integer array:

int [] mArray = {0,3,6,0,3,9,5,2,0};

Call method for move all zero element to end of array:

moveAllZerosElementToEndOfArray(mArray);

Add this method:

private void moveAllZerosElementToEndOfArray(int arr[])
    {
        int count = 0;  // Count of non-zero elements
        // Traverse the array. If element encountered is non-zero, then
        // replace the element at index 'count' with this element
        for (int i = 0; i < arr.length; i++)
            if (arr[i] != 0)
                arr[count++] = arr[i]; // here count is incremented

        // Now all non-zero elements have been shifted to front and 'count' is
        // set as index of first 0. Make all elements 0 from count to end.
        while (count < arr.length)
            arr[count++] = 0;

        for (int i = 0; i < arr.length; i++) {
            Log.i(TAG, ""+arr[i]);
        }
    }

Hope this will help you.

0 votes
answered Jun 29, 2015 by mohit-motiani

Here's an attempt:

public class MoveAllZeroToRight {

/**
 * @param args
 * You are given an integer array which contains some zeros. 
 * Move the zeros to the right side of the array with minimum number of swaps. 
 * The order of the original array can be destroyed.
 */
 public static void main(String[] args) {
    int[] a = {1,3,0,2,6,0,0,3,0,4,0,8};
    a = moveAllZerosToRight(a);
    for(int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
 }
 public static int[] moveAllZerosToRight(int[] a){
    int i=0;
    int j=a.length-1;
    while(i<j){
        if(a[i]==0 && a[j]!=0){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;j--;
        }
        else{
            if(a[i]!=0)
                i++;
            if(a[j]==0)
                j--;
        }
    }
    return a;
 }
}
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...