Top K Frequent Elements: Combining Hashing and Sorting
The Prompt
Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order.
Understanding the Problem
First count how often each value occurs — a hash map handles that in one O(n) pass. The real question is what comes after: you need the k highest counts. Sorting the map entries by frequency costs O(n log n); a size-k min-heap improves that to O(n log k). Both are fine answers, but the problem hints that O(n) is possible.
The unlock is a bound on the counts themselves: a frequency can never exceed n, the array length. Whenever values live in a small known range, you can bucket-sort them for free — make an array of buckets indexed by frequency and drop each number into the bucket matching its count.
The Interview Flow
Interviewer
Given an array of numbers and an integer k, how do you find the k most frequent numbers?
Candidate
First, I need to find the frequency of each number. I can use a hash map for this, iterating through the array once. The numbers will be the keys and their frequencies the values.
Interviewer
Okay, so you have the frequencies. What's next?
Candidate
Now I need to find the top k frequencies. I could sort the items from the hash map based on their frequencies in descending order and then take the first k elements. The time complexity would be dominated by the sort, making it O(n log n).
Interviewer
Can we do better than O(n log n)? Sorting all the unique elements might be overkill if k is small.
Candidate
Yes. I can use a min-heap of size k. I would iterate through the frequency map. For each element, I push it onto the heap. If the heap size exceeds k, I pop the element with the smallest frequency. At the end, the heap will contain the top k frequent elements. This would be O(n log k).
Interviewer
That's a great improvement. Is there a way to achieve O(n) time complexity on average?
Candidate
Yes, with Bucket Sort. Since the frequencies range from 1 to n, I can create an array of "buckets" where the index represents the frequency. I can place all numbers with the same frequency in the corresponding bucket. Then, I can iterate backward from the last bucket (highest frequency) and collect elements until I have k elements.
Interviewer
Excellent. The bucket sort approach is very clever. Let's implement that one.
Why does bucket sort beat the heap here?
Frequencies are integers in [1, n], so an array of n + 1 buckets indexed by frequency loses nothing: bucket[f] holds every value that occurred exactly f times. Walking the buckets from index n down to 1 visits values in strictly non-increasing frequency order — so the first k values collected are exactly the k most frequent, no comparisons needed.
Counting is O(n), filling buckets is O(number of distinct values) ≤ O(n), and the reverse walk stops after emitting k values — O(n) total time with O(n) extra space for the map and buckets. The trade versus the heap is more memory and a less flexible structure for a better worst-case bound; saying when you would still prefer the heap (streaming data, huge n with tiny k) is bonus credit.
O(n) Solution using Bucket Sort
- Create a hash map to store the frequency of each number in `nums`. This takes O(n) time.
- Create an array of lists (buckets), where the size is `len(nums) + 1`. The index of this array will represent the frequency of a number.
- Iterate through the frequency map. For each number and its frequency, add the number to the bucket at the index corresponding to its frequency.
- Initialize an empty list for the result.
- Iterate through the buckets array from the end (highest frequency) to the beginning.
- For each bucket that is not empty, add its numbers to the result list. Stop once the result list contains `k` elements.
- Return the result list.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function topKFrequent(nums, k) {
const freqMap = new Map();
for (const num of nums) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
const buckets = new Array(nums.length + 1).fill(0).map(() => []);
for (const [num, freq] of freqMap.entries()) {
buckets[freq].push(num);
}
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
if (buckets[i].length > 0) {
result.push(...buckets[i]);
}
}
return result;
}Explanation
Run nums = [1, 1, 1, 2, 2, 3] with k = 2 through count-then-bucket.
1Count pass: {1: 3, 2: 2, 3: 1}. Sanity check: 3 + 2 + 1 = 6 elements, matching len(nums).
2Buckets indexed by frequency 0..6: value 3 lands in bucket 1, value 2 in bucket 2, value 1 in bucket 3. Scan from the right; the first non-empty bucket is index 3 → take value 1. Result: [1].
3Next non-empty bucket is index 2 → take value 2. Result: [1, 2] now has k = 2 elements — stop and return. Bucket 1 (value 3) is never even reached.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.