Last Updated: 22 Nov, 2020
Subarray with distinct integers
Easy
Asked in companies
You are given an array/list 'ARR' consisting of 'N' integers and an integer 'B'. A non-empty subarray of 'ARR' is good if it contains exactly 'B' distinct integers.
Your task is to return the number of good subarrays in the given array/list.
Example:
For 'ARR' = [1, 2, 1, 3, 2, 4] and 'B' = 3, one of the good subarrays which contains three distinct integers is [1, 2, 1, 3].
Note:
An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end from array 'D'.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains two single space-separated integers ‘N’ and ‘B’ denoting the number of integers in the array/list and the given integer.
The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array.
Output Format :
For each test case, print an integer denoting the number of good subarrays in the given array/list.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
1 <= B <= N
1 <= ARR[i] <= 10^9
Time Limit: 1sec
Approaches
We will iterate through all possible subarrays of the array with the help of two nested loops. We will maintain a Set data structure for the count of distinct integers in a subarray.
The algorithm will be-
- We will run a loop for the starting index of the subarray.
- From every starting index, we will run a loop for the ending index of the subarray.
- We will maintain a set ‘DISTINCT_COUNT’ for the number of distinct integers in the current subarray.
- Let the current ending index be ‘CURR_INDEX’. Then for each iteration, we will-
- Insert ‘ARR[CURR_INDEX]’ to ‘DISTINCT_COUNT’.
- If the size of ‘DISTINCT_COUNT’ is exactly ‘B’, we will increment our ‘COUNT’ by 1.
- We finally return ‘COUNT’.
We can use the method of two pointers with the sliding window technique to find the number of good subarrays with atmost ‘B’ distinct elements. Then we can subtract with it the number of good subarrays with atmost ‘B’ - 1 distinct elements to find our final answer.
The current window will be our current processing subarray-
- If the count of the distinct elements in this window is less than ‘B’, then we will expand our window until the count of distinct elements is less than equal to 'B'.
- Similarly, if the count of distinct integers in this window is equal to 'B', we shrink our window.
The algorithm will be-
- Take two pointers ‘START’ and ‘END’ with an initial value of ‘START’ equal to 0, and ‘END’ equal to 0.
- We can use a hashmap for finding the count of distinct integers.
- Now, while ‘START’ < ‘N’:
- We will keep incrementing ‘END' until the count of distinct integers is less than equal to ‘B’.
- Add ‘END’ - ‘START’ to the ‘COUNT’.
- Remove ‘ARR[START]’ from the hashmap.
- Increment ‘START’ by 1.
- We finally return our ‘ANSWER’.
Similar problems