Good Subarrays

Moderate
0/80
Average time to solve is 15m
Contributed by

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]
``````
Detailed explanation ( Input/output format, Notes, Images )
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.
``````
Console