Top k most frequent number in a stream

#1

I’m unable to figure out how to write its code

#2

Do you want me to give you code for this problem
?

#3

Yeah it would help me understand this problem

#4

Have coded this question for you, You can take reference from it and try to do dry run for multiple test cases. You will get the intuition. If you still have any doubts left you can feel free to ask :slight_smile:

#5

Can you please explain line 21 from this code

#6

This line means that li is that value where i have found arr[i] in vector ans and after finding the index where arr[i] is present i am subtracting the ans.begin() [starting point of vector]

else{
  li=find(ans.begin(),ans.end(),arr[i])-ans.begin();
}

Though if this code is not understandable you can ask me for a detailed explanation too as by knowing it you can code on your own too.

#7

It would be great help if you could provide its detailed explanation too.

#8

So let me explain you this question with an approach, initialise a k priority queue window that store top k frequent number.
Whenever we gets a new number we will updated its frequency and then check it if that can be a part of our window or not.
We will find the element which has least frequncy . if this frequency is less than our current element frequency’ then we will remove that least frequent element and add then add our current element in our window. For eg: See this test case.
For input:
n=5,k=2;
arr[] = 5 1 3 5 2

Explanation
So we first get 5 its freq is 1 and since its the only element we print it :5
Next we get 1 its freq is 1 but its smaller than 5 so it comes before it and since k is 2 we print : 1 5
Next we get 3 now all 1 ,3 ,5 have same freq and 1,3 comes first on order so we print :1 3
Next comes 5 now 5 freq is 2 and 1,3 freq is 1 so while printing we print : 5(most freq) 1(second most freq but smaller than others having same freq)
Next comes 2 its freq is 1 so again we print :5 1

1 Like
#9

Got it thank you soo much!!

#10

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.