Top K most frequent number in stream

#1

How to solve this using Heaps?

#2

Hello @dsingh200021,

As we have to keep track of each input in the stream even if it’s not currently the top k elements because it is possible that the next 4 elements in the stream can be this number.
So, keeping track of its previous count is also important.
Also, you are required to delete k elements from the heap, each time a query is made to view top k elements.

Tus, considering the above limitations I would suggest you to not to use the heap for this problem.
Using Hashmap will produce an optimal solution:

Approach:

  1. Iterate through the array which contains stream of numbers.
  2. To keep track of top k elements, make a top vector of size k+1.
  3. 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.
  4. 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.
  5. And make that list of k+1 numbers sorted according to frequency and their value.
  6. Print top k elements form top vector.
  7. Repeat the above steps for every element in the stream.

Hope, this would help.
Give a like, if you are satisfied.

#3

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.