# Count Distinct Element in Every K Size Window

#### You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.

##### Note:

```
1. The size of ‘ARR’ will always be greater than or equal to the ‘K’.
2. Here window refers to a subarray of ‘ARR’. Hence ‘K’ sized window means a subarray of size ‘K’.
3. You are not required to print the output explicitly. It has already been taken care of. Just implement the function and return an array of the count of all distinct elements in the ‘K’ size window.
```

#### Example

```
Consider ARR = [ 1, 2, 1, 3, 4, 2, 3 ] and K = 3.
```

```
As per the given input, we have a sequence of numbers of length 7, and we need to find the number of distinct elements present in all the windows of size 3.
Window-1 has three elements { 1, 2, 1 } and only two elements { 1, 2 } are distinct because 1 is repeating two times.
Window-2 has three elements { 2, 1, 3 } and all three elements are distinct { 2, 1, 3 }.
Window-3 has three elements { 1, 3, 4 } and all three elements are distinct { 1, 3, 4 }.
Window-4 has three elements { 3, 4, 2 } and all three elements are distinct { 3, 4, 2 }.
Window-5 has three elements { 4, 2, 3 } and all three elements are distinct { 4, 2, 3 }.
Hence, the count of distinct elements in all K sized windows is { 2, 3, 3, 3, 3 }.
```

##### Input format:

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and ‘K’, denoting the number of elements in the array and the size of the window.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
```

##### Output Format:

```
For each test case, print an array that contains the number of distinct elements in all ‘K’ size windows, and the count of distinct elements must be from the left to the right window.
Print the output of each test case in a separate line.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= K <= N
1 <=ARR[i] <= 10 ^ 9
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, ‘K’ denotes the size of the window, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'.
Time limit: 1 second
```

The basic idea of this approach is to check every window of size K and count the number of distinct elements in each window.

Our approach will be to maintain an array **answer**, which will store the count of the distinct elements in every window. We will traverse through each window and find the number of distinct elements in the current window.

- For each element in the window, we will traverse through the window elements and check if the current number has already been included in the number of distinct elements of the current window.
- In the end, insert the number of distinct elements in the current window in the array
**answer**.

We will return the array **answer**.

**Algorithm:**

- Create an array
**answer**, which will store the number of distinct elements in all windows. - Iterate
**windowNumber**from 0 to**N - K**.- Set the variable
**count**as 0, which will store the number of distinct elements in the current window. - Iterate
**index**from**windowNumber**to**windowNumber + K - 1**.- Set the variable
**distinctElement**as**true**. The variable**distinctElement**will store if the current element is distinct in the current window or not. - Iterate
**pos**from**windowNumber**to**index - 1**.- Check if
**ARR[index]**is equal to**ARR[pos]**, then assign**distinctElement**as**false**and terminate the loop.

- Check if
- Check if
**distinctElement**is**true**.- Increment
**count**by 1.

- Increment

- Set the variable
- Insert
**count**in the array**answer**.

- Set the variable
- Return the array
**answer**.

The basic idea of this approach is to store every distinct element present in the window in the HashMap, and we will find the number of distinct elements in the window with the help of HashMap.

Our approach will be to maintain an array **answer**, which will store the count of the distinct elements in every window. We will traverse through each window and find the number of distinct elements in the current window.

- We will check if the current number is not present in the HashMap for each element in the window, then we will insert the current number in the HashMap.
- In the end, we will insert the number of distinct elements present in the HashMap in the array
**answer**.

We will return the array **answer**.

**Algorithm:**

- Create an array
**answer**, which will store the number of distinct elements in all windows. - Iterate
**windowNumber**from**0**to**N - K**.- Maintain a HashMap to store distinct elements in the current window.
- Iterate
**index**from**windowNumber**to**windowNumber + K - 1**.- Check if
**ARR[index]**is not present in the HashMap.- Insert
**ARR[index]**in the HashMap.

- Insert

- Check if
- Insert the number of elements present in the HashMap in the array
**answer**.

- Return the array
**answer**.

The basic idea of this approach is to maintain a window and then slide the window by one element at each step. We will achieve this by using a HashMap to maintain the frequency of elements present in the window. While we are sliding the window, we add an element in the window and remove an element from the window.

Our approach will be to maintain an array **answer**, which will store the count of the distinct and a HashMap to store the frequency of elements in the current window.

- Iterate
**index**from**0**to**K - 1**and update the; frequency of**ARR[index]**in the HashMap. So, we will increment the frequency of**ARR[index]**in the HashMap by 1. Insert the number of elements present in the current window in the array**answer**with the help of the HashMap. - Iterate
**index**from**K**to**N - 1**. In each iteration, we are deleting the**ARR[index - K]**from the window. We will decrement the frequency of**ARR[index - K]**in the HashMap by 1. We are inserting**ARR[index]**in the window, and we will increment the frequency of**ARR[index]**by 1. In the end, we will insert the number of the distinct elements present in the HashMap in the array**answer**.

We will return the array **answer**.

**Algorithm:**

- Create an array
**answer**, which will store the number of distinct elements in all windows. - Maintain a HashMap to store the frequency of elements in the current window.
- Iterate
**index**from**0**to**K - 1**.- Increment the frequency of
**ARR[index]**in the HashMap by 1.

- Increment the frequency of
- Insert the number of elements present in the HashMap in the array
**answer**. - Iterate
**index**from**K**to**N - 1**.- Decrement the frequency of
**ARR[index - K]**in the HashMap by 1. - Check if the frequency of
**ARR[index - K]**in the HashMap is 0.- Delete
**ARR[index - K]**from the HashMap.

- Delete
- Increment the frequency of
**ARR[index]**in the HashMap by 1. - Insert the number of elements present in the HashMap in the array
**answer**.

- Decrement the frequency of
- Return the array
**answer**.