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

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[0]);
  printSorted012(arr, arrSize);
  return 0;
}

TC – O(N)

SC – O(1)