Given an array of n numbers, your task is to keep at most k elements at the top according to their frequency. When the stream has k or more distinct elements, print the top k numbers else print all the numbers sorted by increasing order of values. Refer to below examples for clarity.
Examples :
Input : n = 6 k = 4 arr = {5, 2, 1, 3, 2, 4}
Output : 5 2 5 1 2 5 1 2 3 5 2 1 3 5 2 1 3 4
Explanation :
Initally stream contains only 5 so print it.
then 2, since their freq is same print in sorted order.
then similarly for 1 & 3, same freq print in sorted order then 2
again, which now has highest freq so 2 1 3 5
now we have k distinct elements so when 4 arrives we have to print at
most k elements i.e.
2 1 3 4
Source: Amazon Frequently Asked Questions We will use a map to store the frequency of elements in the stream. We then use an array to store all the pairs. A compare function is designed which returns true if the freq of first element is more than the second element or if freq is same and value of first < value of second. This function is used as the third arguement to the inbuilt sort function. After sorting we display at most k elements from the array of pairs.
Implementation :
#include <bits/stdc++.h>
using namespace std;
//function used for sorting pairs
bool compare(pair<int, int> a, pair<int, int> b)
{
return (a.second == b.second) ? a.first < b.first : a.second > b.second;
}
int main()
{
int arr[] = { 5, 2, 1, 3, 2, 4 };
int n = 6, k = 4;
// map to store freq of each distinct value
// hashMap[value] = freq
map<int, int> Map;
// to traverse through the map
map<int, int>::iterator it;
//array to store (value, freq) pairs
//first = value
//second = freq
pair<int, int> Elements[100];
for (int i = 0; i < n; i++) {
// increase freq of curr element
Map[arr[i]] += 1;
//fill in all the pairs till now
int j = 0;
for (it = Map.begin(); it != Map.end(); ++it) {
Elements[j++] = make_pair(it->first, it->second);
}
// sort all the pairs acc to given constraint
sort(Elements, Elements + j, compare);
// print atmost k values
for (int t = 0; t < min(j, k); t++)
cout << Elements[t].first << " ";
}
}
Output :
5 2 5 1 2 5 1 2 3 5 2 1 3 5 2 1 3 4