Array Three Keys Sorting LeetCode (Sort Colors)

Given an array that contains three different elements, sort the array efficiently. Assuming that keys take one of three values, reorder the array so that all objects with the same key appear together. 

The order of the subarrays is not important. For example, [1,1,1,2,2,3,3,3] and [2,2,1,1,1,3,3,3] and [3,3,3,1,1,1,2,2] and so on are valid answers.

 NOTE: Use O(1) additional space and O(n) time
 
 Solution 1:

•  scan the array and store the element,count in a map
•  iterate through the keys of the elements and replace the value of the original array by the item from the map
• Complexity: O(n)
• Space: O(1) - the size of hash is equal to the number of unique elements (=3 in our case)

This is a variant of array sorting problem that is popular in StackOverFlow, StackOverFlow - Grouping array, GeeksForGeeks, and LeetCode

Solution: