Top k most frequent element in a stream

#1

in the logic given in editorial,what is the need to create vector of size k+1, why cannot vctor of size k work??
and like everytime we are pointing to the top[k] = arr[m] …isn’t this going to make only 1 element present int the vector,if we are always assigning eleemnt to kth index how are we suppose to maintain 2 values in the vectos? tehere will obviously only 1 value in the vecotr

#2

vector of size k+1 is created is to simplify the code.
check the line were we call find() method. when vector top wont contain the element , what will top return? it will return top.end()-1. and if you analyze carefully, on a vector of size k+1, top.end()-1 is k. so the comparison will start from index k.
all the comparison can be done inside vector only, no need for another variable.

you can do it without taking vector of size k+1 also. you just need another variable to store coming element and you need to handle two cases , when element is found and when it is not found.
try to write code with vector of size k. you will realize that taking k+1 compresses the code in the way like handling only one case instead of two.

now after assigning top[k] = arr[m], we are moving this element to the left as well … at its right position based on the frequency… so the first coming value will no longer be at kth index, it will move to 0th index before 2nd element arrives.

try to dry run the sample test case through the algorithm, you will better understand the working.

thanks

#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.