Problem Statement
Given an integer array and an integer k, return the k most frequent elements.
Brute Force Intuition
Count frequencies.
Sort elements based on frequency.
Return first K elements.
Complexity
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Moving Towards the Optimal Approach
We only need:
Top K Frequencies
Not the entire sorted order.
Use:
Min Heap of Size K
Pattern Recognition
Whenever you see:
Top K
K Largest
K Smallest
Think:
Heap
Optimal Approach
Step 1:
Count frequencies.
HashMap<Integer,Integer>
Step 2:
Maintain Min Heap ordered by frequency.
If heap size exceeds K:
pq.poll();
At the end:
Heap contains K most frequent elements.
Optimal Java Solution
class Solution {
public int[] topKFrequent(
int[] nums,
int k) {
HashMap<Integer,Integer> map =
new HashMap<>();
for (int num : nums) {
map.put(
num,
map.getOrDefault(num, 0) + 1
);
}
PriorityQueue<Integer> pq =
new PriorityQueue<>(
(a,b) ->
map.get(a) - map.get(b)
);
for (int key : map.keySet()) {
pq.add(key);
if (pq.size() > k)
pq.poll();
}
int[] ans =
new int[k];
int idx = 0;
while (!pq.isEmpty()) {
ans[idx++] =
pq.poll();
}
return ans;
}
}
Dry Run
nums = [1,1,1,2,2,3]
k = 2
Frequency Map:
1 → 3
2 → 2
3 → 1
Heap:
3
removed.
Remaining:
1
2
Answer:
[1,2]
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time | O(N log K) |
| Space | O(N) |
Interview One-Liner
Count frequencies using HashMap and maintain a Min Heap of size K to keep only the most frequent elements.