Top K Frequent Elements Using Heap in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a map that counts frequencies of elements.

DSA C++

std::unordered_map<int, int> freqMap;
for (int num : nums) {
    freqMap[num] [1];
}

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

A--

B++

C=

D*=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '++' resets the count instead of increasing it.

Using '--' decreases the count which is incorrect here.

We use ++ to increase the count of each number in the frequency map.

2fill in blank

medium

Complete the code to push pairs of (frequency, number) into the priority queue.

DSA C++

std::priority_queue<std::pair<int, int>> maxHeap;
for (auto& p : freqMap) {
    maxHeap.[1](std::make_pair(p.second, p.first));
}

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

Apush

Bpop

Ctop

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push removes elements instead of adding.

Using top or empty does not add elements.

We use push to add elements into the priority queue.

3fill in blank

hard

Fix the error in the loop that extracts top k elements from the heap.

DSA C++

std::vector<int> result;
for (int i = 0; i < k; i++) {
    result.push_back(maxHeap.[1]().second);
    maxHeap.pop();
}

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

Atop

Bpop

Cpush

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() to access element causes error because pop() returns void.

Using push() or empty() are incorrect for accessing elements.

We use top() to access the element at the top of the heap before popping it.

4fill in blank

hard

Fill both blanks to create a min-heap that stores pairs of (frequency, number).

DSA C++

auto cmp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.[1] > b.[2];
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> minHeap(cmp);

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

Afirst

Bsecond

Csize

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing 'second' compares the number, not frequency.

Using size or empty are invalid for pair elements.

We compare the 'first' element of pairs which is frequency to create a min-heap.

5fill in blank

hard

Fill all three blanks to insert elements into the min-heap and maintain size k.

DSA C++

for (auto& p : freqMap) {
    minHeap.[1](p);
    if (minHeap.[2]() > k) {
        minHeap.[3]();
    }
}

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

Apush

Bsize

Cpop

Dtop

Attempts:

3 left

💡 Hint

Common Mistakes

Using top() instead of size() to check heap size.

Using pop() before checking size causes errors.

We push elements, check size, and pop smallest to keep top k frequent elements.

Practice

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

easy

A. To efficiently keep track of the top k 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 problem goal

   The problem requires finding the k elements that appear most frequently.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top k frequent elements by maintaining a structure where the smallest frequency is easily accessible and can be replaced if a more frequent element is found.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top k tracking [OK]

Hint: Heap keeps smallest frequency on top for quick replacement [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple array storage
• Assuming heap removes duplicates

2. Which of the following C++ STL containers is best suited to implement a min-heap for the Top K Frequent Elements problem?

easy

A. std::vector with std::make_heap and std::pop_heap

B. std::list

C. std::map

D. std::queue

Solution

1. Step 1: Identify heap implementation in C++ STL

   C++ STL uses a vector with heap algorithms like std::make_heap, std::pop_heap, and std::push_heap to implement heaps.

2. Step 2: Check other container suitability

   std::list and std::queue do not support heap operations directly. std::map is a balanced tree, not a heap.

3. Final Answer:

   std::vector with std::make_heap and std::pop_heap -> Option A

4. Quick Check:

   Vector + heap algorithms = min-heap [OK]

Hint: Use vector + heap functions for heap in C++ [OK]

Common Mistakes:

• Choosing std::map thinking it is a heap
• Using std::queue which is FIFO, not heap
• Using std::list which lacks random access

3. What is the output of the following C++ code snippet for nums = {1,1,1,2,2,3} and k = 2?

std::vector<int> nums = {1,1,1,2,2,3};
int k = 2;
// Frequency map
std::unordered_map freq;
for (int n : nums) freq[n]++;

// Min heap to store pairs (frequency, element)
std::priority_queue, std::vector>, std::greater<>> minHeap;

for (auto& p : freq) {
    minHeap.push({p.second, p.first});
    if (minHeap.size() > k) minHeap.pop();
}

std::vector<int> result;
while (!minHeap.empty()) {
    result.push_back(minHeap.top().second);
    minHeap.pop();
}
std::reverse(result.begin(), result.end());
for (int x : result) std::cout << x << " ";

medium

A. 3 2

B. 2 3

C. 1 3

D. 1 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

   Insert (3,1), (2,2), (1,3). When size exceeds 2, pop smallest frequency. After all insertions, heap contains (2,2) and (3,1).

3. Step 3: Extract and reverse result

   Extracting gives elements 2 and 1, reversed to 1 2.

4. Final Answer:

   1 2 -> Option D

5. Quick Check:

   Top 2 frequent = 1 and 2 [OK]

Hint: Heap keeps smallest freq; pop when size > k [OK]

Common Mistakes:

• Not reversing the result vector
• Confusing element and frequency in pairs
• Popping wrong element from heap

4. Identify the bug in this code snippet for finding top k frequent elements:

std::unordered_map freq;
for (int n : nums) freq[n]++;

std::priority_queue> maxHeap;
for (auto& p : freq) {
    maxHeap.push({p.second, p.first});
    if (maxHeap.size() > k) maxHeap.pop();
}

std::vector<int> result;
while (!maxHeap.empty()) {
    result.push_back(maxHeap.top().second);
    maxHeap.pop();
}

medium

A. Frequency map is not created correctly

B. Using maxHeap and popping when size > k removes most frequent elements

C. Result vector is not reversed before output

D. Priority queue should store only elements, not pairs

Solution

1. Step 1: Understand heap type and popping logic

   maxHeap stores pairs with highest frequency on top. Popping when size > k removes the top (most frequent) element, which is wrong.

2. Step 2: Correct approach

   Use a minHeap to keep smallest frequency on top and pop it when size > k, so top k frequent remain.

3. Final Answer:

   Using maxHeap and popping when size > k removes most frequent elements -> Option B

4. Quick Check:

   MaxHeap pop removes top freq, wrong for top k [OK]

Hint: Pop from minHeap, not maxHeap, to keep top k [OK]

Common Mistakes:

• Using maxHeap and popping top element
• Not reversing result vector if needed
• Ignoring frequency-element pair structure

5. Given a large input array with many elements having the same frequency, how can you modify the heap approach to ensure the Top K Frequent Elements always returns the smallest elements when frequencies tie? Choose the best approach.

hard

A. Use a hash map only without any heap

B. Use a max-heap ordered by frequency only

C. Use a min-heap ordered by frequency, then by element value descending

D. Sort the entire array before building the heap

Solution

1. Step 1: Understand tie-breaking requirement

   When frequencies tie, we want the smaller element to come first in the top k.

2. Step 2: Modify heap ordering

   Use a min-heap that orders pairs by frequency first, then by element value ascending to break ties correctly.

3. Step 3: Why other options fail

   Max-heap ignores tie-break order, sorting entire array is inefficient, and hash map alone cannot find top k efficiently.

4. Final Answer:

   Use a min-heap ordered by frequency, then by element value ascending -> Option C

5. Quick Check:

   Min-heap with tie-break by element value [OK]

Hint: Tie-break by element value in heap comparator [OK]

Common Mistakes:

• Ignoring tie-break condition in heap
• Sorting entire array wastes time
• Using hash map alone without heap