Top K Frequent Elements Using Heap in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Java code using a min-heap to find top K frequent elements?

Consider the following Java code snippet that finds the top 2 frequent elements in an array using a min-heap.

import java.util.*;

public class Solution {
    public static List topKFrequent(int[] nums, int k) {
        Map freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
        for (int num : freqMap.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }

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

DSA Java

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
        for (int num : freqMap.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }

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

A [3, 2]

B [2, 1]

C [1, 3]

D [1, 2]

💡 Hint

Remember the min-heap keeps the least frequent element at the top, so after processing, the heap contains the top K frequent elements in ascending order of frequency.

The frequency map is {1=3, 2=2, 3=1}. The min-heap keeps the top 2 frequent elements. After adding all, the heap contains 1 and 2. Polling and reversing gives [1, 2].

🧠 Conceptual

intermediate

Why use a min-heap instead of a max-heap to find top K frequent elements?

In the top K frequent elements problem, why is a min-heap preferred over a max-heap when maintaining the heap size to K?

A Because a min-heap allows us to efficiently remove the least frequent element when the heap size exceeds K.

B Because a min-heap automatically sorts elements in descending order of frequency.

C Because a max-heap cannot be implemented in Java's PriorityQueue.

D Because a min-heap stores elements in ascending order, which is the final desired output order.

💡 Hint

Think about which element you want to remove when the heap size grows beyond K.

We use a min-heap to keep the smallest frequency element at the top. When the heap size exceeds K, we remove the least frequent element, ensuring the heap contains the top K frequent elements.

🔧 Debug

advanced

What error occurs when running this Java code for top K frequent elements?

Identify the error in the following code snippet:

import java.util.*;

public class Solution {
    public static List topKFrequent(int[] nums, int k) {
        Map freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue heap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
        for (int num : freqMap.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }

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

DSA Java

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
        for (int num : freqMap.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }

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

A The code runs correctly and outputs [1, 2]

B The code throws a NullPointerException

C The code outputs [3, 2]

D The comparator causes a runtime error due to integer overflow

💡 Hint

Determine if the comparator creates a min-heap or max-heap and simulate the heap operations.

The comparator (a, b) -> freqMap.get(b) - freqMap.get(a) creates a max-heap where the element with the highest frequency is at the top (pops first). When size exceeds k=2 after adding 3, it polls the most frequent (1, freq=3), leaving 2 and 3. Polling adds 2 then 3 to result, reversing gives [3, 2].

📝 Syntax

advanced

Which option fixes the syntax error in this Java PriorityQueue comparator?

Fix the syntax error in this comparator used in a PriorityQueue:

PriorityQueue heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b))

A Add a semicolon at the end: PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));

B Replace arrow with colon: PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) : freqMap.get(a) - freqMap.get(b));

C Remove parentheses: PriorityQueue<Integer> heap = new PriorityQueue<>; (a, b) -> freqMap.get(a) - freqMap.get(b);

D Add curly braces: PriorityQueue<Integer> heap = new PriorityQueue<>({a, b} -> freqMap.get(a) - freqMap.get(b));

💡 Hint

Check Java syntax for lambda expressions and statements.

The only syntax error is missing semicolon at the end of the statement. The arrow syntax is correct.

🚀 Application

expert

How many elements are in the heap after processing this input for top 3 frequent elements?

Given the input array nums = {4,4,4,1,1,2,2,3} and k = 3, how many elements remain in the min-heap after processing all frequencies?

DSA Java

Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
    freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
for (int num : freqMap.keySet()) {
    heap.offer(num);
    if (heap.size() > k) {
        heap.poll();
    }
}

A 1

B 3

C 2

D 4

💡 Hint

The heap size is limited to k by polling when size exceeds k.

The frequency map has 4 keys: 4,1,2,3. The heap size is limited to k=3, so after processing all keys, the heap size is 3.

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