Sliding Window || Aditya Verma's Approach || Easy to Understand
Link to a similar problem && solution :) \nhttps://leetcode.com/problems/binary-subarrays-with-sum/solutions/3379313/easy-sliding-window-comments-added-for-expl
# Link to a similar problem && solution :) \nhttps://leetcode.com/problems/binary-subarrays-with-sum/solutions/3379313/easy-sliding-window-comments-added-for-explanation-beats-92/ \n# Approach :\nThe given code provides a solution to find the number of subarrays that contain exactly k distinct integers. It uses a sliding window approach with the help of an unordered map to keep track of the count of each integer in the current window.\n\nThe subarrayCountWithAtMostKchar function is used to find the number of subarrays that have at most k distinct integers. It initializes two pointers i and j at the start of the array and uses an unordered map mp to keep track of the count of each integer in the current window. It then moves the right pointer j forward, increments the count of the integer arr[j] in the map, and checks if the number of distinct integers in the map is less than or equal to k. If it is, then it updates the count with the number of subarrays that can be formed with this window and moves the right pointer j forward. If it is not, then it moves the left pointer i forward, decrements the count of the integer arr[i] in the map, and checks if the count becomes 0. If it does, then it removes the integer from the map. It continues this process until the number of distinct integers in the map is less than or equal to k. After shrinking the window, it updates the count with the number of subarrays that can be formed with this window and moves the right pointer j forward. It repeats this process until the right pointer j reaches the end of the array.\n\nThe subarraysWithKDistinct function is used to find the number of subarrays that have exactly k distinct integers. It calls the subarrayCountWithAtMostKchar function twice with k and k-1 as input, respectively. It then returns the difference between these two counts, which gives the count of subarrays that have exactly k distinct integers.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity : The time complexity of the given code is $$O(N)$$, where N is the length of the input array arr or nums. This is because we iterate through each element of the array once using the sliding window approach, and perform constant time operations at each step.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity :  The space complexity of the given code is  $$O(K)$$, where K is the size of the unordered map mp. This is because we store at most K distinct integers in the map at any given time.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// This is a solution to find the number of subarrays that contain exactly k distinct integers\n\nclass Solution {\npublic:\n    int subarrayCountWithAtMostKchar(vector<int>& arr, int k) {\n        int i = 0, j = 0, count = 0;\n        unordered_map<int, int> mp; // create an unordered map to keep track of the count of each integer\n\n        while (j < arr.size()) {\n            mp[arr[j]]++; // increment the count of integer arr[j] in the map\n\n            if (mp.size() <= k) { // if the number of distinct integers in the map is less than or equal to k\n                count += j - i + 1; // then update the count with the number of subarrays that can be formed with this window\n                j++; // move the right pointer forward\n            } else {\n                while (mp.size() > k) { // if the number of distinct integers in the map is greater than k\n                    mp[arr[i]]--; // decrement the count of the integer arr[i] in the map\n\n                    if (mp[arr[i]] == 0) { // if the count becomes 0\n                        mp.erase(arr[i]); // then remove the integer from the map\n                    }\n\n                    i++; // move the left pointer forward\n                }\n\n                if (mp.size() <= k) { // after shrinking the window, if the number of distinct integers in the map is less than or equal to k\n                    count += j - i + 1; // then update the count with the number of subarrays that can be formed with this window\n                }\n\n                j++; // move the right pointer forward\n            }\n        }\n\n        return count; // return the count\n    }\n\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        int a = subarrayCountWithAtMostKchar(nums, k); // get the count of subarrays with at most k distinct integers\n        int b = subarrayCountWithAtMostKchar(nums, k - 1); // get the count of subarrays with at most k-1 distinct integers\n\n        return a - b; // the difference between these counts gives the count of subarrays with exactly k distinct integers\n    }\n};\n\n```\n\n---\n\n**PLEASE UPVOTE IF YOU LIKED THE SOLUTION :)**\n\n**![ezgif.com-optimize.gif](https://assets.leetcode.com/users/images/a234e8f5-3869-425b-94a7-beee9509065f_1680614836.0752363.gif)**\n
['Sliding Window', 'C++']