# Find the count of distinct elements in every subarray of size k

Posted in  Vinay Khatri
Last updated on December 7, 2023

## Problem

Given an array of integers and a number ``` k ``` . Find the count of distinct elements in every subarray of size ``` k ``` in the array.

#### Sample Input

```N = 3  k = 2
[4, 1, 1]```

#### Sample Output

`2 1`

#### Explanation

[4,1] is the first subarray and [1,1] is second

### Approach

We can use Hashmap to solve this problem. Initially, we can keep the count of each element in the first subarray in the hashmap. The size of the hashmap will be the number of distinct elements in the first subarray. Now, we slide the window by 1 and decrement the frequency of the starting element of the current window and increment the frequency of the next candidate element of the window.

Also, if we are decrementing the starting element’s frequency in the current window and it becomes 0, we can remove this element from the map. This way, we will always keep a unique number of elements in the hashmap.

#### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
void countDistinct (int arr[], int n, int k)
{
unordered_map<int,int>mp;
for(int i=0;i<k;i++) mp[arr[i]]++;
int i = 0, j=k;
while(j<=n){
cout<<mp.size()<<" ";
mp[arr[i]]--;
if(!mp[arr[i]])
mp.erase(arr[i]);    //remove element if frequency becomes 0
mp[arr[j]]++;
j++,i++;         // move to next window

}
}

int main(){
int arr = {4, 1, 1};

int n =  sizeof(arr)/sizeof(arr);
int k =2;
countDistinct(arr, n, k);
}```

Output

`2 1`

We can also use a variable instead of hashmap size in the above algorithm. Below is an implementation of this.

#### Python Programming

```from collections import defaultdict

def countDistinctElements(arr, k, n):

mp = defaultdict(lambda:0)
ans = 0
for i in range(k):
if mp[arr[i]] == 0:
ans += 1
mp[arr[i]] += 1
print(ans)

for i in range(k, n):
if mp[arr[i - k]] == 1:
ans -= 1
mp[arr[i - k]] -= 1

if mp[arr[i]] == 0:
ans += 1
mp[arr[i]] += 1

print(ans)

arr = [4, 1, 1]
n = len(arr)
k = 2
countDistinctElements(arr, k, n)```

Output

```2
1```

#### C# Programming

```using System;
using System.Collections.Generic;

public class Solution {
static void countDistinct(int[] arr, int k)
{
Dictionary<int, int> mp = new Dictionary<int, int>();

int ans = 0;

for (int i = 0; i < k; i++) {
if (!mp.ContainsKey(arr[i])) {
ans++;
}
else {
int count = mp[arr[i]];
mp.Remove(arr[i]);
}
}
Console.WriteLine(ans);

for (int i = k; i < arr.Length; i++) {

if (mp[arr[i - k]] == 1) {
mp.Remove(arr[i - k]);
ans--;
}
else
{
int count = mp[arr[i - k]];
mp.Remove(arr[i - k]);
mp.Add(arr[i - k], count - 1);
}
if (!mp.ContainsKey(arr[i])) {
ans++;
}
else
{
int count = mp[arr[i]];
mp.Remove(arr[i]);
}

Console.WriteLine(ans);
}
}

public static void Main(String[] arg)
{
int[] arr = {4, 1, 1};
int k = 2;
countDistinct(arr, k);
}
}```

Output

```2
1```