Top K Frequent Elements
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Two passes: first count frequencies into a hash map. Then walk the (value, count) pairs, keeping the top k by count in a min-heap. Whenever the heap exceeds size k, pop the smallest count — what remains is the answer.
nums = [5, 2, 5, 4, 2, 5, 7, 4], k = 2[5, 2]import heapq
def top_k_frequent(nums, k):
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
heap = []
for val, c in freq.items():
heapq.heappush(heap, (c, val))
if len(heap) > k:
heapq.heappop(heap)
return [v for _, v in heap]function topKFrequent(nums, k) {
const freq = new Map();
for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);
const heap = new MinHeap((a, b) => a[0] - b[0]);
for (const [val, c] of freq) {
heap.push([c, val]);
if (heap.size() > k) heap.pop();
}
return heap.toArray().map(p => p[1]);
}class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (var e : freq.entrySet()) {
heap.offer(new int[]{ e.getValue(), e.getKey() });
if (heap.size() > k) heap.poll();
}
int[] out = new int[k];
for (int i = 0; i < k; i++) out[i] = heap.poll()[1];
return out;
}
}vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int x : nums) freq[x]++;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
for (auto& [val, c] : freq) {
heap.push({c, val});
if ((int)heap.size() > k) heap.pop();
}
vector<int> out;
while (!heap.empty()) { out.push_back(heap.top().second); heap.pop(); }
return out;
}Explanation
This is a two-step problem: first figure out how often each value appears, then keep only the k most frequent. A min-heap of size k is a tidy way to track the current top contenders.
We start by counting frequencies into a hash map freq, so each distinct value maps to its count. Then we walk those (count, value) pairs and push each into a min-heap keyed by count.
The clever part is that we cap the heap at size k: whenever it grows past k, we pop the smallest count. Because the heap's top is always the weakest of the kept entries, anything popped cannot belong to the final answer. After processing everything, the heap holds exactly the top k values.
Example: nums = [5, 2, 5, 4, 2, 5, 7, 4], k = 2. Counts are 5:3, 2:2, 4:2, 7:1. As we push pairs and trim to size 2, the smallest counts (like 7:1) get popped, leaving 5 and one of the twos, so the answer is something like [5, 2].
Keeping the heap at size k instead of sorting everything is why this runs in O(n log k), which is faster when k is much smaller than the number of distinct values.