Shifting zeros to end in an array

Given an array with sorted numbers and zeros in between them, than how could we rearrange the array such that all the zeros are placed at end in O(1) space complexity.

ex: I/p: 3 0 0 4 0 5 0 6 7 8 0 0 9
o/p: 3 4 5 6 7 8 9 0 0 0 0 0 0
Method1 :

int* shiftZeroToEnd(int *a, int n) // n is size of array
{
  int i,firstZero = -1;
  for(i=0;i<n;i++) // finding where first zero exists
  {
    if(a[i]==0)
    {
     firstZero=i;
     break;
    }
  }
  if(firstZero== -1) // no zeros in array
      return a;
  for(i=firstZero+1;i<n;i++)
  {
      if(a[i]!=0)
      {
        swap(a,i,firstZero); //swapping a[i] with a[firstZero]
        firstZero++;
      }
  }
  return a;
 }

Method 2 :

Here is another solution in O(n)

int * shiftZeroToEnd(int *a,int n)
{
int pos = 0, i, count_zero;

for(i = 0; i <= n-1; i++)
{
     if(a[i] != 0) {
         a[pos] = a[i];
         pos++;
     }
}
for(i = n-1; i >= pos; i--)
    a[i] = 0;
return a;
}

If there is any better way to implement this algorithm, please do comment.

4 Thoughts on “Shifting zeros to end in an array

  1. Input Arr[] = {0,1,5,0,0,4,7,0,2}, Size = 9;

    int i = 0, j = Size – 1;
    while ( i != j ){

    if( a[i] == 0 && a[j] == 0 ){
    j–;
    }
    else if( a[i] == 0 && a[j] != 0 ){
    Swap( a[i] , a[j] );
    i++;
    j–;
    }
    else if( a[i] != 0 && a[j] == 0 ){
    i++;
    j–;
    }
    else if( a[i] != 0 && a[j] != 0 ){
    i++;
    }
    }

  2. P Karthik on September 13, 2014 at 10:58 am said:

    import java.util.Scanner;
    import java.lang.*;
    /**
    *
    * @author PKS
    */
    public class Endzero {

    public static void main(String[] args)
    {
    Scanner sc = new Scanner(System.in); // TODO code application logic here

    System.out.println(“Enter the Array Size: “);

    int size = Integer.parseInt(sc.nextLine());

    int arr[] = new int[size]; // used to store array element

    for(int i=0;i<size;i++)
    arr[i] = Integer.parseInt(sc.next());

    int k=0; // used to store non zero values starting from zero'th index
    // of an array
    for(int j=0;j=k) // store zero when j greather then k
    arr[j]=0; // after completing loop all zero moved back
    }

    for(int i=0;i<size;i++)
    System.out.print(arr[i]+" ");
    }
    }

    Output:
    Enter the Array Size:
    5
    1 0 2 0 3
    1 2 3 0 0

  3. Shobhank on October 21, 2014 at 3:55 am said:

    int z = a.length-1;
    for(int i=0;i<z;i++){
    while(a[i] == 0 && a[z] == 0){
    z–;
    }
    if(a[i] == 0){
    a[i] = a[z];
    a[z] = 0;
    z–;
    }
    }

  4. Parminder Kumar Bharti on May 31, 2015 at 12:09 pm said:

    #include
    #include

    void shiftZeorsAtEnd(int Arr[],int size)
    {
    int j,N;
    j=0;
    N=size-1;
    int newArr[20];

    for(int i=0;i<size;++i)
    {
    if(Arr[i] != 0)
    newArr[j++]=Arr[i];
    else
    newArr[N--]=Arr[i];

    }

    printf("Output is \n");

    for(int i=0;i<size;++i)
    printf("%d ",newArr[i]);

    }

    main()
    {
    int Arr[]={1,0,0,9,1,0,8,0,6,0,25,35,0,0,11};

    shiftZeorsAtEnd(Arr,15);
    getch();
    }

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation