Top K Frequent Elements
MediumHeaps
Given an array of integers nums and a number k, return the k values that appear most often in nums.
The values can come back in any order. Every test has exactly one right set of k values, so there are no ties at the cut.
Examples
Input: nums = [4, 4, 4, 7, 7, 2], k = 2 Output: [4, 7]
4 appears three times and 7 twice; 2 only once.
Input: nums = [9], k = 1 Output: [9]
The only value is the most frequent one.
Constraints
1 ≤ nums.length ≤ 10⁵-10⁴ ≤ nums[i] ≤ 10⁴kis between 1 and the number of different values.- The answer is unique.
Stuck?
Hint 1
First count how often each value appears with a Map. The question is then which k counts are the largest.
Hint 2
Sorting the counts costs O(n log n). To do better, put each value in a bucket indexed by its count (no count exceeds n), then read the buckets from the top down until you have k values.
The idea
Count each value, then pick the k largest counts. No count can be more than nums.length, so instead of sorting the counts, drop each value into a bucket numbered by its count and read the buckets from the highest number down. That keeps the whole thing O(n).
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Count how often each value appears. counts.get(num) || 0 starts a value that has not been seen yet at zero.
function topKFrequent(nums, k) { const counts = new Map(); for (const num of nums) counts.set(num, (counts.get(num) || 0) + 1); const buckets = Array.from({ length: nums.length + 1 }, () => []); for (const [num, count] of counts) buckets[count].push(num); const answer = []; for (let count = nums.length; count > 0 && answer.length < k; count--) { answer.push(...buckets[count]); } return answer.slice(0, k);}The trap
Counting, sorting by count and taking k is a correct plan, and it reads right. The sort compares a[1] - b[1], though, which puts the smallest counts first, so it returns the k rarest values. It only passes when k is the number of different values, because then every value is in the answer anyway.
function topKFrequent(nums, k) { const counts = new Map(); for (const num of nums) counts.set(num, (counts.get(num) || 0) + 1); return [...counts.entries()] .sort((a, b) => a[1] - b[1]) // smallest counts first .slice(0, k) .map(([num]) => num);}