Can not understand what the problem is. can you clarify it a little?

#1

Question:

Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (according to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency. If frequency of two numbers are same then print them in increasing order.

Input Format
First line contains integer t as number of test cases. Each test case contains following input. First line contains integer n and k, n represents the length of the array and next line contains n space separated integers.

Constraints
1 < t < 100 1< n < 100000

Output Format
Print top k running stream.

Sample Input
1
5 2
5 1 3 5 2
Sample Output
5 1 5 1 3 5 1 5 1

#2

Hey @tasfikrahman007

We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency.
i can explain you better with examples :-
Input : arr[] = {5, 2, 1, 3, 2}
k = 4
Output : 5 2 5 1 2 5 1 2 3 5 2 1 3 5
Explanation:

  1. After reading 5, there is only one element 5 whose frequency is max till now.
    so print 5.
  2. After reading 2, we will have two elements 2 and 5 with the same frequency.
    As 2, is smaller than 5 but their frequency is the same so we will print 2 5.
  3. After reading 1, we will have 3 elements 1, 2 and 5 with the same frequency,
    so print 1 2 5.
  4. Similarly after reading 3, print 1 2 3 5
  5. After reading last element 2 since 2 has already occurred so we have now a
    frequency of 2 as 2. So we keep 2 at the top and then rest of the element
    with the same frequency in sorted order. So print, 2 1 3 5.

Input : arr[] = {5, 2, 1, 3, 4}
k = 4
Output : 5 2 5 1 2 5 1 2 3 5 1 2 3 4
Explanation:

  1. After reading 5, there is only one element 5 whose frequency is max till now.
    so print 5.
  2. After reading 2, we will have two elements 2 and 5 with the same frequency.
    As 2, is smaller than 5 but their frequency is the same so we will print 2 5.
  3. After reading 1, we will have 3 elements 1, 2 and 5 with the same frequency,
    so print 1 2 5.
    Similarly after reading 3, print 1 2 3 5
  4. After reading last element 4, All the elements have same frequency
    So print, 1 2 3 4.
#3

If this resolves your query then please mark it as resolved :slight_smile:.

#4

I solved this using hashmap. as it is in the heap chapter is there any efficient way to sove it using heaps?

#5

Hey @tasfikrahman007
Best solution using Priority Queue


But the one with hashmap is more efficient then this one.
If this resolves your query then please mark it as resolved :slight_smile:.

#6

yes I also thought so, implementing heap would make it slower

1 Like