Top k Most Frequent Elements
Problem
Given an array and an integer k, return the k values that appear most often. Any order is acceptable. Solve it in better than O(n log n).
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.
Input
nums = [5, 2, 5, 4, 2, 5, 7, 4], k = 2Output
[5, 2]5 appears 3 times, 2 appears twice, 4 twice, 7 once. Top 2 by frequency are 5 and one of {2, 4}.
import heapq
def top_k(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 topK(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[] topK(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> topK(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;
}