Top K Frequent Elements
Return the k most frequent elements in the array.
Return the k most frequent elements. The core split is simple: count first, then keep only the top-k frontier with a heap.
Pattern fit
Frequency counting creates candidates, and a heap of size k keeps only the most important ones.
Key observation
The heap should compare by frequency, not by value itself.
Target complexity
O(n log k) / O(n)
How to break down the solution cleanly
Use a frequency map to count each value.
Maintain a min heap of size k based on frequency.
Whenever the heap grows beyond k, pop the smallest-frequency item.
At the end, the heap contains exactly the k most frequent elements.
Walk through one example
Example: nums = [1,1,1,2,2,3], k = 2.
Counts become {1: 3, 2: 2, 3: 1}.
After pushing all pairs and trimming to size 2, the heap keeps 1 and 2.
So the answer is [1, 2] in any order.
Reference implementation
Pythonfrom collections import Counter
import heapq
def topKFrequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
heap: list[tuple[int, int]] = []
for value, frequency in counts.items():
heapq.heappush(heap, (frequency, value))
if len(heap) > k:
heapq.heappop(heap)
return [value for _, value in heap]
Common pitfalls
Pushing raw values instead of (frequency, value) pairs.
Forgetting that the final output order often does not matter.
Common follow-ups
When would bucket sort beat the heap?
How would you stream this problem?
Continue with related problems
Build repeatable depth inside the Heap / Priority Queue cluster before moving on.