Sunday, December 30, 2012

Sort an Array of 0s, 1s and 2s


Given an unsorted array of 0s, 1s and 2s, sort the array such that the 0s appear before the 1s and the 1s appear before the 2s.

e.g: A[0,2,1,1,0,2] --> A[0,0,1,1,2,2].

import java.util.Arrays;

public class SortZerosOnesAndTwos {

 static int[] sortZerosOnesAndTwos(int[] a) {
  if (a.length < 2) {
   return a;
  }
  int len = a.length;
  int sum_1s = 0; // keep track of 1s
  int sum_2s = 0; // keep track of 2s 

  for(int i = 0 ; i < len ; i++) {
   if(a[i] == 1) {
    sum_1s++; 
    a[i] = 0; // Make all the 1s zeros
   }
   else if(a[i] == 2) {
    sum_2s++; 
    a[i] = 0; // Make all the 2s zeros
   }
  }

  // In reverse order place the 2s back into the array
  if(sum_2s > 0) {
   for(int i = 0 ; i < sum_2s ; i++) {
    a[a.length-i-1] = 2;
   }
  }

  // In reverse order place the 1s back into the array
  if(sum_1s > 0) {
   int start = a.length-1 - sum_2s;
   for(int i = 0 ; i < sum_1s ; i++) {
    a[start-i] = 1;
   }
  }

  return a;
 }

 public static void main(String[] args) {
  int[] a2 = {0,0,2,1,1,2,0,0,2,1};
  System.out.println(Arrays.toString(sortZerosOnesAndTwos(a2)));
  // OUTPUT: [0, 0, 0, 0, 1, 1, 1, 2, 2, 2]
 }
}


Time Complexity: O(n+m+l) where:
n - Number of elements in the  array
m - Number of 1s in the array(assuming the array contains any 1s)
l - Number of 2s in the array(assuming the array contains any 2s)

No comments:

Post a Comment