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

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    
    // Function to count distinct elements in every window of size k
    public static int[] countDistinctInWindows(int[] arr, int k) {
        int n = arr.length;

        // Initialize the answer array
        int numberOfSubarrays = n - k + 1;
        int[] ans = new int[numberOfSubarrays];

        // Create a frequency map for the first window
        HashMap<Integer, Integer> fmap = new HashMap<>();
        for (int i = 0; i < k; i++) {
            int ele = arr[i];
            if (fmap.containsKey(ele)) {
                // If element is present in map, increase the old frequency
                int oldFreq = fmap.get(ele);
                fmap.put(ele, oldFreq + 1);
            } else {
                // Element is not available, add the element with frequency 1
                fmap.put(ele, 1);
            }
        }

        int index = 0;
        int s = 1;
        int e = k;
        while (e < n) {

            // Store the count of distinct elements in the current window
            ans[index] = fmap.size();
            index++;

            // Remove impact of A[s-1] from fmap
            if (fmap.containsKey(arr[s - 1])) {
                // If key is present in frequency map
                int count = fmap.get(arr[s - 1]); // Retrieve the current count
                if (count > 1) {
                    // Decrement the count
                    fmap.put(arr[s - 1], count - 1);
                } else {
                    // If the count is 1, remove the entry from the frequency map
                    fmap.remove(arr[s - 1]);
                }
            }

            // Add impact of A[e] in fmap
            if (fmap.containsKey(arr[e])) {
                // If the key is already present, increment the count
                fmap.put(arr[e], fmap.get(arr[e]) + 1);
            } else {
                // If the key is not present, add it to the frequency map with a count of 1
                fmap.put(arr[e], 1);
            }

            // Slide the window by 1 index
            s++;
            e++;
            
        }

        // Manage the last window
        ans[index] = fmap.size();
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 8, 3, 9, 4, 9};
        int k = 4;

        int[] result = countDistinctInWindows(arr, k);

        System.out.println("Count of distinct elements in windows: " + Arrays.toString(result));
    }
}