Approach Summary
Count frequencies with a map. Use a min-heap of size k or bucket sort by frequency for O(n) solution.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Min-Heap of Size k | O(N log k) | O(N) | Maintains a min-heap containing at most k elements ordered by frequency, evicting the smallest frequency when size exceeds k. |
| 2 Approach 2: Bucket Sort (Linear Time O(N)) (Optimal) | O(N) | O(N) | Groups numbers into an array of buckets indexed by their frequency, collecting k numbers from highest frequency bucket downward. |
Step 1: Baseline
Approach 1: Min-Heap of Size k
Time: O(N log k)
Space: O(N)
1. Count frequencies of all numbers in a hash map `freq` in O(N) time. 2. Instantiate a Min-Heap comparing pairs by frequency. 3. Iterate over each unique `(number, frequency)` pair in the hash map: - Push `(frequency, number)` onto the min-heap. - If `heap.size() > k`, pop the top element (the element with the lowest frequency among the current k + 1 candidates). 4. After examining all unique numbers, the heap holds the top k frequent numbers. 5. Extract all remaining elements into the output array in O(k log k) time.
Approach 1: Min-Heap of Size k Implementation
Approach 1: Min-Heap of Size k
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (Map.Entry<Integer, Integer> e : map.entrySet()) {
minHeap.add(new int[]{e.getKey(), e.getValue()});
if (minHeap.size() > k) minHeap.poll();
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = minHeap.poll()[0];
return res;
}
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int n : nums) count[n]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (auto& [num, freq] : count) {
pq.push({freq, num});
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
};import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for freq, num in heap]var topKFrequent = function(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Sort unique elements by frequency descending
const unique = Array.from(freq.keys());
unique.sort((a, b) => freq.get(b) - freq.get(a));
return unique.slice(0, k);
}; Step 2: Most Optimized
Approach 2: Bucket Sort (Linear Time O(N)) (Optimal)
Time: O(N)
Space: O(N)
1. Build frequency map `count` of size at most N. 2. Create an array of buckets `buckets` of length `N + 1`, where `buckets[i]` holds a list of numbers appearing `i` times. 3. Populate `buckets[count[num]].append(num)` for each distinct number. 4. Traverse `buckets` in reverse from index N down to 0. 5. Append elements to the result list until `result.length == k`. 6. Because iterating over buckets and unique elements takes at most O(N), runtime is strictly linear O(N) without any logarithmic heap factors.
Approach 2: Bucket Sort (Linear Time O(N)) (Optimal) Implementation
Approach 2: Bucket Sort (Linear Time O(N)) (Optimal)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);
List<Integer>[] buckets = new List[nums.length + 1];
for (int key : count.keySet()) {
int freq = count.get(key);
if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
buckets[freq].add(key);
}
int[] res = new int[k];
int idx = 0;
for (int i = buckets.length - 1; i > 0 && idx < k; i--) {
if (buckets[i] != null) {
for (int num : buckets[i]) {
res[idx++] = num;
if (idx == k) return res;
}
}
}
return res;
}
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int n : nums) count[n]++;
vector<vector<int>> buckets(nums.size() + 1);
for (auto& [num, freq] : count) {
buckets[freq].push_back(num);
}
vector<int> res;
for (int i = buckets.size() - 1; i > 0 && res.size() < k; i--) {
for (int num : buckets[i]) {
res.push_back(num);
if (res.size() == k) return res;
}
}
return res;
}
};from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
res = []
for freq in range(len(buckets) - 1, 0, -1):
for num in buckets[freq]:
res.append(num)
if len(res) == k:
return res
return resvar topKFrequent = function(nums, k) {
const count = new Map();
for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
const buckets = Array.from({length: nums.length + 1}, () => []);
for (const [num, freq] of count.entries()) {
buckets[freq].push(num);
}
const res = [];
for (let i = buckets.length - 1; i > 0 && res.length < k; i--) {
for (const num of buckets[i]) {
res.push(num);
if (res.length === k) return res;
}
}
return res;
};Edge Cases to Watch
- k equals the number of unique elements (e.g. nums = [1, 2, 3], k = 3) — returns all distinct elements
- Array contains negative numbers (e.g. [-1, -1, 2]) — hash map handles signed integers without special handling
- All elements identical (e.g. [1, 1, 1, 1], k = 1) — returns [1]
- k = 1 — immediately returns the single mode of the array
Algorithmic Pattern
View Pattern Guide →
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
Framework: Hash Map / Set • Interview Prep: Tested at FAANG •
Explore all Hash Map / Set problems & invariants →
How to Recognize This Pattern
- Find k most frequent elements
Complexity Analysis
Time Complexity
O(n log k)
Space Complexity
O(n)
Tags
Array Hash Map Heap Bucket Sort
Frequently Asked Questions
What is the optimal time and space complexity for Top K Frequent Elements?
The optimal solution for Top K Frequent Elements achieves O(n log k) runtime complexity and requires O(n) auxiliary space. Time Complexity is O(N) using the Bucket Sort approach or O(N log k) using the Min-Heap approach, where N is the number of elements in nums and k is the number of top elements requested. Since k <= N, both are substantially faster than sorting all distinct elements O(N log N). Space Complexity is O(N) to store element counts in the hash map and the heap or bucket structure.
How do I identify that Top K Frequent Elements requires the Hash Map / Set pattern?
In technical interviews, look for key problem signals: Find k most frequent elements. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Hash Map / Set strategy.
What critical edge cases must be handled in Top K Frequent Elements?
Essential edge cases to verify include: k equals the number of unique elements (e.g. nums = [1, 2, 3], k = 3) — returns all distinct elements; Array contains negative numbers (e.g. [-1, -1, 2]) — hash map handles signed integers without special handling; All elements identical (e.g. [1, 1, 1, 1], k = 1) — returns [1]; k = 1 — immediately returns the single mode of the array. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Top K Frequent Elements?
Top K Frequent Elements is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Google.