Posts Count distinct elements in every window (geeksforgeeks - SDE Sheet)
Post
Cancel

Count distinct elements in every window (geeksforgeeks - SDE Sheet)

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.

geeksforgeeks

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;
    }
}

This post is licensed under CC BY 4.0 by the author.