Count Distinct Elements in Every Window of Size k in Java

This Java program counts the number of distinct elements in every sliding window of size k in a given array. It utilizes a hash map (or dictionary) to track the frequency of each element in the current window, allowing for efficient updates as the window slides.

Program Structure

import java.util.HashMap;

public class DistinctCountInWindow {
    
    /**
     * Function to count distinct elements in every window of size k
     * 
     * @param arr the input array of integers
     * @param k the size of the sliding window
     */
    public static void countDistinct(int[] arr, int k) {
        // Create a hash map to store the frequency of elements
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Initialize the count of distinct elements
        int distinctCount = 0;
        
        // Process the first k elements to set up the initial window
        for (int i = 0; i < k; i++) {
            if (frequencyMap.get(arr[i]) == null) {
                // Element is seen for the first time
                frequencyMap.put(arr[i], 1);
                distinctCount++;
            } else {
                // Element exists, increment its frequency
                frequencyMap.put(arr[i], frequencyMap.get(arr[i]) + 1);
            }
        }
        
        // Print the count of distinct elements for the first window
        System.out.println("Distinct count in window 1: " + distinctCount);
        
        // Slide the window from start to end of the array
        for (int i = k; i < arr.length; i++) {
            // Remove the element going out of the window
            int outgoingElement = arr[i - k];
            frequencyMap.put(outgoingElement, frequencyMap.get(outgoingElement) - 1);
            if (frequencyMap.get(outgoingElement) == 0) {
                frequencyMap.remove(outgoingElement);
                distinctCount--;
            }
            
            // Add the new element coming into the window
            int incomingElement = arr[i];
            if (frequencyMap.get(incomingElement) == null) {
                frequencyMap.put(incomingElement, 1);
                distinctCount++;
            } else {
                frequencyMap.put(incomingElement, frequencyMap.get(incomingElement) + 1);
            }
            
            // Print the count of distinct elements for the current window
            System.out.println("Distinct count in window " + (i - k + 2) + ": " + distinctCount);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 4, 2, 3};
        int k = 3;
        countDistinct(arr, k);
    }
}

How the Program Works

• The program defines a method countDistinct that takes an integer array arr and an integer k.
• It initializes a HashMap to keep track of the frequency of elements in the current window.
• The first k elements are processed to build the initial window and calculate the distinct count.
• As the window slides, the program updates the frequency map by removing the outgoing element and adding the incoming element.
• It prints the number of distinct elements for each window.

Example Output

Distinct count in window 1: 2
Distinct count in window 2: 3
Distinct count in window 3: 3
Distinct count in window 4: 3

This output indicates the distinct count of elements in each sliding window of size k.

Explanation of the Code

1. Imports: We import the HashMap class from the Java Collections Framework.
2. Function Definition: The countDistinct function takes an integer array and the size of the sliding window as parameters.
3. HashMap: We use a HashMap to store the frequency of each element.
4. Initial Window Setup: The first loop sets up the initial window by counting the elements and their frequencies.
5. Sliding Window: The second loop slides the window through the array, updating the frequency map and counting distinct elements for each new window.
6. Output: It prints the count of distinct elements for each sliding window.

This approach ensures efficient counting while sliding the window, maintaining an overall time complexity of $O(n)$.