-1
$\begingroup$

Link to Problem: https://leetcode.com/problems/top-k-frequent-elements/description/

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).

$\endgroup$
2
  • $\begingroup$ (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.) $\endgroup$
    – greybeard
    Commented Jun 11 at 10:48
  • 1
    $\begingroup$ (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.) $\endgroup$
    – greybeard
    Commented Jun 11 at 11:02

1 Answer 1

1
$\begingroup$

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).)

Counting sort (bucket sort with bucket size 1) is just one procedure for ordering values known to take O(n+c) time, c being the number of counters/buckets.
No intuition involved, just awareness of this/one such method.
(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.)

$\endgroup$
1
  • $\begingroup$ Thanks so much! I think because I haven't seen bucket sort, I just got nervous that it was a method I should've came up with myself, rather than a method to just learn and know for the future (if I'm getting that right?) Also I agree, heapselect is more intuitive. $\endgroup$
    – penguin365
    Commented Jun 11 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.