# Distinct Numbers in Window

You are given an array of N integers, A1, A2 ,…, AN and an integer K. Return the of count of distinct numbers in all windows of size K.

Formally, return an array of size N-K+1 where i’th element in this array contains number of distinct elements in sequence Ai, Ai+1 ,…, Ai+k-1.

Note:

``` If K > N, return empty array.
A[i] is a signed integer
```
For example,

```A=[1, 2, 1, 3, 4, 3] and K = 3

All windows of size K are

[1, 2, 1]
[2, 1, 3]
[1, 3, 4]
[3, 4, 3]

So, we return an array [2, 3, 3, 2].```
Solution:

Time: O(n)
Space: O(k)

public class Solution {
public ArrayList<Integer> dNums(ArrayList<Integer> A, int B) {
Map<Integer, Integer> map = new HashMap<>();
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < A.size(); i ++) {
int val = A.get(i);
int freq = map.getOrDefault(val, 0);
map.put(val, freq + 1);
if (i >= B) {
int oldVal = A.get(i - B);
map.put(oldVal, map.get(oldVal) - 1);
if (map.get(oldVal) == 0) {
map.remove(oldVal);
}
}
// System.out.println(map);
if (i >= B - 1) result.add(map.size());
}
return result;
}
}