Hashing: Given an array and a value k, return top k frequent elements

Problem Statement:

Given an array and a value k, return top k frequent elements.

Example:

Input: arr = [1, 2, 1, 2, 2, 2, 1], k = 2

Output: [1, 2]

Solution Explanation:

We will use hashmap to solve the problem.

We will use map to store the frequency of each element.

Add the details into a vector as a pair with element and the frequency.

Then iterate through the vector and print the result for k elements.

Time Complexity: O(n log n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <map>

using namespace std;

vector<int> solution(vector<int>& nums, int k) 
{
    vector<int> ans;
    map<int,int> mp;

    for(int i=0;i<nums.size();i++)
        mp[nums[i]]++;

    vector<pair<int,int>>v;

    for(auto it : mp )
        v.push_back(make_pair(it.second,it.first));

    sort(v.rbegin(),v.rend());

    for(int i=0; i<v.size() && k!=0 ;i++)
    {
        ans.push_back(v[i].second);
        k--;
    }
    
    return ans; 
}


int main() 
{
    vector<int> a = {1, 1, 2, 2, 2, 1, 1, 3, 4};
    int x = 2;

    vector<int> result = solution(a, x);

    for(auto num : result )
    	cout<< num <<endl;


    return 0;     
}

Output

1
2