LeetCode 347 Top K Frequent Elements - Why Naive Fails

Count frequencies with a hash map, then sort all unique elements by their counts. Take the first k.

With nums = [1, 1, 1, 2, 2, 3] and k = 2, you get counts {1: 3, 2: 2, 3: 1}. Sort by value descending: [(1, 3), (2, 2), (3, 1)]. Take top $2$: [1, 2].

Sorting is $O(m \log m)$ where $m$ is the number of unique elements. In the worst case, $m = n$, so this becomes $O(n \log n)$.

Can you do better than $O(n \log n)$?