https://leetcode.com/problems/top-k-frequent-elements/

I love this problem – its not that hard to solve sub-optimally, but the optimal solution is super elegant.

Counting frequency of each number and then sorting the array by the frequency of each number would be the most straightforward approach – but there are multiple ways of doing that!

#1. Simple sort:
Count the frequency of each number. Create an array of pairs -> {number, count} -> sort this array of pairs using the frequency. Return the first k results of this sorted array. This would be fairly easy to code up within 15 mins or so in an interview. However, this would be O(n log n) since we are sorting the entire array – when in fact we only need the first K elements.

[#2. Min heap] -> This only works if your language has a min heap data structure. Swift does not, and I would not venture coding one up during an interview. But this is a neat solution to propose since it fixes the issue with the first approach – instead of sorting the entire array, this solution uses a min heap to pop the current ‘least’ frequent number – since the heap does not grow beyond size k – we improve the time complexity to O(N log k).

#3. Bucket sort – by far the best solution. The key insight here is the fact that the frequency of any number cannot be higher than N -> this allows us to use an Array to store numbers at an index equal to their frequencies. Which also means we do not need to sort – instead we can just reverse iterate the array – the numbers with maximum frequency will be stored at the back of the array. And just like that we have a O(N) solution.