Can I get a hint for this problem? I’m unable to think about how to store the number and keep track of most frequent number.
Hint for Top K most frequent number in a stream
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.
Yeah read this on GFG.
But where are we using the concept of heap in this?
we can do this without heaps as well and frequency based questions are best done with hashtables most of the time
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.
Hello @tomarvikas738,
Let’s understand this problem with the help of two examples:
1.
arr[] = {5, 2, 1, 3, 2}
k = 4
Output :
5 2 5 1 2 5 1 2 3 5 2 1 3 5
Explanation:
Given array is arr[] = {5, 2, 1, 3, 2} and k = 4
Step 1:After reading 5, there is only one element 5 whose frequency is max till now. so print 5.
Step 2:After reading 2, we will have two elements 2 and 5 with same frequency. As 2, is smaller than 5 but their frequency is same so we will print 2 5.
Step 3: After reading 1, we will have 3 elements 1,2 and 5 with same frequency, so print 1 2 5.
Step 4: Similarly after reading 3, print 1 2 3 5
Step 5: After reading last element 2, since 2 has already occurred so we have now frequency of 2 as 2. So we keep 2 at the top and then rest of element with same frequency in sorted order. So print, 2 1 3 5.
arr[] = {5, 2, 1, 3, 4}
k = 4
Output :
5 2 5 1 2 5 1 2 3 5 1 2 3 4
Explanation:
Given array is arr[] = {5, 2, 1, 3, 4} and k = 4
Step 1:After reading 5, there is only one element 5 whose frequency is max till now. so print 5.
Step 2:After reading 2, we will have two elements 2 and 5 with same frequency. As 2, is smaller than 5 but their frequency is same so we will print 2 5.
Step 3: After reading 1, we will have 3 elements 1,2 and 5 with same frequency, so print 1 2 5.
Step 4: Similarly after reading 3, print 1 2 3 5
Step 5: After reading last element 4, since 4 is smaller than 5. So we keep 4 at the top and then rest of element with same frequency in sorted order and will discard 5 as k=4. So print, 2 1 3 4.
Now, try to implement the same using the approach @AASTHA011 has explained.
Code it. If you face any issue, feel free to ask.
Hope, this would help.
Give a like if you are satisfied.
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.
I made the heap as per the given condition,but how do I keep track of the elements as they 'll keep getting popped for the next iteration?
Can you share your code.