Top K Frequent Elements Using Heap in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a frequency map for the elements in the array.

DSA Java

Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
    freqMap.put(num, freqMap.getOrDefault(num, [1]) + 1);
}

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as default causes counts to be off by one.

Using the element itself as default causes errors.

We use 0 as the default frequency for elements not yet in the map, then add 1.

2fill in blank

medium

Complete the code to create a priority queue (min-heap) that sorts elements by frequency.

DSA Java

PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get([1]) - freqMap.get(b));

Drag options to blanks, or click blank then click option'

Anums

Ba

CfreqMap

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping 'a' and 'b' changes min-heap to max-heap.

Using freqMap instead of elements causes errors.

We compare frequencies of elements 'a' and 'b' to build a min-heap based on frequency.

3fill in blank

hard

Fix the error in the code that adds elements to the heap and maintains its size at k.

DSA Java

for (int num : freqMap.keySet()) {
    heap.offer(num);
    if (heap.size() > [1]) {
        heap.poll();
    }
}

Drag options to blanks, or click blank then click option'

AfreqMap.size()

Bnums.length

Ck

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using nums.length causes heap to grow too large.

Using 0 causes no elements to be removed.

We keep the heap size at most k to track top k frequent elements.

4fill in blank

hard

Fill both blanks to extract elements from the heap into the result list in correct order.

DSA Java

List<Integer> result = new ArrayList<>();
while (!heap.isEmpty()) {
    result.add([1]);
}
Collections.[2](result);

Drag options to blanks, or click blank then click option'

Aheap.poll()

Bheap.peek()

Creverse

Dsort

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() does not remove elements, causing infinite loop.

Sorting instead of reversing changes order incorrectly.

We poll elements from the heap and then reverse the list to get descending frequency order.

5fill in blank

hard

Fill all three blanks to complete the method that returns the top k frequent elements.

DSA Java

public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, [1]) + 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() > [2]) {
            heap.poll();
        }
    }
    List<Integer> result = new ArrayList<>();
    while (!heap.isEmpty()) {
        result.add(heap.poll());
    }
    Collections.[3](result);
    return result;
}

Drag options to blanks, or click blank then click option'

A0

Bk

Creverse

Dsort

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as default frequency causes off-by-one errors.

Not limiting heap size causes incorrect results.

Sorting instead of reversing changes order.

Default frequency is 0, keep heap size at k, then reverse the result list for correct order.

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