Most Votes :
Difficulty Level : Medium
Submissions : 175
Asked In :
Marks :15
: 2 | : 0
An online streaming application wishes to analyze the popularity of the web series streaming on their application. Every web series is given a unique ID. The users have voted for their one of the most favorite web series.
To analyze the popularity of the web series, the marketing team has picked $$$N$$$ users (with ID $$$0$$$ to $$$N-1$$$) of the application and recorded the ID of the web series voted by the users. The marketing team analyze the web series in batches of size $$$K$$$. The first batch consists of web series voted by users with IDs $$$0$$$ to $$$K-1$$$. For the next batch, the web series of the first user with ID $$$0$$$ is removed from the left side and the web series of the next user with ID is added from the right side and so on for further batches until the $$$N^{th}$$$ user (with ID $$$N-1$$$).
For every batch, the maximum number of votes for a web series needs to be recorded. The marketing team manager wants to add this feature in their system to save the team's time. Write an algorithm to find the maximum number of votes for a web series for every batch.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases.
The first line of each testcase contains two space separated integers $$$N$$$ and $$$K$$$ $$$(1 \le K \le N \le 10^{5})$$$ — the number of users and the number of users included in a batch for analysis.
The second line consists of N space-separated integers - $$$wsID[0], wsID[1]......., wsID[N-1]$$$ $$$(1 \le wsID[i] \le 10^9)$$$ — representing the ID of the web series voted by the users.
It is guaranteed that the individual sums of $$$n$$$ and $$$k$$$ over all testcases do not exceed $$$10^5$$$.
For each test case, print space-separated integers representing the maximum number of votes for a web series for every batch in a single line.
16 320 10 20 16 40 40
2 1 1 2
In the sample test case,
- In the first batch, the web series with ID 20 is voted by a maximum of 2 users.
- In the second batch, every web series is voted by 1 user only.
- In the third batch, every web series is voted by 1 user only.
- In the fourth batch, the web series with ID 40 is voted by a maximum of 2 users.
