Example 1
ready- Input
nums = [ 1, 1, 1, 2, 2, 3 ] k = 2- Expected
[ 1, 2 ]- Why
- 1 appears three times and 2 appears twice
Top K Frequent Elements
35 min · topKFrequent()mediumOpen in LeetCode #347 ↗
Raw event logs are noisy. A short list of the values that appear most often is much more useful.
Given an integer array nums and an integer k, return the k values with the highest
frequency — the number of times a value appears. You may return those values in any
order.
A few ground rules:
knever exceeds the number of distinct values innums.- The answer is unique. When one value sits just inside the top
kand another sits just outside it, the inside value always appears more often. - The output contains values from
nums, not their positions or their frequencies.
Constraints
1 <= nums.length <= 100_0001 <= k <=the number of distinct values innums-1_000_000_000 <= nums[i] <= 1_000_000_000- The set of
kmost frequent values is unique.
Hints
Count before you rank
First build a map from each value to the number of times it appears. Sorting those map entries by their counts already gives you a correct baseline.
A frequency has a ceiling
No value can appear more than nums.length times. What if index f of an array
held every value whose frequency is exactly f?
Walk the buckets backwards
Fill the frequency buckets in one pass over the count map, then scan from the
largest possible frequency down. Stop as soon as you've collected k values.
Follow-up
Could you keep only the current top k values if the input arrived as a stream and
there were too many distinct values to bucket at once?
Visible cases
Examples
Example 2
ready- Input
nums = [ 4, -2, -2, 4, 9, 4, 4 ] k = 1- Expected
[ 4 ]- Why
- 4 has the single highest frequency
Example 3
ready- Input
nums = [ -1, 8, 5, 8, 8, -1 ] k = 3- Expected
[ 8, -1, 5 ]- Why
- k includes all three distinct values
Interview signal
Asked at
AmazonMetaYelpUber
Let n be the number of array entries and m the number of distinct values. Both
approaches begin with the same honest move: count every value once.
Count + sort
Store each value's frequency in a dictionary, then sort the distinct values from most
frequent to least frequent. The first k values are the answer.
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts: dict[int, int] = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
ranked = sorted(counts, key=counts.get, reverse=True)
return ranked[:k]Time O(n + m log m) — counting costs O(n), then sorting m distinct values costs
O(m log m). Space O(m) for the count map and ranking.
This is a solid baseline, but sorting learns more order than you need. You only need to
visit frequency groups from high to low until k values have appeared.
Frequency buckets
A value's frequency is an integer from 1 through n. Create n + 1 buckets, where
bucket f stores the values seen exactly f times. Once the buckets are filled, walk
them backwards.
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts: dict[int, int] = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for value, frequency in counts.items():
buckets[frequency].append(value)
answer: list[int] = []
for frequency in range(len(nums), 0, -1):
for value in buckets[frequency]:
answer.append(value)
if len(answer) == k:
return answer
return answerEvery input entry contributes to one count, every distinct value enters one bucket, and
the backward scan crosses at most n bucket positions. The unique-answer guarantee
means the scan never has to choose between tied values at the top-k boundary.
Time O(n) — counting, bucketing, and scanning are all linear. Space O(n) for the count map, buckets, and returned values.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 2 ]
Run: visible + custom · Submit: full suite