The problem
Given a list of numbers and a number k, return the k numbers that appear most often.
Input: nums = [1,1,1,2,2,3,4,4,4,4], k = 2 Output: [4, 1] (4 appears 4 times, 1 appears 3 times)
Picture it
Imagine a clinic logbook full of visitor IDs. First we count how many times each visitor came. Then we line the visitors up in buckets by visit count: bucket 1 holds people who came once, bucket 2 those who came twice, and so on. Reading the buckets from the highest count down, the first k visitors we meet are the answer.
How to recognise it
- The question asks for the top k of something (the k largest, most frequent, closest).
- You need the k winners, not a full ranking of everything.
- The score here is a frequency, so you must count first with a dictionary.
- Up to 10^5 numbers. LeetCode's follow-up asks for better than O(n log n), which hints that sorting everything is more than needed.
Start with brute force
For each distinct value, count how often it appears by scanning the list, then sort the values by count and take the first k.
def top_k_brute(nums, k):
freq = {v: nums.count(v) for v in set(nums)} # each count scans the list
order = sorted(freq, key=lambda v: freq[v], reverse=True)
return order[:k]
With d distinct values, the counting alone is O(n · d), up to O(n²). If all 10^5 numbers differ, that is 10^10 steps. Sorting adds O(d log d). Space is O(d).
Counting in one pass with a Counter fixes the first part at O(n). Sorting all d values by count then costs O(d log d), which works, but does more than the problem needs.
From brute force to the idea
- Count once.
Counter(nums)builds value → count in one O(n) pass. - Find the waste. Sorting puts all d values in order, but only the top k matter. The order of the rest is wasted work.
- Keep a small shortlist. Hold at most k (count, value) pairs in a min-heap: a structure that keeps the smallest item on top and can add or remove in O(log size).
- Push, then trim. Push each pair. If the heap now has k + 1 items, pop the top, which is the least frequent of them. The k most frequent seen so far always survive.
- Read the answer. After every value has been offered, the heap holds exactly the k most frequent values.
This is the key idea: a min-heap capped at size k, whose top is the weakest member and the first to be dropped.
The key idea
Count with a dictionary, then use “bucket by count”: no full sort needed, so it runs in O(n).
Python solution
def top_k_frequent(nums, k):
count = Counter(nums)
heap = [] # (visits, value), fewest on top
for x, c in count.items():
heappush(heap, (c, x))
if len(heap) > k:
heappop(heap)
return [x for c, x in heap]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · d + d log d): one scan of the list per distinct value | O(d): the count table |
| Counter + size-k heap (shown code) | O(n + d log k): one counting pass, then each push or pop is O(log k) | O(d + k): the Counter and the heap |
Edge cases
- k equals the number of distinct values: nothing is ever popped, so every value is returned.
- Single number (
[1], k = 1): returns[1]. - Output order: the result is in heap order, not sorted by frequency. For the example it returns
[1, 4], not[4, 1]. LeetCode accepts any order; sort the result if a caller needs it ranked. - Ties at the cut-off: LeetCode promises a unique answer. If two values did tie, the pair
(count, value)compares by value next, so the smaller value is popped first. - Negative numbers: work unchanged, since the value is only a tie-breaker.
- Missing imports: the code needs
from collections import Counterandfrom heapq import heappush, heappop; without them it raisesNameError.
Common mistakes
- Using a max-heap (or negated counts) but still popping when the size passes k. That throws away the most frequent values and keeps the least frequent.
- Pushing all d values into a heap and popping k times. Still correct, but O(d + k log d) with O(d) heap space, so it no longer benefits from small k.
- Forgetting the heap stores pairs and returning them as-is instead of extracting the values.
An O(n) alternative is bucket sort: make a list of buckets indexed by count (0 to n) and read them from the highest down.
Given a list of words and k, return the k most frequent words, sorted by frequency from high to low, with ties broken alphabetically. For ["i", "love", "leetcode", "i", "love", "coding"] and k = 2 the answer is ["i", "love"]. Describe your approach, then write it if you like.
Compare with our answer
Count with a Counter, then order the distinct words by the key (−count, word): the minus sign puts higher counts first, and equal counts fall back to alphabetical order.
from collections import Counter
def top_k_words(words, k):
count = Counter(words)
return sorted(count, key=lambda w: (-count[w], w))[:k]
Time O(n + d log d), space O(d). A size-k heap also works, but its comparison must be reversed for the words, which is easy to get wrong.
A strong answer mentions: a two-part sort key, negating the count rather than the word, and that the result here must be ranked, unlike in the original problem.
1. Numbers arrive one at a time and you must always be able to report the 10 largest seen so far. Which approach fits best?
The capped min-heap keeps only the current top 10, and its smallest member is the one to evict: O(log 10) per number. The other options store everything and redo work on every request.
2. Why is each heap operation in the shown code O(log k) and not O(log d)?
Every value is pushed, but the heap never holds more than k + 1 pairs, so each push and pop costs O(log k). The Counter is not sorted, and values seen once are still offered.
3. A learner changes the push to heappush(heap, (-c, x)) and keeps everything else. What does top_k_frequent([1, 1, 1, 2, 2, 3], 2) return?
With negated counts, the top of the min-heap is the most frequent value, so each trim discards it. The heap keeps the k least frequent: [2, 3]. Negation needs a different trimming rule, not the same one.
Score 60% or more and the lesson is marked complete.