by Given an array of size “n” and an integer “k” where k < n. Write a program to return the count of distinct elements in every subarray of size “k”.
For eg:
int arr[] = {1,2,3,4,1,3,4} , window size k = 4
For 1st window of size 4 (index 0-3) – subarray = {1,2,3,4}, distinct element = 4
For 2nd window of size 4 (index 1-4) – subarray = {2,3,4,1}, distinct element = 4
For 3rd window of size 4 (index 2-5) – subarray = {3,4,1,3}, distinct element = 3
For 4th window of size 4 (index 3-6) – subarray = {4,1,3,4}, distinct element = 3
Algorithm
- Create a hash map with element as key and total occurrence as value.
- Define a variable distinct which will count number of distinct elements.
- Iterate through array elements.
- If element is in hash map and occurrence value is 0 then increment distinct value.
- Increment hash value by 1.
- If “k” elements are already visited, then
- If hashmap contains [i-k]th element and value is 1 then decrement distinct by 1.
- If hashmap contains [i-k]th element and value is greater than 0 then decrement hash entry value by 1.
- Publish the distinct variable value along with indexes.
Implementation
Let’s have a look into the sample program to solve the above problem.
/*
* Given an array of size n and an integer k,
* return the count of distinct numbers in all windows of size k.
*/
#include "iostream"
#include <unordered_map>
using namespace std;
#define ARRAY_MAX_VALUE 200
void count_distinct_number (int* arr, int size, int k)
{
unordered_map <int, int> hash_map;
int distinct = 0;
for (int i = 0; i < size; i++) {
if (hash_map[arr[i]] == 0)
distinct++;
hash_map[arr[i]] = hash_map[arr[i]] + 1;
if (i >= k-1) {
if (hash_map[arr[i-k]] == 1)
distinct--;
if (hash_map[arr[i-k]] > 0)
hash_map[arr[i-k]]--;
cout << "K indexes: " << i-k+1 << " and " << i << " distinct entries: " << distinct << endl;
}
}
}
int main ()
{
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = rand () % 10;
}
for (int i = 0; i < 10; i++) {
cout << arr[i] << " ";
}
cout << endl;
count_distinct_number (arr, 10, 4);
count_distinct_number (arr, 10, 6);
}
Let’s have a look into the output o above program.
3 6 7 5 3 5 6 2 9 1
K indexes: 0 and 3 distinct entries: 4
K indexes: 1 and 4 distinct entries: 4
K indexes: 2 and 5 distinct entries: 3
K indexes: 3 and 6 distinct entries: 3
K indexes: 4 and 7 distinct entries: 4
K indexes: 5 and 8 distinct entries: 4
K indexes: 6 and 9 distinct entries: 4
K indexes: 0 and 5 distinct entries: 4
K indexes: 1 and 6 distinct entries: 4
K indexes: 2 and 7 distinct entries: 5
K indexes: 3 and 8 distinct entries: 5
K indexes: 4 and 9 distinct entries: 6
