Top K Frequent Elements medium
Description
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Examples
> Case 1:
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
# 1 appears 3 times; 2 appears 2 times — those are the top 2.
> Case 2:
Input: nums = [1], k = 1
Output: [1]Constraints
1 <= nums.length <= 10^5kis guaranteed to be in[1, number of distinct elements]
Intuition
The problem decomposes into two steps:
- Count the frequencies — that’s just a hash map:
Counter(nums)in Python,unordered_map<int,int>in C++,HashMap<Integer,Integer>in Java. O(n). - Find the K largest counts. Same pattern as Kth Largest Element: a size-K min-heap, but the priority is the frequency and the payload is the element.
The min-heap holds the K elements with the highest counts seen so far. The root is the one with the smallest count among the K — so a new element with a higher count kicks it out.
Code
Bucket sort — the linear alternative
When the counts are bounded (and here they are — no count can exceed n), there’s a faster trick: bucket sort by frequency. Create n + 1 buckets where bucket[i] is “elements that appear exactly i times.” Walk the buckets from high to low and collect the first K elements you find. O(n) total.
def top_k_frequent_bucket(nums, k):
freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for val, cnt in freq.items():
buckets[cnt].append(val)
result = []
for i in range(len(buckets) - 1, 0, -1):
for val in buckets[i]:
result.append(val)
if len(result) == k:
return resultIn an interview, either is acceptable. Heap = the general pattern, bucket sort = the optimal answer for this specific shape.
The same frequency + heap template solves Sort Characters by Frequency, Reorganize String, Task Scheduler, K Most Common Words, and many more. Once you spot the pattern (count → top K by count), the implementation is identical.
Analysis
| Approach | Time | Space |
|---|---|---|
| Heap (this page) | O(n log k) | O(n) |
| Bucket sort | O(n) | O(n) |
| Sort by frequency | O(n log n) | O(n) |