This document presents a C++ program to count distinct elements in every window of size k within a given array. The approach utilizes a hash map to efficiently track the count of elements in each sliding window.

Program Explanation

The program consists of the following key components:

1. Input Handling:The program first reads the size of the array and the size of the window k. Then, it reads the elements of the array.
2. Sliding Window Technique:We use a sliding window approach where we maintain a count of elements in the current window using a hash map. This allows us to efficiently update the count as the window moves.
3. Output:For each window, we print the count of distinct elements.

C++ Code

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

/**
 * Function to count distinct elements in every window of size k.
 * 
 * @param arr The input array of integers.
 * @param n The size of the array.
 * @param k The size of the window.
 */
void countDistinctInWindow(int arr[], int n, int k) {
    unordered_map<int, int> elementCount; // Map to store counts of elements
    int distinctCount = 0; // Count of distinct elements in the current window

    // Process the first k elements separately
    for (int i = 0; i < k; i++) {
        if (elementCount[arr[i]] == 0) {
            distinctCount++;
        }
        elementCount[arr[i]]++;
    }

    cout << distinctCount << " "; // Print count of distinct elements for the first window

    // Slide the window from start to end of the array
    for (int i = k; i < n; i++) {
        // Add the new element to the window
        if (elementCount[arr[i]] == 0) {
            distinctCount++;
        }
        elementCount[arr[i]]++;

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

        cout << distinctCount << " "; // Print count for the current window
    }
}

int main() {
    int n, k;
    
    // Input size of array and size of the window
    cout << "Enter the size of the array: ";
    cin >> n;
    cout << "Enter the size of the window k: ";
    cin >> k;

    int arr[n]; // Array to store elements

    // Input the elements of the array
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Function call to count distinct elements in every window of size k
    countDistinctInWindow(arr, n, k);

    return 0;
}

Explanation of the Program

1. Header Files:
   • <iostream> for input and output operations.
   • <unordered_map> for using a hash map to store element counts.
   • <vector> for working with vectors (though not used here, it’s often included in modern C++ programs).
2. Function countDistinctInWindow:
   • This function takes an array of integers, its size, and the window size k as parameters.
   • It initializes a hash map to count occurrences of elements and a variable to track the number of distinct elements.
3. Processing the First Window:
   • The first k elements are processed separately to initialize the count.
4. Sliding the Window:
   • For each new element added to the window, it checks if it’s new and updates the count.
   • It also removes the element that goes out of the window, adjusting the distinct count as needed.
5. Main Function:
   • It handles user input for the array size, window size, and the elements of the array.
   • Finally, it calls the counting function.

How to Run the Program

1. Copy the code into a file named countDistinct.cpp.
2. Open a terminal and navigate to the directory where the file is saved.
3. Compile the program using a C++ compiler, e.g., g++ countDistinct.cpp -o countDistinct.
4. Run the executable: ./countDistinct.
5. Follow the prompts to enter the size of the array, the size of the window, and the elements of the array.

Conclusion

This program efficiently counts the distinct elements in every window of size k using a sliding window technique and a hash map for counting. This method ensures optimal performance with a time complexity of O(n), where n is the number of elements in the array.