Top K Frequent Elements
Return the k values that appear most often in an array. A counting problem where bucket sort beats the obvious sort-by-frequency. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums and an integer k. Return the k distinct values that occur most often in nums.
The inputs are chosen so the answer is unique: there's never a tie for the last spot. You may return the values in any order.
Aim for better than O(n log n) time.
Example 1
- Input
- nums = [4, 4, 4, 6, 6, 9], k = 2
- Output
- [4, 6]
4 appears three times and 6 twice; 9 appears only once.
Example 2
- Input
- nums = [7], k = 1
- Output
- [7]
Example 3
- Input
- nums = [-1, -1, 3, 3, 3, 0], k = 1
- Output
- [3]
3 appears three times, more than any other value.
Constraints
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ number of distinct values in nums
- The set of k most frequent values is unique.
Practice
Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Top K Frequent Elements in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Top K Frequent Elements
Pattern: Count, then bucket by frequency
The first step is obvious: count how often each value appears with a hash map. The interesting part is picking the top k counts without fully sorting them.
The key observation is that a count can only be between 1 and n. When the possible keys are small integers in a known range, you can sort them by putting them in buckets instead of comparing. Make an array of n + 1 lists where bucket c holds every value that appeared c times. Then walk the buckets from n down to 1, collecting values until you have k. No comparisons, no log factor.
Approach 1: Count and sort by frequency
Build a frequency map, sort the distinct values by count descending, and take the first k. Short and easy to explain; the sort over up to n distinct values is the cost.
Time O(n log n) · Space O(n)
Approach 2: Count and keep a size-k min-heap
Push (count, value) pairs into a min-heap and pop whenever it grows past k. What remains are the k largest counts. This is the best choice when k is much smaller than the number of distinct values.
Time O(n log k) · Space O(n)
Approach 3: Count and bucket by frequency
- Count each value in a hash map.
- Create
buckets, an array ofn + 1empty lists, and add each value tobuckets[count]. - Walk
cfromndown to 1, appending the values inbuckets[c]to the result, and stop as soon as it holdskvalues.
Every step is linear in n.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Count and sort by frequency | O(n log n) | O(n) |
| Count and keep a size-k min-heap | O(n log k) | O(n) |
| Count and bucket by frequency | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Top K Frequent Elements solution in Python
from collections import Counter
def k_most_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for value, count in counts.items():
buckets[count].append(value)
result = []
for count in range(len(nums), 0, -1):
for value in buckets[count]:
result.append(value)
if len(result) == k:
return result
return resultTop K Frequent Elements solution in JavaScript
function kMostFrequent(nums, k) {
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 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; count--) {
for (const value of buckets[count]) {
result.push(value);
if (result.length === k) return result;
}
}
return result;
}Common mistakes
- Returning the counts instead of the values.
- Sizing the bucket array by the number of distinct values instead of `n + 1`. A count can be as large as `n`.
- Collecting a whole bucket after you already have `k` values, which returns too many when a bucket holds several values.
- Using a max-heap of all distinct values and popping `k` times, then calling it O(n log k). Building the full heap is O(n) but each pop is O(log n).
What interviewers look for
Most candidates get the hash map immediately. What separates answers is the second half: say the sort-based version, then point out that counts are bounded by n, which is what makes bucket sort possible. That reasoning, "the keys are small integers, so I don't need comparisons", is what interviewers listen for.
Be ready to compare the heap and bucket versions. The heap uses O(k) extra space beyond the counts and is better for streaming; buckets give strict O(n).
Follow-up questions
What if the numbers arrive as a stream and you need the top k at any time?
Keep the running count map plus a size-k min-heap, updating it as counts change, or use a count-to-values map with a doubly linked list of frequencies. For approximate answers on huge streams, a Count-Min Sketch with a small heap uses fixed memory.
How would you break ties, for example by smaller value first?
Sort each bucket (or order heap entries by `(count, -value)` or similar). The answer becomes deterministic, and the extra sort only touches values that share a count.
Can you get expected O(n) without the bucket array?
Yes, with quickselect on the distinct values keyed by count: partition until the k most frequent sit on one side. It is expected O(n) but O(n²) in the worst case unless you pick pivots carefully.
Companies that ask Top K Frequent Elements
Top K Frequent Elements is tagged by 135 companies in our interview dataset. The score shows how often it comes up at each company.
- Notion100%
- Blue Yonder100%
- Sopra Steria100%
- Traveloka100%
- Myriad Genetics100%
- Mvf100%
- Pocket Gems100%
- Disney100%
- Chewy100%
- Gocardless98%
- Avito95.6%
- Yelp94.2%
- And Digital93%
- Two Six Technologies93%
- Ancestry92%
- Roku91.4%
- Sofi91.4%
- The New York Times Company90%
- Redfin90%
- Logmein89%
- Buffer88%
- Solo Funds87%
- Pagerduty86%
- Yahoo84.4%
and 111 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required