Last Updated: 10 Mar, 2021
Good Subarrays
Moderate
Asked in companies
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
Approaches
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.
- 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:
- Finally, return ‘answer’.
We can iterate the ‘ARR’ and use two pointers for our sliding window (‘i’, ‘j’). The back of the window will always be the current position in the ‘ARR’ (‘i’). The front of the window (‘j’) is moved such that 'ARR[j]' appears exactly once in our sliding window. Basically, we are trying to shrink our sliding window and maintain the same number of unique elements at each step.
To do the above-discussed approach, we keep checks on how many times each number appears in our sliding window which is 'slidingWindow'. After adding the next element to the back of our sliding window, we will try to remove as many elements from the front as possible, until the element in the front of the sliding window appears exactly once. While removing the elements, we are increasing our prefix.
If we are able to collect exactly 'K' unique elements, that means we found a total 1 + number of prefix subarray, as each removed element would also form a subarray.
If our sliding window reaches 'K' + 1 unique elements, we remove one number from the front and reset the prefix such that now we are starting a new subarray.
Here is the complete Algorithm:
- Initialize an array/list ‘slidingWindow’of size ‘N’ + 1.
- Make variables ‘answer’ = 0, ‘i’ = 0, ‘j’ = 0, ‘prefix’ = 0, ‘cnt’ = 0.
- Run a for loop from ‘i’ = 0 to ‘i’ < ‘N’ and do the following:
- If the value at index ‘ARR[i]’ in 'slidingWindow' is 0 then increment ‘cnt’ by 1 and 'slidingWindow[ARR[i]]' by 1.
- If ‘cnt’ > ‘K’ then decrease 'slidingWindow[ARR[j]]' by 1 and ‘cnt’ by 1.
- While 'slidingWindow[A[j]]' > 1 do the following :
- Increment the ‘prefix’ by 1.
- Decrement the 'slidingWindow[A[j]' by 1.
- Increment ‘j’ by 1.
- If ‘cnt’ = ‘K’ do the following:
- ‘answer’ = ‘answer’ + ‘prefix’ + 1
- Finally, return the ‘answer’.