On this page
Description
"The 3 most common error codes today", "the 10 most-viewed pages": these rank distinct values by how often they occur. The raw data may have millions of entries but only thousands of distinct values - so count first, then select among the distinct values.
This skill covers count-then-select: a hash map of counts, then either a size-k heap or buckets indexed by count. It also covers writing the tie rule into the comparator and reading results in the right order. Approximate counting appears briefly, for when the distinct values themselves don't fit in memory.
We'll go from simple to more technical:
- The pattern: count with a map, then keep the k strongest in a min-heap with a tie rule.
- A second flavor: bucket sort by count, which needs no heap and runs in O(n).
- Where frequency ranking shows up (top pages, error codes, trending tags).
- What breaks it: no tie rule, the reversed tie, output order, selecting on raw data.
The approach
Java
int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum); // O(n)
// "weaker" = lower count, or the same count and a LARGER value (smaller values must win ties)
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) ->
!count.get(a).equals(count.get(b)) ? Integer.compare(count.get(a), count.get(b))
: Integer.compare(b, a));
for (int v : count.keySet()) {
heap.offer(v);
if (heap.size() > k) heap.poll(); // evict the weakest
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = heap.poll(); // the heap pops weakest first
return result;
}
Python
import heapq
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
count = Counter(nums) # O(n)
heap = [] # a tuple is the comparator:
for v, c in count.items(): # (count, -v) - lower count, or the same count
heapq.heappush(heap, (c, -v)) # and a LARGER value, is the weaker one
if len(heap) > k:
heapq.heappop(heap) # evict the weakest
result = [-heapq.heappop(heap)[1] for _ in range(len(heap))]
return result[::-1] # the heap pops weakest first
After counting, the heap runs over the d distinct values: O(n + d log k). Two details decide correctness. Ties need a rule, and it belongs in the comparator: if smaller values win ties, then among equal counts the larger value is the weaker one to evict. And a min-heap pops from weakest to strongest, so the result is filled from the back. In Python a tuple takes the comparator's place - (count, -value) sorts weaker entries first - and Counter.most_common(k) is no shortcut here: it breaks ties by first appearance, not by value.
A second flavor: bucket sort by count
Counts range from 1 to n, so values can be bucketed by count and read from the highest bucket down - no heap, O(n) in total:
Java
List<Integer>[] buckets = new List[nums.length + 1]; // buckets[c] = values seen c times
for (var e : count.entrySet()) {
int c = e.getValue();
if (buckets[c] == null) buckets[c] = new ArrayList<>();
buckets[c].add(e.getKey());
}
// walk c from n down to 1, sort each bucket for the tie rule, and take values until you have k
Python
buckets = [[] for _ in range(len(nums) + 1)] # buckets[c] = values seen c times
for value, c in count.items():
buckets[c].append(value)
# walk c from n down to 1, sort each bucket for the tie rule, and take values until you have k
Where you'll see it
Top pages, top error codes, trending hashtags and "most frequent queries" reports are count-then-select. At very large scale the exact count map is replaced by approximate structures (Count-Min sketch plus a heap of candidates, or Space-Saving) that keep memory bounded while tracking the heavy hitters.
Which tool for which job?
| You need | Use |
|---|---|
| Top k by count, k small | count, then a size-k min-heap |
| Top k by count in O(n) | count, then buckets indexed by count |
| Few distinct values | count, then sort the distinct values |
| Heavy hitters in a stream too big to count exactly | Space-Saving or Count-Min with a heap |
| Top k across many servers | merge full counts (or enough candidates), not each server's top k |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No tie rule | equal counts come out in hash order | break ties on the value in the comparator |
| The tie reversed in a min-heap | the value that should win is evicted | the weaker side is the larger value when smaller wins |
| Reading the heap as the answer | weakest first | fill the result from the back |
most_common(k) with a value tie rule | ties come out by first appearance | sort by (-count, value) |
| Heaping the raw array | ranks by value, needless work | count first |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why count first and then select?
Show answer
The question ranks distinct values by frequency. Counting turns it into "the k largest counts" over d distinct values, which is much smaller than the n raw entries - O(n + d log k) instead of working on every repeat.
2. Smaller values win ties. Which value should a size-k min-heap evict among two with equal counts?
Show answer
The larger one - it's the weaker of the two under the tie rule, so the comparator orders equal counts by value descending (Integer.compare(b, a)).
3. How does bucket sort make top-k frequency O(n)?
Show answer
Counts are integers from 1 to n, so each distinct value goes into bucket[count]. Reading buckets from n down to 1 yields values by decreasing frequency without any comparison sort.
Key takeaways
- Count with a map, then select among distinct values.
- A size-k min-heap: O(n + d log k); pop order is weakest first, so reverse.
- Put the tie rule in the comparator - and remember the heap evicts the weaker side.
- Bucket sort by count gives O(n).