Subarrays with K Different Integers

class Solution {
   public:
    int countKDistinctSubarrays(vector<int>& arr, int k) {
        vector<int> count(arr.size() + 1, 0);
        int totalSubarrays = 0, start = 0, end = 0, windowSize = 0;
    
        while (end < arr.size()) {
            if (++count[arr[end++]] == 1) {
                k--;
            }
    
            if (k < 0) {
                --count[arr[start++]];
                k++;
                windowSize = 0;
            }
    
            if (k == 0) {
                while (count[arr[start]] > 1) {
                    --count[arr[start++]];
                    windowSize++;
                }
                totalSubarrays += (windowSize + 1);
            }
        }
        return totalSubarrays;
    }
};

In the provided C++ code, the solution focuses on finding the number of subarrays within a given array that contain exactly k distinct integers. It uses a sliding window approach with two pointers, start and end, to efficiently determine the count of such subarrays without the need to check every possible subarray explicitly. Here's a breakdown of how the code tackles the problem:

• A function countKDistinctSubarrays is declared, which takes a vector of integers arr and an integer k as parameters, representing the array and the number of distinct integers in the subarrays, respectively.
• Initially, a count vector is created to keep track of the frequency of each element in the current window. The totalSubarrays variable is initialized to zero to store the result.
• The outer while loop progresses the end pointer from the beginning to the end of the array, incrementing the count of each element as it is included in the window. If a new distinct element is added (count[arr[end]] == 1), k is decremented.
• When k becomes negative (meaning the window has more than k distinct integers), the window is adjusted by moving the start pointer forward and reducing the counts accordingly until k is non-negative.
• An inner while loop further adjusts the start pointer to ensure that every possible subarray starting from the current position of start and ending at end - 1 is counted. The count of such valid subarrays is then incremented based on the size of the window freeze frame, which ensures subarrays containing exactly k distinct integers are counted.
• Finally, the function returns totalSubarrays, which is the count of subarrays containing exactly k distinct integers.

The beauty of this approach lies in its efficiency—by maintaining a dynamic sliding window of the array, the solution avoids the computational overhead of checking each subarray individually, which would be substantially slower especially for large arrays. The sliding window technique, combined with careful counting of distinct elements and adjusting the window size, offers an optimal solution to the problem.

class Solution {
    public int countSubarraysWithKDistinct(int[] arr, int k) {
        int[] countMap = new int[arr.length + 1];
        int total = 0;
        int start = 0;
        int end = 0;
        int count = 0;
    
        while (end < arr.length) {
            if (countMap[arr[end++]]++ == 0) {
                k--;
            }
    
            if (k < 0) {
                --countMap[arr[start++]];
                k++;
                count = 0;
            }
    
            if (k == 0) {
                while (countMap[arr[start]] > 1) {
                    --countMap[arr[start++]];
                    count++;
                }
                total += (count + 1);
            }
        }
        return total;
    }
}

This solution aims to tackle the problem of counting subarrays in an array that contain exactly K different integers. It uses an array-based sliding window approach to efficiently keep track of the number of distinct integers and calculates the subarray counts.

• The function countSubarraysWithKDistinct takes two parameters: an integer array arr and an integer k representing the desired number of distinct integers.
• A countMap array is utilized to store the frequency of each integer in the current window of the array.
• Variables total, start, end, and count are initialized to manage the counting and the window's bounds during the traversal of the array.
• As the end point of the sliding window expands (end++), the array element at this position increments in the countMap and checks if a new integer has been added (countMap[arr[end]]++ == 0). If yes, decrement k.
• If k becomes less than zero, meaning the window has more than k distinct integers, the algorithm shrinks the window from the start side until k is no longer negative. This is done by incrementing the start pointer and adjusting the map and k accordingly.
• When k is exactly zero, indicating the window has exactly k distinct integers, count possible subarrays originating from this window configuration. It increments count for all duplicate start elements and adds these to total.
• The algorithm keeps adjusting the window using the start and end pointers and updates the total count of valid subarrays.
• Finally, total is returned, providing the count of all subarrays in arr that contain exactly k different integers.

This Java implementation efficiently manages the exploration of subarrays using both increasing and decreasing the bounds of a sliding window based on the status of k and updates the count of distinct integers efficiently using an array to represent current integer frequencies within the window.

class Solution:
    def countDistinctSubarrays(self, arr: List[int], distinct_num: int) -> int:
        count_dict = [0] * (len(arr) + 1)
    
        total_subarrays = 0
        window_start = 0
        window_end = 0
        active_count = 0
    
        while window_end < len(arr):
            count_dict[arr[window_end]] += 1
    
            if count_dict[arr[window_end]] == 1:
                distinct_num -= 1
    
            if distinct_num < 0:
                count_dict[arr[window_start]] -= 1
                if count_dict[arr[window_start]] == 0:
                    distinct_num += 1
                window_start += 1
                active_count = 0
    
            if distinct_num == 0:
                while count_dict[arr[window_start]] > 1:
                    count_dict[arr[window_start]] -= 1
                    window_start += 1
                    active_count += 1
                total_subarrays += (active_count + 1)
    
            window_end += 1
    
        return total_subarrays

This Python3 solution defines a method countDistinctSubarrays in the Solution class to solve the problem of finding subarrays containing exactly K distinct integers. Here's how the implementation works:

• Initialize a list count_dict of size len(arr) + 1 to zero, to keep track of the count of each element within the current window of the subarray.
• Set total_subarrays, window_start, window_end, and active_count to 0.
• Traverse the array using the window_end variable. For each element at window_end, increment its count in count_dict.
• Decrement distinct_num when a new distinct element is encountered by checking if its count becomes one.
• If distinct_num becomes negative, adjust the window_start to potentially remove some elements from the current subarray to try and bring back the count of distinct integers within the required limit.
• Whenever distinct_num reaches zero, meaning the subarray between window_start and window_end has exactly K distinct integers, further adjust window_start and count the number of valid subarrays.
• Continue this until window_end has traversed the entire array.
• Return the total_subarrays count, which represents the number of subarrays having exactly K distinct integers.

This approach utilises the sliding window technique combined with a frequency count array, effectively allowing the program to consider each possible subarray and record the valid ones as per the given conditions. Adjustments of the window_start help ensure that once a valid subarray configuration is disturbed (due to an exceeding number of distinct integers), it is realigned to remain within the problem constraints.

Efficient management of the subarray window and an accurate count of valid configurations ensure that the solution is both effective and optimal for large inputs.