Top K Frequent Elements Heap DSA Solution - Study Chapter | QuizMaker
Top K Frequent Elements explained with full sort brute force, optimized frequency heap, dry run, edge cases, complexity, and Python, C++, Java code.
- Read
- 12m
- Type
- Chapter
- Access
- Free
Course
DSA Course: Interview Patterns and Problem Solving
Topic
Module 12: Heap & Priority Queue
Learning Outcome
After this lesson, you should be able to combine a frequency map with a size-k heap to rank values.
Problem Statement
Given an integer array and k, return the k elements that appear most frequently.
| Input | Output | Why |
|---|---|---|
nums = [1,1,1,2,2,3], k = 2 | [1,2] | 1 appears three times and 2 appears twice. |
Brute Force Approach
Count frequencies, then sort every unique value by frequency. This works but costs extra sorting time.
Optimized Approach
Count frequencies and maintain a min-heap of size k by frequency. The heap discards lower-frequency values.
Exact Pseudocode
freq = value counts
heap = empty min heap by frequency
for each value and count:
push (count, value)
if heap size is greater than k:
pop smallest frequency
return values from heap
Reference Code
import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums, k):
heap = []
for value, count in Counter(nums).items():
heapq.heappush(heap, (count, value))
if len(heap) > k:
heapq.heappop(heap)
return [value for count, value in heap]
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int x : nums) freq[x]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
for (auto& entry : freq) {
int value = entry.first;
int count = entry.second;
heap.push({count, value});
if (heap.size() > k) heap.pop();
}
vector<int> answer;
while (!heap.empty()) {
answer.push_back(heap.top().second);
heap.pop();
}
return answer;
}
};
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
heap.offer(new int[] {entry.getValue(), entry.getKey()});
if (heap.size() > k) heap.poll();
}
int[] answer = new int[k];
for (int i = 0; i < k; i++) answer[i] = heap.poll()[1];
return answer;
}
}
Sample Dry Run
| Step | State | Result |
|---|---|---|
| Count | 1:3, 2:2, 3:1 | Frequency map ready |
| Push 1 and 2 | heap size is 2 | Both remain |
| Push 3 | frequency 1 is smallest | 3 is popped |
| Return | heap has 1 and 2 | top k frequent values |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n + m log k) | n counts input values and m unique values are processed by the heap. |
| Space | O(m) | The frequency map stores m values and the heap stores k values. |
Edge Cases
- If k equals the number of unique values, return all unique values.
- Output order is usually not important unless specified.
- Values can be negative or repeated many times.
Interview Checklist
- Heap must rank by frequency, not raw value.
- Keep heap size at most k.
- Build the frequency map before ranking.
FAQs
Why use a min-heap?The smallest frequency among the current top k should be easiest to remove.
What does m mean?m is the number of unique values in the input.
What is the core pattern?Frequency map plus size-k heap.
Tags
- dsa
- heap-priority-queue
- frequency heap