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.
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
One pass with a hash map counts every value. Then pick the k best: sorting all d distinct values costs O(d log d), a min-heap of size k costs O(d log k), and since counts run from 1 to n, a bucket sort orders the values by count with no comparisons.
Count, then sort by count
Intuition
Count with a hash map: [4, 1, 4, 2, 1, 4, 3, 1, 4] gives 4 → 4, 1 → 3, 2 → 1, 3 → 1. Then sort the distinct values by count, high first, and by value, low first. That comparison is exactly the answer order, so the first k entries are the answer.
Sorting d distinct values costs O(d log d), about 1.3 × 10^5 comparisons for 10^4 different values. It 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
Hold only k candidates. A new value is kept only if it beats the weakest candidate, where weaker means a lower count, or the same count and a larger value. A min-heap ordered by that rule keeps the weakest on top, read in O(1) and replaced in O(log k). A value that does not beat the top can be dropped, because k better values are already kept.
The heap is only partly sorted, and popping returns the weakest value first, so write the answer from the last position back. Choosing costs O(d log k), which beats sorting when k is much smaller than d.
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 a whole number from 1 to n, so put each value in the bucket of its count and read the buckets from n down. The values come out most frequent first, and no two counts are ever compared.
For the tie rule, count in an array of R = 2 × 10^4 + 1 counters, value v at index v + 10^4, and walk it from the smallest value up, appending each value to its bucket. Every bucket then fills in ascending order, which is the tie order. In the second example the walk puts -2, 5, 7 in bucket 2, and k = 2 takes -2 and 5.
That is O(n + R) in total. With a hash map in place of the array, the buckets fill in map order and each would need sorting.
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
- Breaking ties by first appearance or by hash map order. In the second example
-2,5and7all occur twice, and only the smaller-value rule gives[-2, 5]. - Returning the heap's array as it sits. Its top is the weakest value, the one that belongs last.
- Getting the heap's tie rule backwards. A min-heap on
(count, value)evicts the smaller value when counts tie; use(count, -value). - Making only as many buckets as there are distinct values. In
[3, 3, 3, 3]one value occursntimes, so bucketnmust exist. - In Java, comparing two
Integercounts with!=. That compares references and breaks once counts pass 127.
Frequently asked questions3
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 one pass over the counts 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, because counts are whole numbers from 1 to n. 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.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def topKFrequent(nums, k):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Expected Output
[4, 1]