This problem was recently asked by Google: Given a list of numbers with only 3 unique numbers (1, 2, 3), sort the list in O(n) time.

Example 1: Input: [3, 3, 2, 1, 3, 2, 1] Output: [1, 1, 2, 2, 3, 3, 3] Challenge: Try sorting the list using constant space.

Idea behind the solution

You just need to apply the Bucket sort to sort any array of numbers in linear time. Since we know there will be only 1, 2 and 3, we will use a constant memory space just to count how many of each we found and then modify the array to be sorted.

Please check the main.js snippet for the solution.

This solution originally posted at: Github by @Murillo2380