Find the top k numbers in a stream by frequency

Updated

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
Comment
Mithlesh Upadhyay Published 15 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials