Top K Frequent Elements
MediumHeap · HashingO(n log k) time · O(n) space
The problem
Given an array and a number k, return the k most frequent elements.
nums = [1,1,1,2,2,3], k = 2 → [1, 2]Stuck? Open one hint
Counting is the easy half. For the second half, do you need the whole sorted order or just the top k?
Show the worked solution
Count frequencies in a map — that part is obvious. The interesting choice is how you pick the top k.
- Sort the counts — O(n log n). Fine, and worth saying first.
- Min-heap of size k — O(n log k). Push each entry; when the heap exceeds k, drop the smallest. Better when k is much smaller than n.
- Bucket by frequency — O(n), since frequency cannot exceed n. The optimal answer if they push you.
Walking through all three in that order shows how you think about trade-offs, which is the real purpose of this question.
fun topKFrequent(nums: IntArray, k: Int): List<Int> {
val counts = HashMap<Int, Int>()
for (n in nums) counts[n] = (counts[n] ?: 0) + 1
val heap = java.util.PriorityQueue<Map.Entry<Int, Int>>(compareBy { it.value })
for (entry in counts.entries) {
heap.offer(entry)
if (heap.size > k) heap.poll()
}
return heap.map { it.key }.reversed()
}O(n log k) time · O(n) space
