Top K Frequent Elements
Problem
Return the k most frequent elements, in any order. The answer is guaranteed to be unique. Aim for better than O(n log n).
Example 1
Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2]
Test cases
Case 1
Input: [1,1,1,2,2,3], 2 Expected (any order): [1,2]
Case 2
Input: [1], 1 Expected (any order): [1]
Case 3
Input: [4,4,5,5,5,6], 1 Expected (any order): [5]
View solutionHide solution2 approaches
1. Count + sort
Time O(n log n)Space O(n)
Count with a map, sort entries by count descending, take k.
function topKFrequent(nums, k) { const cnt = new Map(); for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1); return [...cnt].sort((a, b) => b[1] - a[1]).slice(0, k).map(([x]) => x);}2. Bucket sort by frequency
Time O(n)Space O(n)
A count is between 1 and n, so bucket values by count and read buckets from high to low.
function topKFrequent(nums, k) { const cnt = new Map(); for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1); const buckets = Array.from({ length: nums.length + 1 }, () => []); for (const [x, c] of cnt) buckets[c].push(x); const res = []; for (let c = nums.length; c > 0 && res.length < k; c--) res.push(...buckets[c]); return res.slice(0, k);}A min-heap of size k is O(n log k) and is the answer interviewers expect if they forbid bucket sort.