Top K Frequent Elements
Last Updated: March 29, 2026
Understanding the Problem
We have an array of integers that may contain duplicates, and we need to find which elements appear most often. Specifically, we want the top k by frequency. The order of the output doesn't matter, which gives us some flexibility in how we collect results.
The core challenge boils down to two steps: counting how often each element appears, and then efficiently selecting the k elements with the highest counts. The first step is straightforward with a hash map. The interesting part is that second step, because how you select the top k determines whether your solution is O(n log n), O(n log k), or O(n).
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, O(n log n) works but the follow-up explicitly asks us to beat it. This nudges us toward O(n log k) or O(n) solutions.-10^4 <= nums[i] <= 10^4→ Values fit in a small range (20,001 distinct values max). This means the number of unique elements is bounded, which matters for frequency counting.kis valid and the answer is unique → We don't need to handle ties or invalid k values.
Approach 1: Sort by Frequency
Intuition
The most natural approach: count how often each element appears, then sort by frequency and grab the top k. Almost everyone thinks of this first, and it works perfectly well.
We use a hash map to count frequencies in one pass. Then we sort the unique elements by their frequency in descending order. The first k elements in the sorted list are our answer.
Algorithm
- Build a hash map
freqwhere each key is an element fromnumsand the value is its count. - Collect all unique elements (the keys of the map).
- Sort these unique elements by their frequency in descending order.
- Return the first
kelements from the sorted list.
Example Walkthrough
Code
- Time Complexity: O(n log n). Counting frequencies takes O(n). Sorting the unique elements takes O(m log m) where m is the number of unique elements, and in the worst case m = n.
- Space Complexity: O(n). The frequency map stores up to n entries, and the sorted list uses O(m) space.
This approach works but sorts all unique elements when we only need the top k. What if we tracked just k elements as we process the frequencies?
Approach 2: Min-Heap
Intuition
Instead of sorting all unique elements, we can maintain a min-heap of size k. The heap always holds the k most frequent elements seen so far. When we encounter a new element, we compare its frequency to the smallest frequency in the heap. If it's larger, we evict the minimum and insert the new one.
The trick is using a min-heap (not a max-heap). A min-heap lets us efficiently find and remove the least frequent element among our current top k candidates. When a new element has higher frequency than the heap's minimum, the minimum gets evicted, which is exactly what we want.
Algorithm
- Build a frequency map from
nums. - Create a min-heap that orders elements by their frequency.
- For each unique element, add it to the heap. If the heap size exceeds k, remove the minimum.
- After processing all unique elements, the heap contains exactly the k most frequent elements.
- Extract all elements from the heap into the result array.
Example Walkthrough
Code
- Time Complexity: O(n log k). Counting frequencies is O(n). For each of the m unique elements, we do a heap operation costing O(log k). Since m <= n, the total is O(n log k).
- Space Complexity: O(n). The frequency map uses O(n) space. The heap uses O(k) space. Total is O(n).
The heap approach is efficient, but every unique element still requires a log k operation. What if we could distribute elements by frequency without any sorting or heap operations at all?
Approach 3: Bucket Sort
Intuition
Here's the key insight: the maximum frequency any element can have is n (the length of the array). So we can create an array of "buckets" where bucket[i] holds all elements that appear exactly i times. Then we just walk from the highest bucket down, collecting elements until we have k.
This eliminates sorting and heap operations entirely. The bucket array has size n+1, and placing elements into buckets is O(1) per element. Walking the buckets from the end takes at most O(n) steps. The whole thing runs in O(n) time.
Algorithm
- Build a frequency map from
nums. - Create an array
bucketsof size n+1, wherebuckets[i]is a list of elements with frequency i. - Place each unique element into its corresponding bucket based on its frequency.
- Iterate from the highest index (n) down to 1. For each non-empty bucket, add its elements to the result.
- Stop once we've collected k elements.
Example Walkthrough
Code
- Time Complexity: O(n). Counting frequencies is O(n). Creating and filling the buckets is O(n). Walking the buckets to collect k elements visits at most n+1 indices. Everything is O(n).
- Space Complexity: O(n). The frequency map uses O(n) space. The bucket array has n+1 slots, and the total elements stored across all buckets is the number of unique elements.