Problem Statement

Given an array of integers and an integer k, our task is to find the count of distinct elements in every window of size k.

Examples

Example 1

Input: nums = [1, 2, 1, 3, 4, 2, 3], k = 4

Output: [3, 4, 4, 3]

Explanation:

Window [1, 2, 1, 3] contains 3 distinct elements: 1, 2, and 3.
Window [2, 1, 3, 4] contains 4 distinct elements: 1, 2, 3, and 4.
Window [1, 3, 4, 2] contains 4 distinct elements: 1, 2, 3, and 4.
Window [3, 4, 2, 3] contains 3 distinct elements: 2, 3, and 4.

Example 2

Input: nums = [1, 1, 1, 1, 1, 1], k = 2

Output: [1, 1, 1, 1]

Explanation:

Window [1, 1] contains 1 distinct element: 1.
Window [1, 1] contains 1 distinct element: 1.
Window [1, 1] contains 1 distinct element: 1.
Window [1, 1] contains 1 distinct element: 1.
Window [1, 1] contains 1 distinct element: 1.

Different Approaches

1 Brute Force Approach With Set

We iterate through all the possible subarrays of size k. We will be using a set data structure to store the distinct elements within each window of size k. A set ensures that each element is unique, allowing us to efficiently find the count of distinct elements within the window.

Why a Set?

• Sets allow us to maintain a collection of unique elements. Duplicate elements can't be stored. So, after inserting all the elements of window of size k in the set, we can check the set size which will return the unique elements for that window. 
• By storing elements in a set, we can easily determine the count of distinct elements within a window.
• Sets provide efficient insertion and lookup operations, allowing us to efficiently find the count of distinct elements in each window.

Algorithm:

1. Initialize a vector result to store the count of distinct elements for each window.
2. Iterate through the array from index 0 to n - k:
   1. Initialize an empty set distinct_set to store distinct elements within the current window.
   2. Iterate through the current window of size k and add each element to distinct_set.
   3. Update distinct_count with the size of distinct_set.
3. Return result vector.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> countDistinct(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;

    for (int i = 0; i <= n - k; i++) {
        unordered_set<int> distinct_set;
        for (int j = i; j < i + k; j++) {
            distinct_set.insert(nums[j]);
        }
        result.push_back(distinct_set.size());
    }

    return result;
}

Complexity Analysis

Time Complexity:O(n*k), where n is the number of elements in the array, while k is the size of the window.

Space Complexity:O(k), where k is the size of the window.

2 Sliding Window using Hash Map

In this approach, we use the sliding window technique along with a hash map to find the count of distinct elements in every window of size k. We maintain a window of size k and a hash map to store the frequency of elements within the window. By sliding the window and updating the frequency map accordingly, we can find the count of distinct elements in each window.

1. Sliding Window Technique: We use the sliding window technique to maintain a window of size k as it moves along the array.
2. Hash Map for Frequency: We maintain a hash map to store the frequency of elements within the window. The key of the hash map represents the element, and the value represents its frequency within the window.
3. Updating Frequency Map: As we slide the window, we update the frequency map by adding the new element and removing the element that goes out of the window.
4. Counting Distinct Elements: By maintaining the size of the frequency map, we can find the count of distinct elements in each window.

Data Structures Used:

• Hash Map: We use a hash map to store the frequency of elements within each window of size k. The key of the hash map represents the elements, and the value represents its frequency within the window.

Why a Hash Map?

• Hash maps allow us to efficiently store and update the frequency of elements within a window.
• By using a hash map, we can easily determine the count of distinct elements within a window.
• Hash maps provide efficient insertion, deletion, and lookup operations, making them suitable for this problem.

Algorithm:

1. Initialize left and right pointers to 0.
2. Initialize a hash map freq_map to store the frequency of elements within the window.
3. Initialize a variable distinct_count to store the count of distinct elements in each window.
4. Iterate through the array using the sliding window approach:
   1. Add nums[right] to freq_map.
   2. If the size of the window is equal to k, update distinct_count with the size of the frequency map.
   3. If the size of the window exceeds k, remove nums[left] from freq_map and increment left.
5. Return an array containing the count of distinct elements for each window.

Code Implementation using C++:

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

using namespace std;

vector<int> countDistinct(vector<int>& nums, int k) {
    int n = nums.size();
    int left = 0, right = 0;
    unordered_map<int, int> freq_map; // Hash map to store frequency of elements within the window
    vector<int> result;

    // Iterate through the array using the sliding window approach
    while (right < n) {
        freq_map[nums[right]]++; // Add nums[right] to freq_map

        // If the size of the window is equal to k
        if (right - left + 1 == k) {
            result.push_back(freq_map.size()); // Count the number of distinct elements
            if (--freq_map[nums[left]] == 0) { // Remove nums[left] from freq_map
                freq_map.erase(nums[left]);
            }
            left++; // Move the left pointer to slide the window
        }
        right++; // Move the right pointer to slide the window
    }

    return result; // Return an array containing the count of distinct elements for each window
}

Complexity Analysis:

Time Complexity:O(n), where n is the number of elements.

Space Complexity:O(k), where k is the size of the window.