March 24
Top K Frequent Elements
How to count frequency first and then choose only the top K efficiently.
Heap and Frequency Intermediate 20 min TypeScript
Given an integer array nums and an integer k, return the k most frequent elements.
In the original problem, any order is usually accepted. In the SeniorPath playground, return them in descending frequency order to keep comparison deterministic.
Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
What to notice before coding
- The problem has two phases: count and select.
- Frequency is the central information. The original array becomes raw material for building that map.
- If you sort everything, it works. But maybe you are doing more than necessary.
Common mistakes
- trying to solve it without counting frequency first
- sorting the whole array instead of sorting or selecting by frequency
Step 1 - Split the problem into two parts
Many people try to answer directly:
- who are the most frequent elements?
But before that there is a smaller question:
- what is the frequency of each value?
Without that step, you cannot compare anything.
Step 2 - Write the most direct baseline
The natural baseline is:
- count frequency with a
Hash Map - turn it into a list of pairs
- sort by frequency
- take the first K
It works well.
The extra cost is sorting everything.
Step 3 - Ask what really matters
The problem does not ask for the whole list ordered.
It asks for:
- only the K most frequent elements
That creates room for a better selection strategy.
Step 4 - Use frequency buckets
The maximum frequency never exceeds nums.length.
So you can create buckets where:
- the index represents the frequency
- each bucket stores the values with that frequency
Then you just walk from the highest bucket down.
If frequency were not naturally bounded, a heap would be a common middle ground between full sort and buckets.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function topKFrequent(nums: number[], k: number): number[] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(n)
Solution 1 - Count with a Hash Map and sort all pairs
Good baseline because it makes both phases explicit.
export function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>()
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1)
}
return [...counts.entries()]
.sort((a, b) => b[1] - a[1] || a[0] - b[0])
.slice(0, k)
.map(([value]) => value)
}It works. But you sort every candidate even though you only need a few of them.
Solution 2 - Frequency buckets after the Hash Map instead of a heap
Now selection happens without a global sort.
export function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>()
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1)
}
const buckets = Array.from({ length: nums.length + 1 }, () => [])
for (const [value, frequency] of counts.entries()) {
buckets[frequency].push(value)
}
const result: number[] = []
for (let frequency = buckets.length - 1; frequency >= 0 && result.length < k; frequency -= 1) {
for (const value of buckets[frequency]) {
result.push(value)
if (result.length === k) {
break
}
}
}
return result
}The strong idea here is realizing that frequency itself can become an index.
That is why this beats a heap here: the problem gives you a small bounded range for frequency.
What to say in the interview
A strong short explanation would be:
First I count the frequency of each value with a
Hash Map. The baseline would sort all(value, frequency)pairs and take the top K. The better version uses buckets indexed by frequency, because the maximum frequency cannot exceedn. Then I walk from the highest bucket down until I collect K elements inO(n).
That shows that you:
- separated counting from selection
- justified why full sorting was not required
- explained the structure of the solution clearly
When this pattern shows up again
The same pattern comes back when you need to:
- count frequency before deciding
- select top K
- discuss the trade-off between sort,
heap, and buckets
- discuss the trade-off between sort,
- turn a bounded attribute into an index
The point is not memorizing
topKFrequent.
The point is learning to separate “measure” from “choose”.