Top K Frequent Elements
Find the k most frequent elements using sorting, a min-heap, or bucket sort.
Top K Frequent Elements
Problem: Given an array of numbers, return the k most frequently occurring elements. The answer can be in any order.
Example:
- Input:
nums = [1, 1, 1, 2, 2, 3],k = 2 - Output:
[1, 2](1 appears 3 times, 2 appears 2 times — those are the top 2)
Note
First count how many times each number appears. Then figure out which k numbers appeared the most.
How to Think About It
Starting point: Count frequencies with a hash map, then sort all unique elements by frequency descending, return the first k. O(n log n).
First improvement — heap: Sorting is overkill. You're back to the "top-k" pattern: maintain a min-heap of size k keyed by frequency. The root is always the least frequent element in your current top-k. If a new element has a higher frequency than the root, evict the root and insert the new one. O(n log k).
Second improvement — bucket sort: Frequencies can only range from 1 to n (a number can appear at most n times). Create n+1 buckets where bucket[freq] holds all elements with that exact frequency. Then scan from bucket n down to 1, collecting elements until you have k. O(n).
Which to use? Heap is the standard interview answer — it generalizes to any comparator. Bucket sort is faster but only works when frequencies are bounded by input size.
Brute Force — Count + Sort
View Brute Force
Optimal — Min Heap of Size k
View Optimal Solution
Best — Bucket Sort
View Best Solution
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sort by frequency | O(n log n) | O(n) | Simple, easy to write |
| Min Heap of size k | O(n log k) | O(n) | Better when k is small |
| Bucket Sort | O(n) | O(n) | Fastest — uses frequency as index |