Program Description

This C program counts the number of distinct elements in each sliding window of size k in a given array. It utilizes a hash map (or an array for limited ranges) to track the frequency of elements in the current window.

Program Structure

1. Include necessary headers: The program includes standard input-output headers for basic functionality.
2. Function prototype: The function countDistinctInWindow is defined to handle the counting of distinct elements.
3. Main function: This serves as the entry point for the program. It initializes the array and calls the distinct counting function.
4. Logic for counting: The main logic utilizes a hash map to maintain the count of each element in the current window.

Code Implementation

#include 
#include 

void countDistinctInWindow(int arr[], int n, int k) {
    int *count = (int *)calloc(100000, sizeof(int)); // Assuming elements are in a range of 0 to 99999
    int distinctCount = 0;

    // Initialize the first window
    for (int i = 0; i < k; i++) {
        if (count[arr[i]] == 0) {
            distinctCount++;
        }
        count[arr[i]]++;
    }
    printf("Number of distinct elements in the first window: %d\n", distinctCount);

    // Slide the window
    for (int i = k; i < n; i++) {
        // Add the new element
        if (count[arr[i]] == 0) {
            distinctCount++;
        }
        count[arr[i]]++;

        // Remove the element going out of the window
        count[arr[i - k]]--;
        if (count[arr[i - k]] == 0) {
            distinctCount--;
        }

        printf("Number of distinct elements in window %d: %d\n", i - k + 1, distinctCount);
    }

    free(count);
}

int main() {
    int arr[] = {1, 2, 1, 3, 4, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;

    countDistinctInWindow(arr, n, k);
    return 0;
}
    

Explanation of the Code

• Dynamic Memory Allocation: An array count is dynamically allocated to keep track of the frequency of elements. The size is chosen to accommodate a wide range of integer values.
• Initial Window Setup: The first k elements are processed to populate the count array and determine the number of distinct elements.
• Sliding Window Logic: The program iterates through the array, updating the count for the entering and exiting elements of the window, adjusting the distinct count accordingly.
• Output: The number of distinct elements for each window is printed to the console.

Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the array, as each element is processed a constant number of times.
• Space Complexity: O(m), where m is the range of the input values stored in the count array.

Conclusion

This program efficiently counts distinct elements in every sliding window of size k using a hash map for frequency counting, allowing for quick updates as the window slides.