Top K Frequent Elements
Return the k most frequent values in an array in O(n) with a count map and buckets indexed by frequency.
Problem Understanding
Top K Frequent Elements: given an integer array nums and an integer k, return the k values that appear most often, in any order. The answer is guaranteed to be unique.
Example: nums = [1, 1, 1, 2, 2, 3], k = 2 returns [1, 2] — 1 appears three times and 2 twice.
Attempt 1: Count, Then Sort by Count
Count every value with a hash map, sort the distinct values by their count in descending order, and take the first k. Counting is O(n), but sorting the m distinct values costs O(m log m) — up to O(n log n). The count map is the right first step; the sort is the part to replace.
The Intuition: Counts Are Small Integers
A value can appear at most n times, so its count is an integer from 1 to n. That means counts can be used as array indexes instead of being sorted:
- Count every value in a hash map.
- Make buckets
0..n; put each value intobuckets[count]. - Walk the buckets from
ndown to1, taking values untilkhave been taken.
Every step is linear, so the whole method is O(n) — the same idea as bucket sort, applied to frequencies.
Interactive Walkthrough
k = 2
START
nums
0
1
2
3
4
5
Result
—
count (value:count)
Empty
Find the 2 most frequent values. The count map starts empty
Next
nums[0] = 1: count[1] is now 1
Array
Target
First the array is counted left to right while the count map grows beside it. Then the buckets appear, one row per count from the highest down, and are read from the top; each value taken lights up and joins the result.