Top K Frequent Elements
Given an integer array and an integer k, return the k values that occur most often. The answer is guaranteed unique and should be found faster than sorting all distinct values by frequency.
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ number of distinct values
- -10^4 ≤ nums[i] ≤ 10^4
- "k most" of something
- Frequencies come from a hash map first
- Keep only the best k candidates while streaming through the rest
When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.
Count occurrences in a hash map. Push each (count, value) into a min-heap keyed by count; when the heap size exceeds k, pop the smallest. After processing all distinct values the heap holds the k most frequent. Because the heap never grows past k, each push/pop costs O(log k).
- Bucket sort by frequency (buckets 1..n) yields O(n) time and space. Quickselect on the distinct counts is O(d) expected.