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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top K Frequent Elements with Min-Heap

What is the output of the following C++ code that finds the top 2 frequent elements using a min-heap?

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;

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

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

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << " ";
    return 0;
}

A [1, 2]

B [2, 1]

C [3, 2]

D [1, 3]

💡 Hint

Remember that the min-heap keeps the least frequent element at the top, so the final vector is built by popping from the heap.

The min-heap keeps the top k frequent elements with the smallest frequency at the top. After pushing all elements, popping them gives the least frequent among the top k first. So the output order is from least to most frequent among the top k. Frequencies: 1->3, 2->2, 3->1. Top 2 are 1 and 2. The heap pops 2 first, then 1, so output is [2, 1].

🧠 Conceptual

intermediate

Understanding Heap Usage in Top K Frequent Elements

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

A Because a max-heap cannot be used with frequency counts.

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

C Because a min-heap keeps the smallest frequency at the top, allowing easy removal of less frequent elements when size exceeds k.

D Because a min-heap uses less memory than a max-heap.

💡 Hint

Think about how to keep only the top k frequent elements while processing all frequencies.

Using a min-heap of size k allows us to keep the k most frequent elements by removing the smallest frequency element whenever the heap grows beyond k. This way, the heap always contains the top k frequent elements efficiently.

🔧 Debug

advanced

Identify the Error in Top K Frequent Elements Code

What error will this code produce when trying to compile?

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;

    auto cmp = [](pair<int,int> a, pair<int,int> b) { return a.second > b.second; };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> minHeap(cmp);

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

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << " ";
    return 0;
}

A Error: cannot convert lambda to function pointer for decltype(cmp)

B Error: priority_queue requires default constructor for comparator

C Error: missing semicolon after lambda definition

D No error, code compiles and runs correctly

💡 Hint

Check how the lambda comparator is declared and used with priority_queue.

The lambda comparator is declared as a non-capturing lambda but used with decltype(cmp) without an instance passed to priority_queue constructor. This causes a compilation error because priority_queue expects a comparator object, not just a type.

❓ Predict Output

advanced

Output of Top K Frequent Elements with Equal Frequencies

What is the output of this code when multiple elements have the same frequency?

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;

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

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

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    return result;
}

int main() {
    vector<int> nums = {4,4,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 3);
    for (int x : res) cout << x << " ";
    return 0;
}

A [1, 2, 4]

B [2, 1, 4]

C [3, 2, 1]

D [4, 3, 2]

💡 Hint

Elements 4,1,2 all have frequency 2, 3 has frequency 1. The min-heap keeps top 3 frequent elements.

Frequencies: 4->2, 1->2, 2->2, 3->1. Top 3 frequent are 4,1,2. The min-heap pops the smallest frequency first, so 3 is excluded. The output order is from least to most frequent among top k, so 3 is excluded and output is [1, 2, 4].

🚀 Application

expert

Find Top K Frequent Words Using Heap

Given a list of words, which code snippet correctly returns the top 2 frequent words sorted by frequency and then lexicographically?

A

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

vector<string> topKFrequentWords(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    auto cmp = [&](pair<string,int>& a, pair<string,int>& b) {
        if (a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    };

    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> minHeap(cmp);

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

    vector<string> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

B

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

vector<string> topKFrequentWords(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    auto cmp = [&](pair<string,int>& a, pair<string,int>& b) {
        if (a.second == b.second) return a.first > b.first;
        return a.second > b.second;
    };

    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> minHeap(cmp);

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

    vector<string> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

C

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

vector<string> topKFrequentWords(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    auto cmp = [&](pair<string,int>& a, pair<string,int>& b) {
        if (a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    };

    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> minHeap(cmp);

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

    vector<string> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

D

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

vector<string> topKFrequentWords(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;

    auto cmp = [&](pair<string,int>& a, pair<string,int>& b) {
        if (a.second == b.second) return a.first > b.first;
        return a.second < b.second;
    };

    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> minHeap(cmp);

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

    vector<string> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

💡 Hint

The comparator should keep the least frequent words at the top, and for ties, the lexicographically larger word should be removed first.

Option D uses a min-heap comparator that sorts by frequency ascending and for ties by lexicographically descending order. This ensures the heap keeps the top k frequent words, and among ties, the lexicographically smallest words remain. The reverse at the end gives the correct order.

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