Top K Frequent Elements
Find the k most common values using bucket sort by frequency, in linear time
Problem Statement
Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Why: 1 appears 3 times, 2 appears twice, 3 appears once
Input: nums = [1], k = 1
Output: [1]Intuition
Step one is unavoidable: count how often each value occurs, with a hash map. That is O(n).
The interesting question is step two — how to pick the k largest counts. There are three answers, and they form a nice ladder.
Three ways to rank by frequency
Sort the counts — O(n log n). Simple, correct, and often good enough.
A min-heap of size k — O(n log k). Push each (count, value) pair and pop whenever the heap exceeds k, so only the top k survive. Better when k is much smaller than n.
Bucket sort — O(n). The winner, and it relies on a constraint that is easy to miss.
The bucket-sort insight
A frequency cannot be arbitrary. If the array has n elements, no value can appear more than n times. So counts live in the bounded range 1 … n.
Whenever a key is a small bounded integer, you can use it as an array index instead of sorting.
Build n + 1 buckets, where buckets[f] holds every value that appears exactly f times. Then walk the buckets from the highest frequency downward, collecting until you have k values.
nums = [1, 1, 1, 2, 2, 3] counts: {1: 3, 2: 2, 3: 1}
bucket index: 0 1 2 3 4 5 6
contents: [] [3] [2] [1] [] [] []
↑
walk from the right, collect 1 then 2 → [1, 2]Real-world analogy
Sorting exam papers by score when scores run 0–100. You do not compare papers pairwise — you set out 101 trays and drop each paper into its tray. Reading the trays from the top gives a sorted order without a single comparison.
Watch it run
Approach
Count frequencies
One pass into a hash map: value → count.
Create n + 1 empty buckets
Index f is reserved for values with frequency f. Index 0 is never used but keeps the indexing natural.
Walk buckets from n down to 1
Collect every value you find until the result holds k of them, then stop.
Solution
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
"""The k most frequent values, in O(n) time via bucket sort."""
counts = Counter(nums)
# buckets[f] = list of values that appear exactly f times.
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for value, count in counts.items():
buckets[count].append(value)
result: list[int] = []
for frequency in range(len(buckets) - 1, 0, -1):
for value in buckets[frequency]:
result.append(value)
if len(result) == k:
return result
return resultThe heap version, for when you want O(n log k) and less memory:
import heapq
from collections import Counter
def top_k_frequent_heap(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
return [value for value, _ in counts.most_common(k)]
def top_k_frequent_manual_heap(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
heap: list[tuple[int, int]] = []
for value, count in counts.items():
heapq.heappush(heap, (count, value))
if len(heap) > k:
heapq.heappop(heap) # evict the smallest count
return [value for _, value in heap]Do not build buckets with `Array(n).fill([])`
fill([]) puts the same array object into every slot, so pushing into one bucket pushes into all of them. Use Array.from({ length: n }, () => []), which calls the factory once per slot. Python's [[] for _ in range(n)] has the same requirement — [[]] * n is the broken equivalent.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time —
O(n)to count,O(d)to fill buckets whered ≤ nis the number of distinct values, andO(n)to walk the buckets. Linear overall, beating theO(n log n)sort and theO(n log k)heap. - Space —
O(n)for the count map plusO(n)for the buckets.
When is the heap still the right choice?
Bucket sort needs O(n) buckets up front. If n is enormous and k is tiny — say the top 10 of a billion-element stream — a size-k heap uses O(k) memory and can process data it never has to hold all at once. Different constraints, different winner.
Edge Cases
Related Problems
- Number of Good Pairs — the counting half of this problem
- Group Anagrams — hash maps that group rather than rank
- Sort the People — ordering by a derived key