Top K Frequent Elements
LeetCode 347 • Medium • Arrays & Hashing
Given nums and k, return the k most frequent elements. Bucket sort: index = frequency.
TimeO(n)count + bucket collect
SpaceO(n)count + buckets
Bucket i: —
Result: —
Ready
Press Play. Count frequencies with a hash map, build buckets (index = freq), then collect from highest bucket down until we have k elements.
TimeO(n)count + recursive collect
SpaceO(n)count + buckets + call stack
Recursive: collect(i) — base when i < 1 return; for each num in freq[i] append to res, if len(res)==k return; recurse collect(i-1).
3
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Bucket sort (freq[i] = nums with count i) O(n) · O(n)
① COUNT
count = Counter(nums)
② BUILD BUCKETS
freq = [[] for _ in range(len(nums)+1)]
for num, cnt in count.items(): freq[cnt].append(num)
③ COLLECT HIGH TO LOW
res = []
for i in range(len(freq)-1, 0, -1):
for num in freq[i]: res.append(num); if len(res)==k: return res
④ RETURN
return res
▼ your implementation ▼
Verify your solution: