Last Updated: 14 Dec, 2020
Count Distinct Elements In Every Window
Moderate
Asked in companies
Given an array of integers ‘arr’ of size ‘n’ and an integer ‘k’. You need to find the count of distinct elements in every sub-array of size ‘k’ in the given array. Return an integer array ‘count’ that consists of n - k + 1 integers where ‘count[i]’ is equal to the number of distinct elements in a sub-array of size ‘k’ starting from index ‘i’.
Note:
1. The sub-array of an array is a continuous part of the array.
2. Consider ‘0’ based indexing.
3. ‘k’ will always be less than or equal to ‘n’.
3. Don’t print anything, just return the integer array ‘count’.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains two space-separated integers ‘n’ and ‘k’ respectively representing the size of array ‘arr’ and size of sub-array to be considered.
The second line of the test case contains ‘n’ space-separated integers representing elements of the array ‘arr’.
Output format :
For each test case, return an integer array ‘count’ that consists of n - k + 1 integers where ‘count[i]’ is equal to the number of distinct elements in a sub-array of size ‘k’ starting from index ‘i’ in array ‘arr’.
Output for each query must be printed in a new line.
Constraints:
1 <= T <= 50
1 <= n <= 10^4
1 <= k <= n
-10^9 <= arr[i] <= 10^9
Where ‘T’ is the total number of test cases, ‘n’ is the given positive integer, ‘k’ is the size of sub-array to be considered, and arr[i] is the value of the array elements.
Time limit: 1 sec
Approaches
- Make an integer array ‘count’ of size n-k+1.
- Run a loop where ‘i’ ranges from 0 to n-k and for each ‘i’ count number of distinct elements in sub-array starting from this index, this can be done as follow.
- Initialize an integer variable ‘distinct’:= 0.
- Run a loop where ‘j’ ranges from ‘i’ to ‘i + k -1’ and for each ‘j’ check whether there exist any element in the range [i, j-1] which is equal ‘arr[j]’. If no such element found increment ‘distinct’ by 1.
- Assing count[i] := distinct.
- Return this integer array ‘count’.
This problem can be solved by maintaining a sliding window of size ‘k’ and using Hash Map to count distinct element in the window as follow -:
- Make an integer array ‘count’ of size n-k+1.
- Initialize two integer variables‘ start’:= 0 and ‘end’:= 0, representing the start and end of the window.
- Make a Hash Map that will contain unique elements in the current window mapped with their frequency in that window. The size of HashMap will give the count of a distinct element in the current window.
- Run a while loop till ‘end’ is smaller than ‘n’ and do the following in each iteration -:
- Insert the key ‘arr[end]’ in HashMap if it does not exist, and increment its value by 1.
- If ‘end’ is smaller than ‘k-1’ then continue.
- Otherwise, assign the size of HashMap to ‘count[start]’ and then decrement the value of key ‘arr[start]’ in hashMap by 1. If its value becomes 0 remove this key from HashMap. After that increment ‘start’ by 1.
- Increment ‘end’ by 1.
- Return the integer array ‘count’.