Good Subarrays

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
7 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 )
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.
Hint

Can we solve this problem using the brute force approach? 

Approaches (2)
Brute Force

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’.
Time Complexity

O(N ^ 2), where N represents the number of elements in ARR.

 

Because there are (N * (N + 1) / 2) subarrays possible and we are processing each subarray exactly once.

Space Complexity

O(N), where N represents the number of elements in ARR.

 

Because the set will contain N elements in the worst case.

Code Solution
(100% EXP penalty)
Good Subarrays
Full screen
Console