Top K Frequent Elements
Find the k numbers that appear most often in an array.
- Frequency counting
- Bucket sort
Before this, know: Frequency counting with a hash map (see Valid Anagram), Arrays of arrays
You get an array of numbers nums and a number k. Return the k numbers that
appear most often. The frequency of a number is how many times it appears.
Example: nums = [1, 1, 1, 2, 2, 3] and k = 2.
- 10
- 11
- 12
- 23
- 24
- 35
| number | times |
|---|---|
| 1 | 3 |
| 2 | 2 |
| 3 | 1 |
So the answer is [1, 2]. The rules that matter:
- Return the numbers themselves (not their counts), in any order.
- LeetCode promises the answer is unique: there’s never a tie at the cut-off that makes two different answers possible.
kis between 1 and the number of different values.- The follow-up asks for something better than O(n log n), which rules out plain sorting. Keep that in mind. (Big-O notation is a short way of saying how the work grows as the input grows; O(n log n) is what sorting n items costs. See Big-O in 5 minutes.)
The work splits into two parts:
- Count how often each number appears (frequency counting, exactly as in Valid Anagram).
- Pick the k biggest counts.
Part 1 is easy and fast with a hash map: a lookup table from a key (here, a
number) to a value (here, its count), Map in JavaScript and dict in Python,
that finds a key in about one step (see
What is a hash map?). The
interesting question is part 2.
Pause and think
At most 6: that happens when every number is the same, like [7, 7, 7, 7, 7, 7].
A frequency can never exceed the length of the array, so shelves 1 to n
(n = the length) are always enough. That fixed, small range is what makes the
bucket trick possible.
The natural first idea: count with a hash map, list the different numbers, sort them by count from biggest to smallest, and take the first k.
Count, then sort by count
nums = [1, 1, 1, 2, 2, 3], k = 2
- 10
- 11
- 12
- 23
- 24
- 35
| number | times |
|---|---|
| 1 | 1 |
- Looking at now
- Just counted
- Answer
Count nums[0] = 1: count[1] is now 1.
Which line is running?
function topKFrequent(nums, k) { const count = new Map(); // number -> how many times it appears for (const num of nums) {Running now: count.set(num, (count.get(num) ?? 0) + 1); } const distinct = [...count.keys()]; distinct.sort((a, b) => count.get(b) - count.get(a)); // most frequent first return distinct.slice(0, k);}Count, then sort
function topKFrequent(nums, k) { const count = new Map(); // number -> how many times it appears for (const num of nums) { count.set(num, (count.get(num) ?? 0) + 1); } const distinct = [...count.keys()]; distinct.sort((a, b) => count.get(b) - count.get(a)); // most frequent first return distinct.slice(0, k);}def top_k_frequent(nums, k): count = {} # number -> how many times it appears for num in nums: count[num] = count.get(num, 0) + 1 distinct = list(count.keys()) distinct.sort(key=lambda x: count[x], reverse=True) # most frequent first return distinct[:k]Counting is n steps. Sorting m different numbers costs about m × log m steps. In the worst case every number is different (m = n), so the whole thing is O(n log n). For 100,000 numbers that’s roughly 1.7 million steps. That’s honestly fine in practice, but the follow-up explicitly asks to beat O(n log n), so we need to avoid a full sort.
A heap (a “priority queue”) is a structure that always hands you its
smallest (or largest) item in about log k steps. Keep a heap of the k most
frequent numbers seen so far, with the least frequent of them on top. For
each number, push it in; if the heap grows past k, pop the least frequent one
off. At the end, the heap holds the top k. That’s O(n log k), which beats
O(n log n) when k is small. JavaScript has no built-in heap; Python has
heapq. Heaps come later in the roadmap. Next we’ll see a trick that’s even
faster and needs nothing new.
Sorting compares numbers with each other. But frequencies are small whole numbers between 1 and n, so we can use a frequency as an index and drop each number straight into its slot. Using values as positions to avoid comparing is called bucket sort.
Pattern
Bucket sort / top K by frequency
Use it when: you need the most (or least) frequent items, and the counts are bounded by the input size.
Signal words
- “top k”
- “k most frequent”
- “sort by frequency”
- “most common”
- “better than O(n log n)”
- 0
- 31
- 22
- 13
- 4
- 5
- 6
↑ bucket number = how many times
- Count: build a hash map
countof number → frequency. - Make buckets: an array of n + 1 empty lists.
buckets[f]will hold every number that appears exactly f times. - Fill: for each (number, frequency) in
count, append the number tobuckets[frequency]. - Collect: walk
ffrom n down to 1. Take every number inbuckets[f]and add it toresult. As soon asresulthas k numbers, return it.
Press Play. Watch the three stages: the count map filling, numbers dropping into the bucket that matches their count, then the scan from the right. Try the “tie in a bucket” example, where two numbers share a bucket.
Count, then bucket by frequency
nums = [1, 1, 1, 2, 2, 3], k = 2
- 10
- 11
- 12
- 23
- 24
- 35
| number | times |
|---|---|
| 1 | 1 |
- empty
- k
- 2
- f
- —
- Looking at now
- Just changed
- Bucket we're reading
- In the answer
Step 1, counting. nums[0] = 1: first time we see it, so count[1] = 1.
Which line is running?
function topKFrequent(nums, k) { const count = new Map(); // number -> how many times it appears for (const num of nums) {Running now: count.set(num, (count.get(num) ?? 0) + 1); } // buckets[f] holds every number that appears exactly f times const buckets = Array.from({ length: nums.length + 1 }, () => []); for (const [num, freq] of count) { buckets[freq].push(num); } const result = []; for (let f = buckets.length - 1; f > 0; f--) { for (const num of buckets[f]) { result.push(num); if (result.length === k) return result; } } return result; // never reached: k is at most the number of distinct values}Notice that most buckets stay empty. That’s fine: walking past an empty bucket costs one step, and there are only n + 1 of them.
Count, then bucket
function topKFrequent(nums, k) { const count = new Map(); // number -> how many times it appears for (const num of nums) { count.set(num, (count.get(num) ?? 0) + 1); } // buckets[f] holds every number that appears exactly f times const buckets = Array.from({ length: nums.length + 1 }, () => []); for (const [num, freq] of count) { buckets[freq].push(num); } const result = []; for (let f = buckets.length - 1; f > 0; f--) { for (const num of buckets[f]) { result.push(num); if (result.length === k) return result; } } return result; // never reached: k is at most the number of distinct values}def top_k_frequent(nums, k): count = {} # number -> how many times it appears for num in nums: count[num] = count.get(num, 0) + 1 # buckets[f] holds every number that appears exactly f times buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) result = [] for f in range(len(buckets) - 1, 0, -1): for num in buckets[f]: result.append(num) if len(result) == k: return result # we have our k numbers return result # never reached: k is at most the number of distinct valuesJavaScript’s closing braces push its line numbers ahead of Python’s from line 5 on; we give both where they differ.
- Line 1: define the function. (LeetCode uses
var topKFrequent = function(nums, k)in JS anddef topKFrequent(self, nums, k)insideclass Solutionin Python.) - Lines 2–4: the frequency count.
count.get(num) ?? 0/count.get(num, 0)means “the count so far, or 0 if this is the first time”. - Line 7 (JS) / line 6 (Python): n + 1 empty lists, indexes 0 to n. We
need index n because a number could appear n times. Index 0 is never used
(every number in
countappears at least once); it’s there so thatbuckets[f]lines up with f. NoteArray.from({ length }, () => [])creates a separate empty list for each slot. - Lines 8–9 (JS) / lines 7–8 (Python): drop each number into the bucket for its frequency. No comparisons, no sorting.
- Line 12 (JS) / line 10 (Python): walk the buckets from the highest
frequency down to 1. In Python
range(len(buckets) - 1, 0, -1)counts down and stops before 0. - Lines 13–15 (JS) / lines 11–14 (Python): take each number from the bucket, and return as soon as we have k.
- The last line is a safety net. Since k is never more than the number of different values, we always return earlier.
| stage | what happens | state afterwards |
|---|---|---|
| count | walk nums | count = {1: 3, 2: 2, 3: 1} |
| make | 7 empty buckets (0 to 6) | [[], [], [], [], [], [], []] |
| fill | 1 → bucket 3, 2 → bucket 2, 3 → bucket 1 | [[], [3], [2], [1], [], [], []] |
| collect f = 6, 5, 4 | empty, skip | result = [] |
| collect f = 3 | take 1 | result = [1] |
| collect f = 2 | take 2: that's k = 2 | return [1, 2] |
Look at the “fill” row: in one walk over the count map, every number lands in the right place. A sort would have needed to compare them.
Here n is the length of nums.
Count, then sort
Time
O(n log n)
Counting is n steps; sorting up to n different numbers is about n × log n.
Space
O(n)
The count map and the list of distinct numbers.
Count, then heap of size k
Time
O(n log k)
Each of up to n numbers is pushed into a heap that never holds more than k, costing about log k each.
Space
O(n)
The count map (n) plus the heap (k).
Count, then bucket sort
Time
O(n)
Counting is n steps, filling buckets is at most n, and the final walk visits n + 1 buckets and at most n numbers. Three straight passes.
Space
O(n)
The count map plus n + 1 buckets holding each distinct number once.
What to say out loud, in this order:
- “Two parts: count frequencies with a hash map, then select the top k.”
- “Sorting by count is O(n log n). A min-heap of size k is O(n log k).”
- “Frequencies are between 1 and n, so I can bucket by frequency: O(n) overall.”
- Point out the n + 1 bucket size and the early stop at k.
Likely follow-up questions:
- “What if k is close to n?” The bucket approach is O(n) either way; a heap of size k would be close to O(n log n).
- “What if the data is a stream and doesn’t fit in memory?” Be careful: the count map still holds one entry per different value, so the heap doesn’t shrink that. A heap of size k only bounds the selection step (it holds k items instead of n + 1 buckets). If even one count per different value doesn’t fit, you need an approximate method that trades a little accuracy for much less memory.
- “Top k frequent words, ties broken alphabetically?” Sort the words inside each bucket, or use a heap with a custom comparison.
Related problems:
- Valid Anagram (this week): the counting step on its own.
- Group Anagrams (this week): grouping things under a shared key, like grouping numbers under their frequency here.
- Contains Duplicate (this week): the simplest “has it appeared before?” question.