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.