Practice › Heap & Priority Queue
Top K Frequent Elements
Medium · Heap & Priority Queue · Asked at Amazon, Meta, Google, Microsoft, Yelp
Print the k most frequent values. Order them by frequency (highest first); if two values have the same frequency, the smaller value comes first.
Input
First line: n k. Second line: n integers.
Output
The k values, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ number of distinct values
- -10^4 ≤ a[i] ≤ 10^4
Count with a hash map, then use a heap of size k (or bucket sort by frequency).
Example 1
Input
6 2 1 1 1 2 2 3
Output
1 2
Example 2
Input
1 1 1
Output
1
Hints
- Count every value with a hash map.
- Pick the k best (frequency desc, value asc) with a heap of size k, then output them in that order.
Approach
Build the frequency map. Keep a heap of size k whose top is the worst of the kept entries under the order "higher frequency, then smaller value"; push each (value, count) and pop when the size passes k. Finally sort the k kept entries best-first. Bucket sort by frequency gives O(n) too.
Complexity: O(n + d log k) time · O(d) space (d = distinct values)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_map<int, int> cnt;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
// "better" = higher count, then smaller value; keep the k best, worst on top
auto better = [](const pair<int, int> &a, const pair<int, int> &b) {
return a.second != b.second ? a.second > b.second : a.first < b.first;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(better)> pq(better);
for (auto &e : cnt) {
pq.push(e);
if ((int)pq.size() > k) pq.pop();
}
vector<pair<int, int>> v;
while (!pq.empty()) v.push_back(pq.top()), pq.pop();
sort(v.begin(), v.end(), better);
for (size_t i = 0; i < v.size(); i++) cout << v[i].first << (i + 1 < v.size() ? " " : "\n");
return 0;
}Python solution
import sys
import heapq
from collections import Counter
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
cnt = Counter(data[2 : 2 + n])
best = heapq.nsmallest(k, cnt.items(), key=lambda e: (-e[1], e[0]))
print(*[v for v, _ in best])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < n; i++) cnt.merge(sc.nextInt(), 1, Integer::sum);
Comparator<int[]> better = (a, b) -> a[1] != b[1] ? b[1] - a[1] : a[0] - b[0];
PriorityQueue<int[]> pq = new PriorityQueue<>(better.reversed());
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
pq.add(new int[] {e.getKey(), e.getValue()});
if (pq.size() > k) pq.poll();
}
List<int[]> v = new ArrayList<>(pq);
v.sort(better);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < v.size(); i++) sb.append(v.get(i)[0]).append(i + 1 < v.size() ? " " : "");
System.out.println(sb);
}
}Solve Top K Frequent Elements online · All practice problems