CareerCup

one possible solution could be just count the number of zero one and twos.
And overwrite the whole array with 0 ,1 or 2

Another way could be to pick up first '1' as a pivot element and do a quick sort over the array.

1 option is much better. It is counting sort and happens in linear time.

first option(counting) is much better. It is counting sort and happens in linear time.

linerly traverse the array and add the number to the link list and keep track of the pointer to the last 0 , 1 and 2

Keep on appending the numbers and update the last pointers.

Thus, O(n)

Option 1 is bad since the complexity is O(N^2), first traverse each item to count number of 0s, 1s and 2 and then again tarverse the array to set 0,1 and 2 in correct position.

Option 2: Quick sort or Merge Sort will give N(LogN) complexity.

Option 3: Using a Linked List: best performance since it will be O(n), however it needs extra spaces for the Linked List and also for the 0,1,2 s pointer. However, the question mentioned 'Overwrite the whole array', so considering that fact we have to rewrite the Array by traversing the Linked List.

So, so far the Sort( Qucik or Merge )is a better solution that the others.

Keep track of 0's index (start at zero and increment when 0 found)
Keep track of 2's index (start at end of array, decrement when 2's found)
Keep count of 1's,
loop 0's index < 2's index

fill 1's from 0's index to 2's index

This is same as Dutch Flag Algorithm.

what wud be the ans when there is an order constraint(means u dont have to change the order of 0's and 1's).
This one is actual question asked by Amazon..

Dutch National flag complexity O(n).

#include <stdio.h>
#define MAX 11
// Solution seed by Sandy Grace, NN Priya, Vaishnavi, Prabhakar Dhandapani
// Nurtured, Manured, Weeded, Harvested by Sridhar Arumugasamy
void main( void ) {
    int arr[MAX] = {0,1,2,0,1,2,0,1,2,0,1},ctr,stop;
    for ( ctr = 0 ; ctr < MAX ; ctr++ )
    stop= arr[ctr] > 3  ? (arr[ arr[ ctr] % 3 ] += 3) : (arr[arr[ctr]] += 3) ;
    stop = arr[2] / 3;
    for ( ctr = MAX ; ctr >= MAX - stop ;  ctr-- ) arr[ctr] = 2 ;
    stop += arr[1] / 3 ;
    for ( ; ctr >= MAX - stop ; ctr -- )          arr[ctr] = 1;
    for( ; ctr > -1 ; ctr-- ) 	                 arr[ ctr ] = 0 ;
 }

public class Sort012 {
public static void main(String[]args){
int arr[]={2,1,2,1,1,0,1,0,1,0,1,0,1,0,1,2,0,1,0,2,0,1};
System.out.println(Arrays.toString(arr));
int[] pivots = {0,1,2};
int start=0;
for (int i = 0; i < pivots.length; i++) {
start =sort012(arr,pivots[i],start);
}



System.out.println(Arrays.toString(arr));
}

private static int sort012(int[] arr,int pivot,int startIndex) {
int p=startIndex-1;
for(int i=0;i<arr.length;i++){
if(arr[i]==pivot){
p++;
swap(arr,i,p);
}
}
return p+1;


}

private static void swap(int[] arr, int k, int i) {
int temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;

}
}

This can be solved by traversing the array and keeping two indexes i and j to point to location where next 0 and 2 is going to be placed.
Code is given below :-

// Sort an array containing 0s, 1s and 2s.cpp : Defines the entry point for the console application.
// Program to sort an array containing 0s, 1s and 2s only

#include<iostream>

void swap(int* num1, int* num2)
{
	int nTemp = *num1;
	*num1 = *num2;
	*num2 = nTemp;
}

int main()
{
	int nArray[] = {1, 2, 0, 0, 1, 2, 2, 2, 1, 1, 0, 0, 2, 1, 1};
	int nLength = sizeof(nArray) / sizeof(int);

	int i = 0;
	int j = nLength - 1;
	int k = 0;

	while(k < j)
	{
		if(nArray[k] == 0)
		{
			if(k != i)
			{
				swap(nArray + i, nArray + k);
			}
			k++;
			i++;
		}
		else if(nArray[k] == 2)
		{
			swap(nArray + j, nArray + k);
			j--;
		}
		else
		{
			k++;
		}
	}

	std::cout << "Array after segegating 0s, 1s and 2s\n";
	for(int i = 0; i < nLength; i++)
	{
		std::cout << nArray[i] << std::endl;
	}

	return 0;
}