Count Distinct Elements in Every Window of Size K.
Given an array of n integers and an integer k (k is always smaller or equal to n). Return the count of distinct elements in all windows (or in all sub-arrays) of size k.
For example –
Example 1:
Input: {1, 5, 9, 3, 3, 7, 3}, k = 3
Output: {3, 3, 2, 2, 2}
1st window {1, 5, 9}, Distinct elements are 3.
2nd window {5, 9, 3}, Distinct elements are 3.
3rd window {9, 3, 3}, Distinct elements are 2.
4th window {3, 3, 7}, Distinct elements are 2.
5th window {3, 7, 3}, Distinct elements are 2.
Example 2:
Input: {1, 4, 7, 7}, k = 2
Output: {2, 2, 1}
1st window {1, 4}, Distinct elements are 2.
2nd window {4, 7}, Distinct elements are 2.
3rd window {7, 7}, Distinct elements are 1.
In this problem, we have to find the distinct elements count in all the sub-arrays of size k. The size of output array is always n-k+1 (where n is the length of array, k is the size of window).
This problem can be efficiently solved through sliding window approach. I have also added video tutorial at the end of this post.
Count Distinct Elements in Every Window of Size K – Java Code
An efficient approach to solve this problem is to form a window of size k. After that put all the elements and it’s count of this window in a HashMap. The keys are always unique in a HashMap. So, the number of distinct elements present in this window is the size of a HashMap.
We have computed the result of one window. After that run a loop from 1 to n-k and do the following operations.
i) Remove previous element from a HashMap.
ii) Add new element in a HashMap. The count of distinct elements in this window is the size of HashMap.
The time and space complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
//Find distinct numbers in a window public class DistinctElement { public static List<Integer> distinctElements(int[] arr, int k) { List<Integer> result = new ArrayList<>(); //Declared HashMap Map<Integer, Integer> elemCountMap = new HashMap<>(); int len = arr.length; /* * Create a first window and * put all the element and it's count * of this window in a HashMap. */ for(int j = 0; j < k; j++) { elemCountMap.put(arr[j], elemCountMap.getOrDefault(arr[j], 0)+1); } result.add(elemCountMap.size()); for(int j = 1; j <= len-k; j++) { int removeElem = arr[j-1]; int addElem = arr[j+k-1]; //Remove element from map removeElemFromMap(elemCountMap, removeElem); //Add element from map elemCountMap.put(addElem, elemCountMap.getOrDefault(addElem, 0)+1); result.add(elemCountMap.size()); } return result; } private static void removeElemFromMap(Map<Integer, Integer> elemCountMap, int elem) { Integer count = elemCountMap.get(elem); if(count != null && count > 1) { elemCountMap.put(elem, count-1); } else { elemCountMap.remove(elem); } } public static void main(String[] args) { int[] arr = {1, 5, 9, 3, 3, 7, 3}; int k = 3; List<Integer> result = distinctElements(arr, k); result.forEach(elem -> { System.out.println(elem); }); } } |
