Repository navigation
035 — Top K Frequent Elements
LeetCode 347 · Medium. Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Picture a radio station tallying song requests all day, and at midnight they need to announce the top 5 most-requested songs. The naive approach: write every request on a slip of paper, then sort the entire pile of slips from most-requested to least, and read off the top 5 — even though you only ever needed 5 answers out of what might be thousands of songs. A smarter approach: once you know how many times each song was requested, you don't need to sort at all — just line up empty bins labeled "requested 1 time," "requested 2 times," ... "requested N times," drop each song into its bin, and then read bins back-to-front, grabbing songs until you have 5. No sorting, just direct placement.
"Top K [most/least] frequent" is the headline signal for this whole family of problems (it's common enough to be its own pattern — see Top-K and Heap Pattern). Whenever a problem asks for "the k most/least [common/frequent] items," it's really two sub-problems glued together: (1) count frequencies (hash map), then (2) select the top k by that count without fully sorting everything — either with a heap, or, when frequencies are bounded by the array's own length (as they are here — an element can't appear more than n times in an array of length n), with bucket sort, which avoids comparison-sorting entirely.
Count frequencies, then sort every distinct element by its frequency and take the top k.
func topKFrequentBruteForce(_ nums: [Int], _ k: Int) -> [Int] {
var counts = [Int: Int]()
for num in nums {
counts[num, default: 0] += 1
}
let sortedByFrequency = counts.sorted { $0.value > $1.value }
return sortedByFrequency.prefix(k).map { $0.key }
}Big-O: O(n log n) time — counting is O(n), but sorting the (up to n) distinct elements by frequency is O(n log n). O(n) space for the counts map.
Count frequencies, then bucket elements by frequency into an array indexed 0...n (a frequency can never exceed the array's length). Walk the buckets from highest frequency down to lowest, collecting elements until we have k.
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var counts = [Int: Int]()
for num in nums {
counts[num, default: 0] += 1
}
// buckets[f] = every number that appears exactly f times
var buckets = [[Int]](repeating: [], count: nums.count + 1)
for (num, freq) in counts {
buckets[freq].append(num)
}
var result = [Int]()
var freq = buckets.count - 1
while freq >= 0 && result.count < k {
for num in buckets[freq] {
result.append(num)
if result.count == k {
break
}
}
freq -= 1
}
return result
}Big-O: O(n) time — counting is O(n), filling n + 1 buckets is O(n), and walking the buckets visits at most n total elements across all buckets, so no step depends on log n. O(n) space for the counts map and the buckets.
The brute force treats "find the top k" as "fully order everything, then take a prefix" — but full ordering is overkill when you only need the top k, not a total order over all n elements. The trick that makes this problem collapse to linear time is noticing that frequency itself is a bounded integer (between 0 and n), so instead of comparison-sorting by frequency, you can use frequency as an array index — bucket sort. Placing each element directly into "the bin for its frequency" and reading bins back-to-front sidesteps the log n factor that any comparison-based sort is stuck with, because you never compare two frequencies against each other — you just place and read.
- Hash Maps & Hash Sets — the frequency-counting map both solutions start from.
-
Top-K and Heap Pattern — the broader "select the top k without a full sort" pattern this problem belongs to (a heap-based
O(n log k)solution is the more general tool when frequencies aren't cleanly bounded). - Arrays & Strings — the bucket array used to index by frequency.
Top K Frequent Elements is a radio station's request tally — bin songs by how often they were requested, then read the bins back-to-front instead of sorting the whole pile.
The bucket-sort solution relies on the fact that a frequency can never exceed nums.count. Suppose instead the problem asked for the top k most frequent elements across a stream of numbers where you don't know the total count in advance. Would bucket sort still apply directly? What data structure would you reach for instead, and why does it not need a bound on the maximum frequency?
⬅️ Previous: Group Anagrams · Next: Product of Array Except Self ➡️