Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Examples
nums = [1,1,1,2,2,3], k = 2
[1,2]
Element 1 appears 3 times, element 2 appears 2 times.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4 - •
k is in the range [1, the number of unique elements in the array] - •
It is guaranteed that the answer is unique.
Approaches
Count frequencies, then sort by frequency and return the top k.
def top_k_frequent(nums, k):
from collections import Counter
count = Counter(nums)
sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)
return [item[0] for item in sorted_items[:k]]Use a min heap of size k to keep track of the k most frequent elements.
def top_k_frequent(nums, k):
from collections import Counter
import heapq
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)Use bucket sort where index represents frequency. Collect from highest bucket.
Diagram
def top_k_frequent(nums, k):
from collections import Counter
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return resultComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sorting by Frequency | O(n log n) | O(n) | Count frequencies, then sort by frequency and return the top k. |
| Min Heap | O(n log k) | O(n + k) | Use a min heap of size k to keep track of the k most frequent elements. |
| Bucket Sort | O(n) | O(n) | Use bucket sort where index represents frequency. Collect from highest bucket. |
Count frequencies, then sort by frequency and return the top k.
Use a min heap of size k to keep track of the k most frequent elements.
Use bucket sort where index represents frequency. Collect from highest bucket.
Common Mistakes
Using a max heap when a min heap of size k is more efficient
Forgetting that bucket sort works because max frequency is at most n
Not handling the case where multiple elements have the same frequency