29 April, 2020

Leetcode: https://leetcode.com/problems/top-k-frequent-elements/ Editorial: https://leetcode.com/problems/top-k-frequent-elements/discuss/81602/Java-O(n)-Solution-Bucket-Sort

I will have a list of elements and I need to output the list of most frequently occurring elements.

I liked how this problem can be solved with bucket sort and how simple the solution gets. I solved this problem before by using hashmaps, classes, and priority queue

- Create a hashmap of number and its frequency
- Create buckets of all possible frequencies
- For each element of the hashmap insert the key to the corresponding frequency bucket
- Check the frequency bucket from highest to lowest and keep adding numbers to the final solution

My previous solution took 18ms and this bucketsort solution took 7ms ðŸ¤©

Simply brilliant solution.

#algorithm #data structures