DSA
Top K Frequent Elements
Summmary approach. Optimal — Time O(n log k), Space O(n).
Practice Link
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Intiution#
We need to find the top K frequent elements in the array.
A brute-force approach would count frequencies and sort, but that takes O(m log m) time, where m-> unique elements.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for (int num : nums)
mp[num]++;
// store into vector
vector<pair<int,int>> freqList;
for (auto &x : mp)
freqList.push_back({x.first, x.second});
// sort by frequency (descending)
sort(freqList.begin(), freqList.end(),
[](pair<int,int> &a, pair<int,int> &b) {
return a.second > b.second;
});
// pick top k
vector<int> ans;
for (int i = 0; i < k; i++)
ans.push_back(freqList[i].first);
return ans;
}
};
- Instead, we:
- Count frequencies using a hash map.
- Use a heap (priority queue) to track the top K elements by frequency.
Max Heap#
Push all (frequency, element) pairs from the frequency map into a max-heap. The heap surfaces the highest-frequency element at the top. Pop k times to collect the top-k. This is simple but uses O(n) heap space and O(n log n) time since all unique elements are pushed.
typedef pair<int,int> pii;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pii> pq;
unordered_map<int,int> mp;
// O(n)
for(int num: nums)
mp[num]++;
//O(nlogn)
for(auto x: mp)
pq.push({x.second, x.first});
//O(k)
vector<int> ans;
for(int i=0;i<k;i++){
ans.push_back(pq.top().second);
pq.pop();
}
return ans;
}
};
Time Complexity: O(n log n)
Space Complexity: O(n)
Min Heap of Size k#
Keep the heap trimmed to exactly k elements — identical to the "Kth Largest" pattern applied to frequency instead of value. For each unique element, push it; if the heap exceeds k, pop the minimum-frequency element. After processing all unique elements, the heap contains precisely the k most frequent ones. Since the heap never grows beyond k, each push/pop is O(log k) rather than O(log n).
typedef pair<int,int> pii;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for(int i=0;i<nums.size();i++)
mp[nums[i]]++;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for(auto x: mp)
{
pq.push({x.second, x.first});
if(pq.size() > k)
pq.pop();
}
vector<int> ans;
while(!pq.empty())
{
ans.push_back(pq.top().second);
pq.pop();
}
return ans;
}
};
Time Complexity: O(n log k)
Space Complexity: O(n)
Summary#
Approach 1 (Max Heap) is simpler but less efficient for large n.
Approach 2 (Min Heap) is more optimized, especially when k << n, since it avoids unnecessary heap storage.
Follow-up: Can you do it without a heap?#
Since the frequency of any element is bounded by n (the array length), you can use bucket sort to achieve O(n) time — no heap needed.
Idea: Create n + 1 buckets where bucket[i] holds all elements that appear exactly i times. Then sweep from the highest-frequency bucket downward, collecting elements until you have k.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
int n = nums.size();
// Step 1: count frequencies
unordered_map<int, int> freq;
for (int num : nums)
freq[num]++;
// Step 2: bucket[i] = list of elements with frequency i
// Index range: 1..n (frequency 0 is impossible)
vector<vector<int>> bucket(n + 1);
for (auto& [num, cnt] : freq)
bucket[cnt].push_back(num);
// Step 3: collect from highest frequency downward
vector<int> ans;
for (int i = n; i >= 1 && (int)ans.size() < k; i--)
for (int num : bucket[i])
ans.push_back(num);
return ans;
}
};
Time Complexity: O(n) — counting + bucketing + collecting are all linear.
Space Complexity: O(n) — frequency map + buckets.
Why does this work? No element can appear more than n times, so n + 1 buckets always suffice. The sweep guarantees we pick in descending frequency order, so the first k elements collected are the top-k.