Top K Frequent Elements: Frequency Heap Pattern

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.

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]
  

Sample Dry Run

Complexity

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

The smallest frequency among the current top k should be easiest to remove.

m is the number of unique values in the input.

Frequency map plus size-k heap.