Problem title
Difficulty
Avg time to solve

Uncommon Characters
Moderate
25 mins
Boxes Of Chocolates
Moderate
20 mins
Pythagorean Triplets
Moderate
35 mins
Gold mine problem
Moderate
35 mins
Common Elements
Moderate
35 mins
BST to greater tree
Moderate
25 mins
Largest subarray with equal number of 0s and 1s
Moderate
10 mins
Largest Island
Moderate
15 mins
Subarray With Given Sum
Moderate
15 mins
Shopping Spree
Hard
50 mins
2

Count Distinct Elements In Every Window

Difficulty: MEDIUM
Contributed By
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

Given an array of integers ‘arr’ of size ‘n’ and an integer ‘k’. You need to find the count of distinct elements in every sub-array of size ‘k’ in the given array. Return an integer array ‘count’ that consists of n - k + 1 integers where ‘count[i]’ is equal to the number of distinct elements in a sub-array of size ‘k’ starting from index ‘i’.

Note:
1. The sub-array of an array is a continuous part of the array.
2. Consider ‘0’ based indexing.
3. ‘k’ will always be less than or equal to ‘n’.
3. Don’t print anything, just return the integer array ‘count’.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘k’  respectively representing the size of array ‘arr’ and size of sub-array to be considered.

The second line of the test case contains ‘n’ space-separated integers representing elements of the array ‘arr’.
Output format :
For each test case, return an integer array ‘count’ that consists of n - k + 1 integers where ‘count[i]’ is equal to the number of distinct elements in a sub-array of size ‘k’ starting from index ‘i’ in array ‘arr’.

Output for each query must be printed in a new line.
Constraints:
1 <= T <= 50
1 <= n <= 10^4
1 <= k <= n
-10^9 <= arr[i] <= 10^9

Where ‘T’ is the total number of test cases, ‘n’ is the given positive integer, ‘k’ is the size of sub-array to be considered, and arr[i] is the value of the array elements.


Time limit: 1 sec
Sample Input 1:
2
4 3
2 2 1 3
1 1
5
Sample Output 1:
2 3 
1
Explanation of Sample Input 1:
Test case 1:
Here, ‘n’ = 4, ‘k’ = 3 and ‘arr’ = {2, 2, 1, 3};
The sub-array of size 3 starting from index 0 is {2, 2, 1} and there are 2 distinct elements i.e  2 and 1 in it.
The sub-array of size 3 starting from index 1 is {2, 1, 3} and there are 3 distinct elements i.e 2, 1, and 3 in it.
So, the ‘count’ array will be {2, 3}.     

Test case 2:
Here, ‘n’ = 1, ‘k’ = 1 and ‘arr’ = {1};
The sub-array of size 1 starting from index 0 is {5} and there is 1 distinct element i.e 5 in it.
So, the ‘count’ array will be {1}.
Sample Input 2:
 2
 3 3
 1 1 1
 3 1
 1 2 2
Sample Output 2:
 1
 1 1 1 
Explanation of Sample Input 2:
Test case 1:
Here, ‘n’ = 3, ‘k’ = 3 and ‘arr’ = {1, 1, 1};
The sub-array of size 3 starting from index 0 is {1, 1, 1} and there is 1 distinct element i.e 1 in it.

Test case 2:
Here, ‘n’ = 3, k = ‘1’ and ‘arr’ = {1, 2, 2};
The sub-array of size 1 starting from index 0 is {1} and there is 1 distinct element i.e 1 in it.
The sub-array of size 1 starting from index 1 is {2} and there is 1 distinct element i.e 2 in it.
The sub-array of size 1 starting from index 2 is {2} and there is 1 distinct element i.e 2 in it.
So, the ‘count’ array will be {1, 1, 1}.
Reset Code
Full screen
copy-code
Console