C++ Easy | Sliding Window + Map | Easy Step By Step Explanation
\n\n# Intuition\n- The problem asks us to count the number of subarrays in an array nums that contain exactly k distinct integers. We can approach this by using
![Zombie Upvote.png](https://assets.leetcode.com/users/images/401d1ad0-4b65-400b-8969-c6d12df1ad86_1711759371.0116253.png)\n\n# Intuition\n- The problem asks us to count the number of subarrays in an array nums that contain exactly k distinct integers. We can approach this by using a sliding window technique:\n\n1. **Maintain a window:** We\'ll use two pointers, left and right, to define a subarray within nums.\n2. **Track distinct elements:** We\'ll use a hash map (mp) to keep track of the frequencies of elements encountered within the window.\n3. **Expand the window:** Initially, the window will be empty (left = right = 0). We\'ll increment right to include new elements.\n4. **Ensure at most k distinct elements:** If the size of the hash map (mp.size()) exceeds k, we need to shrink the window from the left (left++) until the condition is met. To maintain efficiency, we\'ll also remove elements from the hash map if their frequency drops to 0.\n5. **Count valid subarrays:** With each valid window (mp.size() == k), we can calculate the number of subarrays it represents. The length of this valid window is right - left + 1, and every subarray within this range will have exactly k distinct elements.\n\n# Approach\n1. **Define helper function findAtMostK:** This function takes the array nums, the desired number of distinct elements (k), and the array size (n) as input. It returns the count of subarrays with at most k distinct elements.\n\n    - Initialize counters ans (to store the count), left (starting index), and right (ending index).\n    - Create a hash map mp to store element frequencies.\nEnter a while loop iterating until right reaches the end of the array (right < n).\n    - If the current element (nums[right]) isn\'t in the hash map, add it with a frequency of 1. Otherwise, increment its frequency.\n    - While the number of distinct elements (mp.size()) is greater than k:\n        - Decrement the frequency of the leftmost element (nums[left]).\n        - If the frequency becomes 0, remove the element from the hash map (mp.erase(nums[left])).\n        - Increment left to shrink the window.\n    - Since the current window has mp.size() == k distinct elements, we can calculate the number of subarrays it represents: right - left + 1. Add this to ans.\n    - Increment right to expand the window for the next iteration.\n    - Return the final count (ans).\n    \n2. **Main function subarraysWithKDistinct:** This function takes the array nums and the target number of distinct elements (k) as input.\n\n    - Get the array size n.\n    - Call the helper function findAtMostK twice: once to find subarrays with at most k distinct elements, and once for at most k-1 distinct elements.\n    - The difference between these counts gives us the number of subarrays with exactly k distinct elements: findAtMostK(n, k, nums) - findAtMostK(n, k-1, nums).\n    - Return the final count.\n\n# Complexity\n- Time complexity: **O(n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(k)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#pragma GCC optimize("03", "unroll-loops")\nclass Solution {\npublic:\n    int findAtMostK(int n, int k, vector<int>&nums){\n        int ans = 0;\n        int left = 0, right = 0;\n        unordered_map<int, int>mp;\n        while(right<n){\n            if(mp.find(nums[right])==mp.end()){\n                mp[nums[right]] = 1;\n            }\n            else{\n                mp[nums[right]]++;\n            }\n\n            while(mp.size()> k && left<=right){\n                mp[nums[left]]--;\n                if(mp[nums[left]]==0){\n                    mp.erase(nums[left]);\n                }\n                left++;\n            }\n            ans += right-left+1;\n            right++;\n        }\n        return ans;\n    }\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        int n = nums.size();\n        return findAtMostK(n, k, nums) - findAtMostK(n, k-1, nums);\n    }\n};\nauto init = [](){\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n![Please Upvote2.jpeg](https://assets.leetcode.com/users/images/d82987f1-fba4-414e-9ab1-381469b33ddd_1711759381.106188.jpeg)\n
['Array', 'Hash Table', 'Ordered Map', 'Sliding Window', 'C++']