PROBLEM DESCRIPTION
Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
ArrayList<Integer> countDistinct(int A[], int n, int k) {
ArrayList<Integer> result = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
// Initialize the map with the first window
for (int i = 0; i < k; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
}
// Add the count of distinct elements in the first window
result.add(map.size());
// Slide the window over the array
for (int i = k; i < n; i++) {
// Remove the element going out of the window
int outgoing = A[i - k];
if (map.get(outgoing) == 1) {
map.remove(outgoing);
} else {
map.put(outgoing, map.get(outgoing) - 1);
}
// Add the new element coming into the window
int incoming = A[i];
map.put(incoming, map.getOrDefault(incoming, 0) + 1);
// Add the count of distinct elements in the current window
result.add(map.size());
}
return result;
}
}