How can approach this problem?
So I thought of unordered_map to store frequency of numbers and min Heap but it’s complicated. I need new approach! Any hint!
Top K Most Frequent Number in a Stream Concept
hello @Kinjal you are thinking some way right you can implement this question with the help of priority queue . in this question there will two heaps both max and min heap .
and suppose first element of your array is your median so push it directly in the max heap.
then you will run your loop from 1 uptil the length of the array .
then there will be 3 conditiond
1.if the length of the maxheap is greter than the min heap and in that also if you element is less then median then you need to push the element in the max heap but as you have noticed that max heap size is greater them the minheap that’s why you will first push the top most elemnt in the min heap you will pop max heap top element and then you will push the a[i] in the max heap.
and if the element is greater then the median then you will push the element directly in the min heap .
and then there comes the second condition in which if the size of the min and max heap are same . then the element of the array is your median .and if the element is greater then the current median then it will be pushed in the min heap and if the element is smaller then the median then it will be pushed in the max heap .
then there will be third condition in which the size of the minheap is greater then the maxheap then there will be vice versa of 1st condition .
here for your reference i am attaching the code ":https://ide.codingblocks.com/s/328588
if you have any query please write here .
i hope i have cleared your doubt .
Happy Learning !!
Bro, I’m sorry. It’s top K most frequent number in a stream. Not running median in a stream.
@Kinjal here is the code for the same https://ide.codingblocks.com/s/328760
tell me if you dont understand anything in the code .
1 Like
I did this way using priority queue but it’s inefficient tho. Anyway, this code worked.
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.