Counting Subarrays with Exactly K Distinct Integers: A Sliding Window Adventure ✅✅✅🔥🔥
\n\nIntuition\n\nThe sliding window technique is a powerful approach for efficiently finding subarrays within a larger array that meet specific criteria. In thi
\n\n**Intuition**\n\nThe sliding window technique is a powerful approach for efficiently finding subarrays within a larger array that meet specific criteria. In this case, we\'re interested in subarrays containing exactly `k` distinct integers.\n\nHere\'s the basic idea:\n\n1. **Two Pointers (`i` and `j`)** represent the start and end of the current subarray window.\n2. **Hashmap (`mp`)** keeps track of the frequency of each element encountered within the window.\n3. **Iterate** using `j` to expand the window rightward, adding elements to the hashmap.\n4. **Maintain Condition:**\n   - If the number of distinct elements in `mp` exceeds `k` (meaning the window contains more than `k` distinct integers), shrink the window by moving `i` forward and removing elements from `mp` until the condition is satisfied.\n5. **Count Valid Subarrays:**\n   - For each valid subarray with exactly `k` distinct elements (determined by `mp.size()` being equal to `k`), add the window size (`j - i + 1`) to a `count` variable.\n\n**Approach (Breakdown with Images)**\n\n1. **Initialization:**\n\n   - Set `i` and `j` to 0.\n   - Initialize `count` to 0.\n   - Create an empty hashmap `mp`.\n\n   \n\n2. **Iteration and Window Expansion:**\n\n   - **While `j` is less than the array length `n`:**\n     - Increment the frequency of the current element `nums[j]` in the hashmap `mp`.\n\n     \n\n   - **Check for Subarray Validity:**\n     - **While `mp.size()` (number of distinct elements) is greater than `k`:**\n       - Decrement the frequency of the element at `nums[i]` in `mp`.\n       - If the frequency becomes 0, remove the element from `mp` using `mp.erase(nums[i])`.\n       - Move `i` forward to shrink the window and maintain the condition.\n\n       \n\n3. **Count Valid Subarrays:**\n\n   - **For each valid subarray:**\n     - Add the current window size (`j - i + 1`) to the `count` variable. This represents the number of possible subarrays within the current window that all have exactly `k` distinct elements.\n\n     \n\n   - Move `j` forward to expand the window for the next iteration.\n\n4. **Return the Final Count:**\n\n   - The final `count` variable stores the total number of subarrays in the input array that contain exactly `k` distinct integers.\n\n**Complexity**\n\n- **Time Complexity: O(n)**\n  - Both `i` and `j` iterate through the array at most once, resulting in linear time complexity.\n- **Space Complexity: O(n)**\n  - The hashmap `mp` can potentially store up to `n` distinct elements in the worst case, leading to linear space complexity.\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int slidingWindow(vector<int>&nums, int k){\n        int n = nums.size();\n        int i = 0, j = 0, count = 0;\n        unordered_map<int,int>mp;\n        while(j < n){\n            mp[nums[j]]++;\n            while(mp.size() > k){\n                mp[nums[i]]--;\n                if(mp[nums[i]] == 0)\n                    mp.erase(nums[i]);\n                i++;\n            }\n            count += j - i + 1;\n            j++;\n        }\n        return count;\n    }\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        return slidingWindow(nums,k) - slidingWindow(nums,k-1);\n    }\n};\n```\n```Java []\nclass Solution {\n    public int slidingWindow(int[] nums, int k) {\n        int n = nums.length;\n        int i = 0;\n        int j = 0;\n        int count = 0;\n        HashMap<Integer, Integer> map = new HashMap<>();\n        \n        while (j < n) {\n            map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);\n            \n            while (map.size() > k) {\n                map.put(nums[i], map.get(nums[i]) - 1);\n                if (map.get(nums[i]) == 0)\n                    map.remove(nums[i]);\n                i++;\n            }\n            \n            count += j - i + 1;\n            j++;\n        }\n        \n        return count;\n    }\n    \n    public int subarraysWithKDistinct(int[] nums, int k) {\n        return slidingWindow(nums, k) - slidingWindow(nums, k - 1);\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def slidingWindow(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        i = 0\n        j = 0\n        count = 0\n        mp = {}\n        \n        while j < n:\n            mp[nums[j]] = mp.get(nums[j], 0) + 1\n            \n            while len(mp) > k:\n                mp[nums[i]] -= 1\n                if mp[nums[i]] == 0:\n                    del mp[nums[i]]\n                i += 1\n            \n            count += j - i + 1\n            j += 1\n        \n        return count\n    \n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        return self.slidingWindow(nums, k) - self.slidingWindow(nums, k - 1)\n\n```\n\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar subarraysWithKDistinct = function(nums, k) {\n    const slidingWindow = (nums, k) => {\n        let i = 0, j = 0, count = 0;\n        const map = new Map();\n        \n        while (j < nums.length) {\n            map.set(nums[j], (map.get(nums[j]) || 0) + 1);\n            \n            while (map.size > k) {\n                map.set(nums[i], map.get(nums[i]) - 1);\n                if (map.get(nums[i]) === 0) map.delete(nums[i]);\n                i++;\n            }\n            \n            count += j - i + 1;\n            j++;\n        }\n        \n        return count;\n    };\n    \n    return slidingWindow(nums, k) - slidingWindow(nums, k - 1);\n};\n\n```\n```Kotlin []\nclass Solution {\n    fun slidingWindow(nums: IntArray, k: Int): Int {\n        var i = 0\n        var j = 0\n        var count = 0\n        val map = HashMap<Int, Int>()\n        \n        while (j < nums.size) {\n            map[nums[j]] = map.getOrDefault(nums[j], 0) + 1\n            \n            while (map.size > k) {\n                map[nums[i]] = map[nums[i]]!! - 1\n                if (map[nums[i]] == 0) map.remove(nums[i])\n                i++\n            }\n            \n            count += j - i + 1\n            j++\n        }\n        \n        return count\n    }\n    \n    fun subarraysWithKDistinct(nums: IntArray, k: Int): Int {\n        return slidingWindow(nums, k) - slidingWindow(nums, k - 1)\n    }\n}\n\n```\n\n
['Array', 'Hash Table', 'Sliding Window', 'C++', 'Java', 'Python3', 'Kotlin', 'JavaScript']