2

Good Subarrays

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

Problem Statement

You have been given an array/list ‘ARR’ consists of positive integers. We call a contiguous subarray of ‘ARR’ good if the number of different integers in that subarray is exactly ‘K’. Your task is to find out the number of good subarrays of ‘ARR’.

For example:

‘ARR[]’ = [1, 3, 1, 1, 2] has 3 different integers: 1, 2, and 3. And for ‘K’ = 2, following are the good subarrays.
1. [1, 3]
2. [1, 3, 1]
3. [1, 3, 1, 1]
4. [3, 1]
5. [3, 1, 1]
6. [1, 1, 2]
7. [1, 2]
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then each test case follows.

The first line of each test case contains a single integer ‘N’ and ‘K’ denoting the number of elements in the ‘ARR’ and ‘K’ respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements in the ‘ARR’.
Output Format :
For each test case, print a single line containing a single integer denoting the number of good subarrays in ‘ARR’

The output for each test case will be printed in a new line. 
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 1000
1 <= K <= 1000
1 <= ARR[i] <= 10 ^ 5

‘T’ is the number of Test Cases
‘N’ is the number of elements in the ‘ARR’
‘ARR[i]’ is the element at the ‘i’th’ index in the ‘ARR’

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 1 2 4 
1 2
1
Sample Output 1:
3
0

Explanation for Sample Output 1:

For the first test case :
Following are the good subarrays for the ‘ARR’ = [1,1,2,4] and ‘K’ = 2:
1. [1, 1, 2]
2. [1, 2]
3. [2, 4]
These are the 3 good subarrays so we return 3.

For the second test case :
There is only one element in ‘ARR’ and ‘K’ = 2 so we can’t not have 2 distinct elements. So we return 0.
Sample Input 2 :
2
6 1
1 2 3 4 5 6
3 3
3 2 1
Sample Output 2 :
6
1

Explanation for Sample output 2:

For the first test case :
Following are the Good SubArrays for the ‘ARR[]’ = [1,2,3,4,5,6] and ‘K’ = 1:
1. [1]
2. [2]
3. [3]
4. [4]
5. [5]
6. [6]
These are the 6 good subarrays so we return 6.

For the second test case :
There is only one subarray [3, 2, 1] for ‘K’ = 3 so we return 1.
Reset Code
Full screen
copy-code
Console