TutorialStudyMite

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

Sstudymite1 min read

Beginner friendly

Track completion, mastery, and revision.

Brute Force Approach

Using Sorting

Sort the given array using sort function.

TC – O(NlogN)

SC – O(1)

Better Approach

Using Hashmap

Keep the occurrence 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 occurrence 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 occurrence 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;
}