Good Subarrays

Posted: 10 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

The idea behind this approach is to generate every possible subarray and then for each subarray count the number of distinct elements. If the count of distinct elements is equal to ‘K’ then include that subarray in our answer.

 

Here is the complete algorithm:

  • Make a variable ‘answer’ which represents the number of good subarrays.
  • We run a loop from ‘i’ = 0 to ‘i’ < ‘N’ where ‘i’ denotes the starting index of the subarray and for each ‘i’ do the following:
    • We run a loop from ‘j’ = ‘i’ to ‘j’ < ‘N’ where ‘j’ represents the last index of the subarray from ‘i’ to ‘j’ and do the following:
      • Insert each element in the set.
      • If the size of the set is ‘K’ then increment ‘answer’.
    • Clear the set for next iteration.
  • Finally, return ‘answer’.
Try Problem