C C++ JAVA PYTHON SQL HTML CSS DSA Robotics AWS CODING INTERVIEW PREPARATION

Made with  & Code

# Sort an array of 0s, 1s, 2s

Written By -

## Brute Force Approach

### Using Sorting

Sort the given array using sort function.

TC – O(NlogN)

SC – O(1)

## Better Approach

### Using Hashmap

Keep the occurence count of 0s, 1s and 2s in a hashmap. Then iterate the given array and put all the 0s first, then 1s and then 2s according to the occurence count storedd in hash map.

TC – O(N)

SC – O(N)

## Optimal Approach

Count the number of 0s, 1s, 2s and store it in three diffrent variables respectively. Then iterate the given array and put all the 0s first, then 1s and then 2s according to the occurence count storedd in the variables.

``````#include<bits/stdc++.h>
using namespace std;

void printSorted012(int arr[], int arrSize){
int zeroCount = 0,
oneCount  = 0,
twoCount  = 0;

for(int i = 0; i < arrSize; i++){
if(arr[i] == 0) zeroCount++;
else if(arr[i] == 1) oneCount++;
else if(arr[i] == 2) twoCount++;
}

for(int i = 0; i < arrSize; i++){
if(zeroCount > 0){
arr[i] = 0;
cout<<arr[i]<<" ";
zeroCount--;
}else if(oneCount > 0){
arr[i] = 1;
cout<<arr[i]<<" ";
oneCount--;
}else if(twoCount > 0){
arr[i] = 2;
cout<<arr[i]<<" ";
twoCount--;
}
}
}

int main(){
int arr[] = {0,1,1,0,1,2,1,2,0,0,0,1};
int arrSize = sizeof(arr)/sizeof(arr);
printSorted012(arr, arrSize);
return 0;
}``````

TC – O(N)

SC – O(1)

Related Posts:

Online Compilers