Top K Frequent Elements Using Heap in DSA Java

Mental Model

We want to find the K numbers that appear most often in a list by counting frequencies and keeping only the top K using a special list that quickly removes the smallest frequency.

Analogy: Imagine you have a basket of fruits and want to keep only the top K types that appear most often. You count each fruit type, then keep a small basket that always drops the least frequent fruit when a new more frequent one comes in.

Input array: [1, 1, 1, 2, 2, 3]
Frequency map: {1:3, 2:2, 3:1}
Min-heap (size K=2):
  [ (1,3), (2,2) ]  ← keeps top 2 frequent elements
Output: [1, 2]

Dry Run Walkthrough

Input: array: [1, 1, 1, 2, 2, 3], k=2

Goal: Find the 2 numbers that appear most frequently

Step 1: Count frequency of each number

Frequency map: {1:3, 2:2, 3:1}

Why: We need to know how often each number appears to find the top K

Step 2: Add (1,3) to min-heap

Min-heap: [(1,3)]

Why: Start building heap with first frequency

Step 3: Add (2,2) to min-heap

Min-heap: [(2,2), (1,3)]

Why: Add second frequency, heap keeps smallest frequency on top

Step 4: Add (3,1) to min-heap, size exceeds k=2, remove smallest frequency (3,1)

Min-heap: [(2,2), (1,3)]

Why: Keep heap size at k by removing least frequent element

Step 5: Extract elements from heap as top K frequent

Result: [1, 2]

Why: Heap now contains the top 2 frequent elements

Result:

Min-heap: [(2,2), (1,3)]
Top K frequent elements: [1, 2]

Annotated Code

DSA Java

import java.util.*;

public class TopKFrequent {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        // Count frequency of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Min-heap to keep top k frequent elements
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue)
        );

        // Add entries to heap, keep size at most k
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.offer(entry); // add entry to heap
            if (minHeap.size() > k) {
                minHeap.poll(); // remove smallest frequency
            }
        }

        // Extract keys from heap
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().getKey());
        }
        Collections.reverse(result); // optional: highest frequency first
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        List<Integer> topK = topKFrequent(nums, k);
        System.out.println(topK);
    }
}

freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);

Count frequency of each number in the array

PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

Create min-heap ordered by frequency

minHeap.offer(entry);

Add frequency entry to heap

if (minHeap.size() > k) { minHeap.poll(); }

Remove smallest frequency if heap size exceeds k

while (!minHeap.isEmpty()) { result.add(minHeap.poll().getKey()); }

Extract keys from heap to get top K frequent elements

Output

[1, 2]

Complexity Analysis

Time: O(n log k) because we count frequencies in O(n) and maintain a heap of size k for all unique elements

Space: O(n) for frequency map and heap in worst case when all elements are unique

vs Alternative: Using sorting all frequencies would be O(n log n), heap reduces this to O(n log k) which is faster when k is small

Edge Cases

Empty array

Returns empty list since no elements to process

DSA Java

freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);

k equals number of unique elements

Returns all unique elements sorted by frequency

DSA Java

if (minHeap.size() > k) { minHeap.poll(); }

All elements have same frequency

Returns any k elements since frequencies tie

DSA Java

minHeap.offer(entry);

When to Use This Pattern

When asked to find the top K frequent items efficiently, use a min-heap to keep track of the K largest frequencies without sorting all elements.

Common Mistakes

Mistake: Using a max-heap and extracting all elements instead of a min-heap of size k
Fix: Use a min-heap of size k to keep only top K frequent elements, removing smaller frequencies as you go

Mistake: Not reversing the result list after extracting from min-heap, resulting in ascending frequency order
Fix: Reverse the result list to get descending order of frequency if needed

Summary

Find the K most frequent elements in an array using a frequency map and a min-heap.

Use when you need the top K frequent items efficiently without sorting all elements.

Keep a min-heap of size K to quickly discard less frequent elements and keep only the top K.

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements Using Heap problem?

easy

A. To efficiently keep track of the top K frequent elements by frequency

B. To sort all elements in ascending order

C. To store elements without any order

D. To remove duplicates from the list

Solution

1. Step 1: Understand the role of a heap

   A heap is a special tree-based data structure that helps quickly find the smallest or largest element.

2. Step 2: Apply heap to top K frequent elements

   Using a min-heap of size K allows us to keep track of the K elements with the highest frequency efficiently.

3. Final Answer:

   To efficiently keep track of the top K frequent elements by frequency -> Option A

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps smallest or largest element on top for quick access [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Using heap to remove duplicates
• Ignoring frequency counts

2. Which of the following Java code snippets correctly declares a min-heap to store integer frequencies for the top K frequent elements problem?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> b - a);

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);

Solution

1. Step 1: Understand Java PriorityQueue default behavior

   By default, PriorityQueue is a min-heap, ordering elements in ascending order.

2. Step 2: Check comparator for min-heap with custom size

   The comparator (a, b) -> a - b keeps the natural ascending order, suitable for min-heap.

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b); -> Option D

4. Quick Check:

   Comparator a-b = min-heap [OK]

Hint: Use (a, b) -> a - b for min-heap comparator in Java [OK]

Common Mistakes:

• Using reverseOrder() creates max-heap, not min-heap
• Wrong comparator sign reverses heap order
• Not specifying initial capacity k is okay but less efficient

3. What will be the output of the following Java code snippet that finds the top 2 frequent elements?

int[] nums = {1,1,1,2,2,3};
int k = 2;
Map freqMap = new HashMap<>();
for (int num : nums) freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
for (int key : freqMap.keySet()) {
    minHeap.offer(key);
    if (minHeap.size() > k) minHeap.poll();
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) result.add(minHeap.poll());
Collections.reverse(result);
System.out.println(result);

medium

A. [2, 1]

B. [1, 2]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequencies

   Frequencies: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time.

2. Step 2: Use min-heap to keep top 2 frequent elements

   Heap keeps smallest frequency on top. Insert keys: 1(3), 2(2), 3(1). When size > 2, remove smallest frequency. After all insertions, heap contains 1 and 2.

3. Step 3: Extract and reverse result

   Polling heap gives [2,1], reversing gives [1,2].

4. Final Answer:

   [1, 2] -> Option B

5. Quick Check:

   Top 2 frequent = [1, 2] [OK]

Hint: Heap keeps least frequent; remove to keep top K [OK]

Common Mistakes:

• Not reversing the result list
• Confusing min-heap with max-heap behavior
• Ignoring frequency counts in comparator

4. Identify the error in the following Java code snippet for finding top K frequent elements:

int[] nums = {4,4,4,6,6,7};
int k = 2;
Map freqMap = new HashMap<>();
for (int num : nums) freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
for (int key : freqMap.keySet()) {
    minHeap.offer(key);
    if (minHeap.size() > k) minHeap.poll();
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) result.add(minHeap.poll());
System.out.println(result);

medium

A. Frequency map is not updated correctly

B. Heap size check condition is incorrect

C. Comparator reverses order causing max-heap instead of min-heap

D. Result list is not reversed before printing

Solution

1. Step 1: Analyze comparator in PriorityQueue

   The comparator (a, b) -> freqMap.get(b) - freqMap.get(a) creates a max-heap (largest frequency on top).

2. Step 2: Understand heap usage for top K frequent elements

   We need a min-heap to remove the smallest frequency when size exceeds k, but max-heap removes largest, causing wrong elements to be removed.

3. Step 3: Identify the error

   The comparator should be (a, b) -> freqMap.get(a) - freqMap.get(b) for min-heap behavior.

4. Final Answer:

   Comparator reverses order causing max-heap instead of min-heap -> Option C

5. Quick Check:

   Wrong comparator = max-heap error [OK]

Hint: Min-heap comparator: a-b; max-heap: b-a [OK]

Common Mistakes:

• Using max-heap instead of min-heap for top K
• Not reversing result list after polling
• Incorrect frequency counting

5. Given an array nums = {5,3,1,1,1,3,73,1} and k = 2, which approach correctly returns the top K frequent elements using a heap? Choose the best sequence of steps.

hard

A. Count frequencies, use min-heap of size k with frequency comparator, add elements, remove smallest when size > k, then extract result

B. Use a hash set to store unique elements, then pick any k elements

C. Sort array, pick last k elements directly

D. Count frequencies, use max-heap to store all elements, poll k times for top elements

Solution

1. Step 1: Count frequencies of elements

   Frequencies: 1 -> 4 times, 3 -> 2 times, 5 -> 1 time, 73 -> 1 time.

2. Step 2: Use min-heap of size k with frequency comparator

   Insert elements into min-heap; if size exceeds k, remove smallest frequency element to keep top k frequent elements.

3. Step 3: Extract elements from heap for result

   After processing, heap contains elements with highest frequencies: 1 and 3.

4. Final Answer:

   Count frequencies, use min-heap of size k with frequency comparator, add elements, remove smallest when size > k, then extract result -> Option A

5. Quick Check:

   Min-heap size k keeps top K frequent [OK]

Hint: Use min-heap size k to keep top frequent elements [OK]

Common Mistakes:

• Using max-heap and polling k times is less efficient
• Sorting array ignores frequency counts
• Using hash set loses frequency info