Heap: Given an array, find the top K frequency elements

Coding Interview Questions

1 min read

Problem Statement:

Given an array, find the top K frequency elements

Solution Explanation:

We will use frequency array and then use min heap to solve the problem.

Time Complexity: O(n + k*log k)
Space Complexity: O(d)

Code Solution

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

using namespace std;

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

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(auto &p : freq)
    {
        pq.push({p.second, p.first});
        if(pq.size() > k)
        {
            pq.pop();
        }
    }
    
    vector<int> res;
    while(!pq.empty())
    {
        res.push_back(pq.top().second);
        pq.pop();
    }
    return res;
}

int main() 
{

    vector<int> arr = {1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 6};
    int k = 2;

    vector<int> res = solution(arr, k);

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
}