Instead of inserting (freq, number) tuples into a heap we can use an array to keep track of numbers and frequencies the following way:
- The array index represents the frequency (we can cap the list at k+2)
- The array value represents the count of numbers with a certain frequency
We can then iterate the list in O(k) time.
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Maximum Distinct Elements (medium) - Grokking the Coding Interview: Patterns for Coding Questions