Top K Frequent Elements
Top K Frequent Elements is a medium heaps problem solved with the composite comparator pattern.
The best approach, bucket sort by frequency (o(n)), runs in O(n) time and O(n) space.
Below are 3 approaches in Java, from count, then sort by frequency up.
Problem
Return the k most frequent values in an integer array, in any order. The answer is guaranteed to be unique.
Examples
Example 1
- Input
nums = [4, 4, 4, 1, 1, 7], k = 2- Output
[4, 1]
Example 2
- Input
nums = [9], k = 1- Output
[9]
Constraints
1 <= nums.length <= 10^5; the answer is unique.- Better than O(n log n).
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Count, then sort by frequency | O(n log n) | O(n) |
| Min-heap of size k (comparator on frequency) | O(n log k) | O(n) |
| Bucket sort by frequency (O(n)) | O(n) | O(n) |
1Count, then sort by frequency
O(n log n)O(n)Count with a map, sort the distinct values by count descending, take the first k.
- Count; sort entries by value descending; take k keys.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum);
List<Integer> keys = new ArrayList<>(count.keySet());
keys.sort((a, b) -> count.get(b) - count.get(a));
int[] out = new int[k];
for (int i = 0; i < k; i++) out[i] = keys.get(i);
return out;
}
}2Min-heap of size k (comparator on frequency)
O(n log k)O(n)Push (value, count) pairs into a min-heap ordered by count and pop when it exceeds k. What stays are the k most frequent.
- Count with a map.
- Heap comparator: (a, b) -> a[1] - b[1]; offer each entry, poll when size > k.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
heap.offer(new int[] { e.getKey(), e.getValue() });
if (heap.size() > k) heap.poll();
}
int[] out = new int[k];
for (int i = k - 1; i >= 0; i--) out[i] = heap.poll()[0];
return out;
}
}3Bucket sort by frequency (O(n))
O(n)O(n)A count is between 1 and n, so put each value into bucket[count]. Walk buckets from high to low until you have k values.
- bucket[c] = list of values with count c.
- For c from n down to 1, add values until k are collected.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum);
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) bucket.add(new ArrayList<>());
for (Map.Entry<Integer, Integer> e : count.entrySet()) bucket.get(e.getValue()).add(e.getKey());
int[] out = new int[k];
int j = 0;
for (int c = nums.length; c > 0 && j < k; c--)
for (int v : bucket.get(c)) if (j < k) out[j++] = v;
return out;
}
}Edge cases to test
- k equals the number of distinct values
- Negative values
Hints
Hint 1
Count frequencies, then either keep a size-k heap ordered by frequency (a composite comparator) or bucket values by their count.
FAQ
What is the best time complexity for Top K Frequent Elements?
Bucket sort by frequency (O(n)) runs in O(n) time and O(n) extra space.
Which pattern does Top K Frequent Elements use?
It is a heaps problem that uses the composite comparator pattern.
Is there a brute force solution for Top K Frequent Elements?
Yes. Count, then sort by frequency takes O(n log n) time and O(n) space. Count with a map, sort the distinct values by count descending, take the first k.
Which edge cases should I test for Top K Frequent Elements?
k equals the number of distinct values; Negative values.