Thursday 29 August 2013

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Given a array of 0's,1's and 2's arrange in a way that all 0's come first, then 1's then 2's.

Method 1: (By using sorting)

        void arrange(int []array){
                if(array == null || array.length == 0)
                     return;
java.util.Arrays.sort(a);
}

Time Complexity : O(NlogN)

Method 2: (by counting the 0s, 1s and 2s)

       void arrange(int []array){
                if(array == null || array.length == 0)
                      return;

int countZeros = 0;
int countOnes = 0;
int countTwos = 0;

for(int i = 0; i < a.length; i++){
if(a[i] == 0)
countZeros++;   //count number of  zero
else if(a[i] == 1)
countOnes++;    //count number of  one
else if(a[i] == 2)
countTwos++;    // count number of two
}

for(int i = 0; i < countZeros; i++)
a[i] = 0;          //write zero to array

for(int i = countZeros; i <a.length-countTwos; i++)
a[i] = 1;          //write one

for(int i = countZeros+countOnes; i < a.length; i++)
a[i] = 2;          //write two
}

Time Complexity : O(N)

Method 3 : (By using Dutch flag algorithm)
     For Dutch Flag Algorithm, click here

      void arrange(int []a){
                if(array == null || array.length == 0)
                      return;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

//Traverse the array once to pickup min and max values
for(int i = 0; i < a.length; i++){
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}

int p = 0, q = a.length - 1;
int temp;  //for swapping values

for(int i = 0; i < q; i++){
if(a[i] == min){   //place the min value at the lowest position
temp = a[p];
a[p] = a[i];
a[i] = temp;
p++;
}
if(a[i] == max){   //place the max value at the highest position
temp = a[q];
a[q] = a[i];
a[i] = temp;
q--;
i--;
}
}
}

Time Complexity : O(N)

No comments:

Post a Comment