Top K Frequent Elements

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.