Top k most frequent element in stream

#1

why this is not passing??

#2

Hello @shampblocks,

Your Code is failing for the test case like:

  1. 2
    5 2
    5 1 3 5 2
    5 2
    5 1 3 5 2
    ExpectedOutput:
    5 1 5 1 3 5 1 5 1
    5 1 5 1 3 5 1 5 1
    Your Output:
    5 1 5 1 3 5 1 5 1
    2 3 1 3 1 3 5 1 5 1

  2. 1
    5 3
    5 1 1 5 2
    Expected Output:
    5 1 5 1 5 1 5 1 5 2
    Your Output:
    5 1 5 1 5 1 1 5 1 1 5 2

  3. 3
    5 4
    5 2 1 3 2
    8 4
    5 1 3 5 2 1 1 3
    8 3
    5 1 3 5 2 1 1 3
    Your Output:
    5 2 5 1 2 5 1 2 3 5 2 1 3 5
    5 2 1 5 1 3 5 5 1 3 5 5 1 2 3 1 5 2 3 1 5 2 3 1 3 5 2
    5 1 1 1 5 1 1 3 5 5 1 3 5 1 2 1 5 2 1 5 2 1 3 5
    Expected Output:
    5 2 5 1 2 5 1 2 3 5 2 1 3 5
    5 1 5 1 3 5 5 1 3 5 1 2 3 1 5 2 3 1 5 2 3 1 3 5 2
    5 1 5 1 3 5 5 1 3 5 1 2 1 5 2 1 5 2 1 3 5

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

#3

can you tell me what is the problem in my approach guide me in this

#4

Sure @shampblocks,

Example 2:
1
5 3
5 1 1 5 2
You have to print top 3: here is the mistake in understanding this and that’s what you are implementing in your code.

index : expected : your code
0 : 5 : 5
1 : 1 5 : 1 5
2 : 1 5 : 1 5 1
3 : 1 5 :1 5 1
4 : 1 5 2 : 1 5 2

Reason:
Your code is printing k values though the distinct values in map are less than k.
This is because you are pushing the same element multiple times in q.

Example 1:
2
5 2
5 1 3 5 2
5 2
5 1 3 5 2
Why you are getting correct output for first test case and wrong for second though they are exactly same?
5 1 5 1 3 5 1 5 1
2 3 1 3 1 3 5 1 5 1
Reason:
Because the queue q is not empty when you are going for the next test case.
Solution:
Clear it at the end of each test case.
As there is no exact function clear exists for a priority queue.
So, pop elements until it becomes empty.

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

1 Like
#5

thanks sir i corrected it…but is there any other efficient approach for this??

#6

Hello @shampblocks,

This is itself an efficient approach as per my knowledge.
But you can implement in a different way.
You can see the following code for reference:

Let me know if you don’t understand something.

#7

Sir mine is n^2logn how this is efficient??

#8

Hello @shampblocks,

Having higher complexity doesn’t makes the solution less efficient always.

What if a problem have higher complexity and that is the only known solution for it?
Then it would be the efficient solution for it.

Hope, you are getting what i am trying to explain.

1 Like
#9

Yes sir i got it thanks what is the complexity of your approach??it’s look like same but using while instead of function…

#10

Hey @shampblocks,

The complexity is O(n^2):

Outer loop will iterate n times.

  1. for each iteration while loop will at max iterate for no. of elements in q.
    first iteration: 1
    second iteration: 2
    nth iteration: n
    complexity: 1+2+…+n=n*(n-1)/2=O(n^2)

  2. complexity of building heap is O(no of elements in heap heap)
    first iteration: O(1)
    second: O(2)
    nth iteration: O(n)
    complexity: O(1)+O(2)+…+O(n)=n*(n-1)/2=O(n^2)

So, it is O(n^2).

#11

But bhaiya for building heap it’s not like ki hume input s build krna h we are inserting the elements in heap and insertion is logn and when n is very large as when n/2 starts it will worstlly takes nlogn then for n entries it will be n^2logn basically it is like 1log1 + 2 log2 + 3log3 + … Nlogn upper bound is n^2logn correct me if I m wrong I understood it in this way…

#12

The following link will help:

#13

You are directly building heap downheapification and then popping k elements??

#14

Yes, that would be the most efficient.

#15

Yess i saw it now what I was doing is inserting for each entries so the way I am calculating complexity of my code is correct??

#16

Yes @shampblocks,

It seems correct to me.

#17

Hello @shampblocks,

Please, mark it as resolved.