Array Three Keys Sorting (Sort Colors) Leetcode

Problem: 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
 
 Technique 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. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

Solution: