Top K Frequent Elements
You get an array of integers nums and an integer k. Return the k values that occur most often in nums, the most frequent first. When two values occur the same number of times, the smaller value comes first.
Each value appears once in the answer, however often it occurs in nums, and k is never larger than the number of different values.
Function
- numsinteger-array
- the values to count
- kinteger
- how many values to return
- Returnsinteger-array
- the k most frequent values, most frequent first, the smaller value first on a tie
Constraints
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, andkis at most the number of distinct values innums.
Examples
- Input
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Output
- [4, 1]
- Explanation
4occurs four times,1three times, and2and3once each. The two most frequent values are4, then1.
- Input
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Output
- [-2, 5]
- Explanation
-2,5and7each occur twice and9once. Three values tie for the top, so the smaller two,-2and5, are the answer.
- Input
- nums = [8]k = 1
- Output
- [8]
- Explanation
- There is one value, so it is the most frequent.
+16 hidden tests on Submit
Hints
Open them one at a time. Each one gives away a little more.
Start by finding out how often each value occurs. Which data structure maps a value to its count in one pass?
With the counts in hand, you want the
kbest values under one ordering: a higher count first, the smaller value on a tie. Sorting every distinct value works. A min-heap of sizekkeeps only the values that can still make the answer.A count is a whole number from 1 to
n. Make one bucket per count, bucketcholding the values that occur exactlyctimes, and read the buckets from the highest count down. Fill the buckets by walking the values from smallest to largest, and every bucket is already in tie order.
Solution
Counting is the quick half: one pass with a hash map gives every value's count. The real question is how to pick the k best values without doing more work than you need. Sorting all d distinct values by count costs O(d log d), a min-heap of size k brings that down to O(d log k), and because a count is a whole number from 1 to n, a bucket sort orders the values by count with no comparisons at all.
Count, then sort by count
Intuition
Count first. One pass with a hash map from value to count turns [4, 1, 4, 2, 1, 4, 3, 1, 4] into 4 → 4, 1 → 3, 2 → 1, 3 → 1.
Then put the distinct values in answer order: the higher count first, and for equal counts the smaller value first. Give the sort exactly that comparison, count as the first key and value as the second, and the first k entries of the sorted list are the answer. Here the order is 4, 1, 2, 3, and k = 2 keeps 4 and 1.
Counting costs O(n). Sorting the d distinct values costs O(d log d), at most O(n log n) when every value differs: 10^4 values take about 1.3 × 10^5 comparisons, which is fast. The waste is that the sort orders every value when only the first k matter.
Algorithm
- Count each value in a hash map.
- Put the distinct values in a list.
- Sort the list by count from high to low, and by value from low to high when counts are equal.
- Return the first
kvalues.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Keep the k best in a min-heap
Intuition
You need only the k best values, so hold only k candidates. For each new value the question is whether it beats the weakest candidate you hold, where weaker means a lower count, or the same count and a larger value. A min-heap ordered by that rule keeps the weakest candidate on top, where you read it in O(1) and replace it in O(log k).
Walk the distinct values. While the heap holds fewer than k, add the value. After that, a value that beats the top replaces it, and a value that does not is dropped, because k better values are already kept. With a library heap it is shorter to push every value and pop once whenever the heap grows past k, which keeps the same k values.
At the end the heap holds the answer, but not in answer order: a heap is only partly sorted. Popping returns the weakest value first, so write the answer from the last position back to the first.
Each of the d distinct values costs at most one heap operation on k entries, so choosing takes O(d log k). That beats sorting when k is much smaller than d, such as the top 10 of 8000 distinct values.
Algorithm
- Count each value in a hash map.
- For each distinct value, push it while the heap holds fewer than
kvalues. - Once the heap is full, compare the value with the top, the weakest value kept. If the new value is stronger, put it on top and sift it down.
- Pop the heap
ktimes, writing each value into the answer from the last position to the first.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultCount, then bucket sort by count
Intuition
A count is not any number: it is a whole number from 1 to n. That allows a bucket sort. Make one bucket per count, bucket c holding the values that occur exactly c times, and read the buckets from bucket n down. The values come out most frequent first, and no two counts are ever compared.
The tie rule asks for one more thing: inside a bucket, the smaller value must come first. The values lie between -10^4 and 10^4, so an array of R = 2 × 10^4 + 1 counters can do the counting, with value v at index v + 10^4. Walk that array from the smallest value to the largest and append each value to the bucket of its count. Every bucket fills in ascending order, which is the tie order, so nothing ever needs sorting.
For [5, -2, 7, -2, 7, 5, 9] the walk puts -2, 5, 7 in bucket 2, in that order, and 9 in bucket 1. Reading down from bucket 7, the first bucket with values is bucket 2, and k = 2 takes -2 and 5.
The work is one pass over nums, one pass over the R counters and one pass over the buckets, O(n + R) in total: linear for a fixed range of values. With a hash map in place of the counting array the counting stays linear, but the buckets fill in map order, and you would have to sort each one to honour the tie rule.
Algorithm
- Count every value in an array indexed by
value + 10^4. - Make buckets 1 to
n, one list per possible count. - Walk the counting array from the smallest value to the largest, and append each value that occurs to the bucket of its count.
- Read the buckets from count
ndown to 1, taking values until you havek.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Pitfalls and edge cases
The counting is rarely wrong. The order of the answer is.
- Breaking ties by first appearance or by hash map order. In the second example
-2,5and7all occur twice, and only the smaller-value rule makes[-2, 5]the one right answer. - Returning the heap's array as it sits. A heap is only partly ordered, and its top is the weakest value, the one that belongs last.
- Getting the heap's tie rule backwards. Of two values with the same count the larger one is weaker, so a min-heap on
(count, value)evicts the wrong one. Use(count, -value)or a comparison written for the rule. - Making only as many buckets as there are distinct values. One value can occur
ntimes, as in[3, 3, 3, 3], so bucketnmust exist. - In Java, comparing two
Integercounts with!=. That compares references, and it breaks once counts pass 127. Unbox them tointfirst. - Taking a whole bucket at the end. Stop as soon as you have
kvalues, even in the middle of a bucket.
Frequently asked questions4
What is the time complexity of Top K Frequent Elements?
Counting takes O(n). Picking the top k then costs O(d log d) with a sort over the d distinct values, O(d log k) with a min-heap of size k, and O(n) plus one pass over the value range with bucket sort. Since d can reach n, sorting is O(n log n) in the worst case and bucket sort is linear.
Can Top K Frequent Elements be solved in O(n) time?
Yes, with bucket sort. Counts are whole numbers from 1 to n, so each value goes into the bucket of its count, and reading the buckets from the highest count down lists the values by frequency without any comparison sort. Quickselect on the counts is also O(n) on average, but its worst case is quadratic.
Why use a min-heap and not a max-heap?
A max-heap of all d values works too: build it in O(d) and pop k times, O(d + k log d) in total. A min-heap of size k holds only k entries and suits values that arrive one at a time, because its top is the candidate to drop. The price is that it releases the answer in reverse, so you fill the result from the back.
How do you break ties in Top K Frequent Elements?
Pick one rule and apply it everywhere; here equal counts put the smaller value first, which makes the answer unique. In a sort, compare counts and then values. In a heap, of two equal counts the larger value is the weaker one. In a bucket sort, fill the buckets in ascending order of value, and each bucket is already in tie order.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def topKFrequent(nums, k):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Expected
[4, 1]