Count distinct elements in every window of size k - GeeksforGeeks
Given an array of size n and an integer k, return the of count of distinct numbers in all windows of size k.
An Efficient Solution is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements of current widow. When we slide the window, we remove an element from hash and add an element. We also keep track of distinct elements.
A Simple Solution is to traverse the given array, consider every window in it and count distinct elements in the window.
Time complexity of the above solution is O(nk2). We can improve time complexity to O(nkLok) by modifying countWindowDistinct() to use sorting. The function can further be optimized to use hashing to find distinct elements in a window. With hashing the time complexity becomes O(nk). Below is a different approach that works in O(n) time.
Read full article from Count distinct elements in every window of size k - GeeksforGeeks
Given an array of size n and an integer k, return the of count of distinct numbers in all windows of size k.
An Efficient Solution is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements of current widow. When we slide the window, we remove an element from hash and add an element. We also keep track of distinct elements.
static void countDistinct(int arr[], int k) { // Creates an empty hashMap hM HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); // initialize distinct element count for // current window int dist_count = 0; // Traverse the first window and store count // of every element in hash map for (int i = 0; i < k; i++) { if (hM.get(arr[i]) == null) { hM.put(arr[i], 1); dist_count++; } else { int count = hM.get(arr[i]); hM.put(arr[i], count+1); } } // Print count of first window System.out.println(dist_count); // Traverse through the remaining array for (int i = k; i < arr.length; i++) { // Remove first element of previous window // If there was only one occurrence, then // reduce distinct count. if (hM.get(arr[i-k]) == 1) { hM.remove(arr[i-k]); dist_count--; } else // reduce count of the removed element { int count = hM.get(arr[i-k]); hM.put(arr[i-k], count-1); } // Add new element of current window // If this element appears first time, // increment distinct element count if (hM.get(arr[i]) == null) { hM.put(arr[i], 1); dist_count++; } else // Increment distinct element count { int count = hM.get(arr[i]); hM.put(arr[i], count+1); } // Print count of current window System.out.println(dist_count); } }A Simple Solution is to traverse the given array, consider every window in it and count distinct elements in the window.
Time complexity of the above solution is O(nk2). We can improve time complexity to O(nkLok) by modifying countWindowDistinct() to use sorting. The function can further be optimized to use hashing to find distinct elements in a window. With hashing the time complexity becomes O(nk). Below is a different approach that works in O(n) time.
// Counts distinct elements in window of size kint countWindowDistinct(int win[], int k){ int dist_count = 0; // Traverse the for (int i=0; i<k; i++) { // Check if element arr[i] exists in arr[0..i-1] int j; for (j=0; j<i; j++) if (win[i] == win[j]) break; if (j==i) dist_count++; } return dist_count;}// Counts distinct elements in all windows of size kvoid countDistinct(int arr[], int n, int k){ // Traverse through every window for (int i=0; i<=n-k; i++) cout << countWindowDistinct(arr+i, k) << endl;}Read full article from Count distinct elements in every window of size k - GeeksforGeeks
