Top K Frequent Elements — Step-by-Step Visualization

Algorithm Pattern

Bucket Sort (O(n))

Key Idea

Instead of sorting by frequency (which is $O(n log n)$), we can use Bucket Sort. We first count the frequencies of all elements using a hash map. Then, we create an array of buckets where the index represents the frequency. Each bucket contains a list of numbers that have that frequency. Finally, we iterate through the buckets from highest frequency to lowest and collect the first $k$ elements.

Step-by-Step Approach

1. Create a frequency map `count` for all elements in `nums`.
2. Create an array `freq` of size `len(nums) + 1` where each index is an empty list.
3. For each number and its count in the map, append the number to `freq[count]`.
4. Iterate through `freq` from index `len(nums)` down to 0.
5. Collect the elements in each bucket until we have `k` elements.

Common Gotchas

• The maximum frequency of any element is `len(nums)`.
• Multiple elements can have the same frequency.