mediumCodingConceptMidSenior
Return the k most frequent elements from a large stream of values. Why not just sort by frequency?
4 min readUpdated 2026-08-15
Answer
Short answer
Count occurrences, then push counts through a min-heap capped at size k, evicting the smallest whenever the heap overflows. That is O(n log k) rather than the O(n log n) of a full sort, it needs only k items resident at once, and it works on a stream you cannot re-read.
Was this answer helpful?
Likely follow-ups
- The stream has a billion distinct keys. Where does your solution break, and what replaces it?
- Counts are bounded by n. Can you get to O(n) without a heap at all?
- Maintain the running median of the same stream instead. What structure now?
- Your comparator subtracts two counts. What is wrong with that?
Related questions
- You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?mediumAlso on heaps and priority-queue6 min
- Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?mediumAlso on heaps and priority-queue6 min
- Numbers arrive one at a time and after each one I want the running median. How would you keep it?mediumAlso on heaps and priority-queue5 min
- Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.mediumAlso on priority-queue5 min