# Top K Most Frequent Elements and Bucket Sorting Intuition

Bucket Sort Solution: https://leetcode.com/problems/top-k-frequent-elements/solutions/5032156/beats-96-39-of-users-with-java-simple-well-explained-bucket-sorting-hashmap-solution/ I was attempting to solve this problem in less than O(nlogn) time. I read through the solution involving 'bucket sort' and although the approach makes sense to me because using an array where indices = frequencies avoids sorting, I seem to be having trouble intuitively or logically going from 'I should first make a frequency hashmap. Now, how do I more efficiently find top k elements without sorting' to ' I should use a bucket array!' (Or it seems like I often have trouble coming up with the right data structures for these efficient solutions myself even with if I understand the solution after).

• (Practice. Practice. Practice. Don't get stuck on any one problem - once you're confident you've understood the problem, don't spend an undue time finding one (more) solution. Turn to something else, maybe returning to this problem later on.) Commented Jun 11 at 10:48
• (How do you come up with an algorithm? was the first good question by a lecturer that I remember. He doesn't know, I'm none the wiser.) Commented Jun 11 at 11:02

Call the mapping value→count a histogram. (If there are $$m \le n/\log n$$ entries, you have time for an $$m\log m$$ processing step).)
(While $$n$$ is a ceiling for value frequency, one could keep the max thereof for a smaller array / less processing.)
One pertaining intuition may be once the distinct values are ordered in descending frequency, just report the first $$k$$ - works, but then, there are Selection algorithms not relying on (complete) ordering.
(I find "heapselect" intuitive: construct a max heap on frequencies, stop reporting after $$k$$ values.)