Coding · Heaps
Top K Frequent Elements
- Appears on company lists
- Medium
- 2 sources
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Given an array of integers and a number k, return the k distinct values that appear most often, in increasing order. The input is guaranteed to have a unique answer, so there is no tie at the cutoff. For nums [7, 2, 7, 5, 2, 7] and k = 2 the answer is [2, 7], because 7 appears three times and 2 appears twice. The array has up to 100,000 elements, and the selection should not sort every distinct value.
Restated in our own words, not a quote from Apple or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: is k always between 1 and the number of distinct values? If two values tie at the cutoff, is any of them acceptable, or is the input guaranteed to avoid that? Can the numbers be negative or large? In what order should the result come back? And is the data an array in memory, or a stream I only see once?
I would assume an in-memory array, any integers, a unique answer, and that the result must come back in increasing order, so I will sort only the k chosen values at the end. I will count first, then choose how to select the top k.
Brute force
Say the obvious answer and why it is too slow.
Count the occurrences with a Map, put the distinct values in an array, sort that array by count from high to low, and take the first k. It is simple and correct. Counting is O(n), and sorting d distinct values costs O(d log d), which is O(n log n) when most values are distinct.
At 100,000 elements this runs fast enough, so it is not wrong, but it does more work than necessary. It fully orders all d values when we only want the top k, and the stated goal is to avoid sorting every distinct value. On much larger inputs the logarithmic factor starts to matter, and a sort also needs all the counts to exist before it begins.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n log n)
- Time
- O(n) plus O(k log k) to sort the output
- Space
- O(n)
A count can never be larger than n, so counts are small whole numbers, and we can sort them without comparing. Make an array of buckets indexed by count, where buckets[c] holds the values that appear exactly c times. Fill it from the count Map, then walk the buckets from the highest index down, collecting values until we have k of them.
Why it is right: walking from index n down visits values in non-increasing order of frequency. So after collecting k values we hold k values with counts at least as large as everything left behind. Because the answer is guaranteed unique, the cutoff never splits a bucket, so those k are exactly the answer. Every value goes into exactly one bucket and every bucket is touched once, so the whole thing is O(n) time and O(n) memory.
There is a second standard answer: a min-heap of size k. Push each distinct value with its count, and when the heap grows past k, pop the smallest count. The heap always holds the k most frequent values seen so far, which is the invariant. That costs O(n log k) and uses O(k) memory beyond the counts, so it is the better choice when k is tiny, the counts arrive as a stream, or the bucket array would be wasteful. JavaScript has no built-in heap, so in an interview you either write one or choose buckets.
Out loud: "count with a hash map, then bucket sort by frequency, because frequency is bounded by n."
Walk it through
A dry run on the example, step by step.
| Step | Counts so far | Bucket scanned | Picked |
|---|---|---|---|
| read 7 | 7:1 | - | - |
| read 2 | 7:1, 2:1 | - | - |
| read 7 | 7:2, 2:1 | - | - |
| read 5 | 7:2, 2:1, 5:1 | - | - |
| read 2 | 7:2, 2:2, 5:1 | - | - |
| read 7 | 7:3, 2:2, 5:1 | - | - |
| make buckets | 1:[5] 2:[2] 3:[7] | - | - |
| scan count 3 | same | [7] | 7 |
| scan count 2 | same | [2] | 7, 2 |
| sort output | k reached | stop | 2, 7 |
The input is [7, 2, 7, 5, 2, 7] with k = 2. The first six rows build the count Map one element at a time; after the last read it holds 7 three times, 2 twice and 5 once.
Next the counts are turned into buckets: bucket 1 holds 5, bucket 2 holds 2 and bucket 3 holds 7. The scan starts at the highest index that can exist, 6, and passes over the empty buckets above 3 without any work worth showing, so the table begins at count 3. Bucket 3 gives 7, and bucket 2 gives 2, so the result has two values and we stop; bucket 1 is never read. The final row sorts the result into [2, 7] only so the output order is fixed. The heap version would instead hold 7 and 2 after reading all counts and would have discarded 5 along the way.
The code
Runnable JavaScript, checked against test cases.
function topKFrequent(nums, k) {
const counts = new Map();
for (const value of nums) {
counts.set(value, (counts.get(value) || 0) + 1);
}
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [value, count] of counts) {
buckets[count].push(value);
}
const result = [];
for (let count = nums.length; count > 0 && result.length < k; count--) {
for (const value of buckets[count]) {
result.push(value);
}
}
return result.sort((a, b) => a - b);
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
k equal to the number of distinct values returns every distinct value, and the scan simply runs down to bucket 1. A single element returns itself. Negative numbers work because the Map accepts any key and the buckets are indexed by count, not by value. An empty array with k = 0 gives an empty result, since the loop stops immediately.
If every value appears once, all of them sit in bucket 1, and the guarantee of a unique answer means the caller then asks for all of them. If the answer were not unique, a bucket could be cut in the middle and the choice would be arbitrary, so I state that assumption early. The bucket array has n + 1 slots so that a value filling the whole array, with count n, still has a bucket.
Follow-ups to expect
Where the interviewer pushes next.
- How would you do it with a size-k min-heap, and when is it better than buckets?
- How would you find the top k in a stream that does not fit in memory?
- How would you break ties by the smaller value, or by who appeared first?
- Can quickselect on the counts give O(n) average time, and what is the catch?
- How would a count-min sketch change the answer, and what accuracy do you give up?
Where candidates slip
The mistakes this problem punishes.
The most common slip is sorting the original array instead of the distinct values, or sorting the Map entries with a comparator that returns a boolean rather than a number, which gives a wrong order. Another is sizing the bucket array to the number of distinct values instead of n + 1, so a high count lands out of range.
With a heap, candidates push every distinct value into a max-heap one by one, which costs O(d log d) for d distinct values and gains nothing over sorting, or they forget to evict when the size passes k. Others use a plain object as the counter and get string keys back, so the output becomes strings instead of numbers. A last one is returning more than k values when the final bucket holds several, which the uniqueness guarantee rules out but a real interviewer may not.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.