educative.io

Top 'K' Frequent Numbers - sample code not correct

Courses
,
#1

Hi,

Solution provided to the second problem is not correct, as per question
Input: [5, 12, 11, 3, 11], K = 2
answer should be the following
Output: [11, 5] or [11, 12] or [11, 3]

But when you run the sample following is seen:
Here are the K frequent numbers: 12 11
Here are the K frequent numbers: 12 11

This is happening so because only 2 elements are kept in heap and remaining elements are getting removed. One way to avoid is to see if frequency is same, if it so then push back. But again pairing has to be created from the final list. So the code is incomplete.

#2

@Venkatesan, The order of the numbers in the output doesn’t matter. [12, 11] is a valid output. If the question specifically asks for an order (based on frequency or increasing/decreasing) then we should take care of that. Both [12, 11] or [11, 12] are valid.

Hope this clarifies your question.

#3

Solution works only if the given input is sorted in descending order or for some specific inputs. This is happening because of removing the elements when the heap size is greater than k. Please check the code once.
For Ex: [12,11, 5, 3, 4, 12, 11, 3, 4, 6] gives output as [12,4] which is wrong. Correct output would be [12,11]

#4

If k=2, then I believe 12,4 is as correct as 12,11, since all of these numbers (12,4,11) appear twice in the input list.

#5

That’s right. @Ilya1

#6

Hi @Design_Gurus, No this solution is not correct, ideally it should have printed the most frequent number first. you should use Max Heap to fix this.

Thanks