{"post":"

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>\nusing namespace std;\n\nvoid printSorted012(int arr[], int arrSize) {\n  int zeroCount = 0,\n    oneCount = 0,\n    twoCount = 0;\n\n  for (int i = 0; i < arrSize; i++) {\n    if (arr[i] == 0) zeroCount++;\n    else if (arr[i] == 1) oneCount++;\n    else if (arr[i] == 2) twoCount++;\n  }\n\n  for (int i = 0; i < arrSize; i++) {\n    if (zeroCount > 0) {\n      arr[i] = 0;\n      cout << arr[i] << \" \";\n      zeroCount--;\n    } else if (oneCount > 0) {\n      arr[i] = 1;\n      cout << arr[i] << \" \";\n      oneCount--;\n    } else if (twoCount > 0) {\n      arr[i] = 2;\n      cout << arr[i] << \" \";\n      twoCount--;\n    }\n  }\n}\n\nint main() {\n  int arr[] = {\n    0,\n    1,\n    1,\n    0,\n    1,\n    2,\n    1,\n    2,\n    0,\n    0,\n    0,\n    1\n  };\n  \n  int arrSize = sizeof(arr) / sizeof(arr[0]);\n  printSorted012(arr, arrSize);\n  return 0;\n}\n

TC – O(N)

SC – O(1)

\n","title":"Sort an array of 0s, 1s, 2s","authorDetails":{"name":"studymite","slug":"admin"},"description":"Sort the given array of 0s, 1s, 2s without using any extra space and in O(n) time complexity.","slug":"sort-an-array-of-0-1-2/","articleId":"636a83417bb1ce5072622b09","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}