Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Good Subarrays

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
alibabaZscaler

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.
Full screen
Console