02
Intuition
Count first, then select. A size-k min-heap over (frequency, value) picks the k biggest counts in O(n log k) — or bucket-by-frequency does it in O(n) flat, since a frequency can't exceed n.
03
Approach
1
Count with a hash map
One pass builds value → frequency. All selection happens on the (much smaller) distinct set.
2
Heap-select the top k
Stream (freq, val) pairs through a size-k min-heap exactly like Kth Largest — smallest frequency guards the gate.
3
Bucket alternative
Index buckets by frequency 1..n, drop each value into bucket[freq], then read buckets from the top until k values are collected — O(n).
04
Solution & live demo
python
▶1from collections import Counter
▶2import heapq
▶3
▶4class Solution:
▶5 def topKFrequent(self, nums, k):
▶6 freq = Counter(nums)
▶7 return [v for _, v in heapq.nlargest(k, ((f, v) for v, f in freq.items()))]
05
Edge cases
k equals the number of distinct values
Every value is returned; order among them is free.
Ties at the k boundary
Problem guarantees a unique answer set — ties never straddle the cut.
06
Complexity
Time
O(n log k)
Space
O(n)
Counting O(n); selection over distinct values.