Top k most frequent number---->not able to understand the question......very confusing?

#1

Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (according to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency. If frequency of two numbers are same then print them in increasing order.

Input Format
First line contains integer t as number of test cases. Each test case contains following input. First line contains integer n and k, n represents the length of the array and next line contains n space separated integers.

Constraints
1 < t < 100 1< n < 100000

Output Format
Print top k running stream.

Sample Input
1
5 2
5 1 3 5 2
Sample Output
5 1 5 1 3 5 1 5 1

#2

hi @hg11110000

Input:
1
5 2
5 1 3 5 2

here n = 5, k = 2

freq map at different points: and output.
(if freq is equal then we print the smaller element first)

freq

5 - 1

output:
5

freq
1 - 1
5 - 1

output:
1
5

freq

1 - 1
3 - 1
5 - 1

output:
1
3

freq

5 - 2
1 - 1
3 - 1

output:
5
1

freq

5 - 2
1 - 1
2 - 1
3 - 1

output:
5
1

You can combine all these outputs and see this is what is given in sample output

#3

@Ishitagambhir

how to approach it ???
not able to understand the tutorial as well using hash maps ???

also please can u give the code using priority queue also??

#4

hi @hg11110000 can you share the editorial, I can help you understand it.

#5

@Ishitagambhir
Iterate through the array which contains stream of numbers.
To keep track of top k elements, make a top vector of size k+1.
For every element in the stream increase its frequency and store it in the last position of top vector. We can use hashing for efficiently fetching frequency of an element and increasing it.
Now find the position of element in top vector and iterate from that position to zero. For finding position we can make use of the find() function in C++ STL, it returns an iterator pointing to element if found in the vector.
And make that list of k+1 numbers sorted according to frequency and their value.
Print top k elements form top vector.
Repeat the above steps for every element in the stream.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void Ktop(int *arr, int n, int k) {
    vector<int> top(k+1);
    unordered_map<int, int> freq;
    for(int m=0;m<n;m++) {
        freq[arr[m]]++;
        top[k] = arr[m];
        auto it = find(top.begin(), top.end()-1, arr[m]);
        for(int i=distance(top.begin(), it)-1;i>=0;i--) {
            if(freq[top[i]]<freq[top[i+1]]) {
                swap(top[i], top[i+1]);
            } else if(freq[top[i]]==freq[top[i+1]] and top[i]>top[i+1]) {
                swap(top[i], top[i+1]);
            } else {
                break;
            }
        }
        for (int i = 0; i < k && top[i] != 0; ++i) 
            cout << top[i] << ' '; 
    }

    cout<<endl;
}

int main(int argc, char const *argv[])
{
    /* code */
    int t;
    cin>>t;
    while(t--) {
      int n, k;
      cin>>n>>k;
      int *arr = new int[n];
      for(int i=0;i<n;i++) {
        cin>>arr[i];
      }
      Ktop(arr, n, k);
      delete [] arr;
    }
    return 0;
}
#6

this is via hashing…can u also give the code via heaps

#7

@hg11110000 hashing is just an efficient way to keep track of frequency, since we dont know the range of elements. In the unordered_map<int, int> we store pairs of element, freq and increment the frequency of elements as and when required, step by step as I illustrated in detail above. You dont have to get in the details of hashing for this, just knowing about the unordered_map data structure is enough, you can read more about it here: http://www.cplusplus.com/reference/unordered_map/unordered_map/
The top vector will keep track of the top k elements at any given point.

If there is anything specific that you did not understand in this solution, let me know I’ll explain that thing.

#8

@hg11110000 you can find the heaps solution here https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.