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.