Simple Sliding Window with Atmost K different integers || C++
Intuition\nOn seeing the problem, the first thought that strucks my mind is sliding window. Ofcourse you have to make certain changes to that approach to get to
# Intuition\nOn seeing the problem, the first thought that strucks my mind is sliding window. Ofcourse you have to make certain changes to that approach to get to the original solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. find the no. of subarrays that have atmost k different integers(lets call it count1)\n2. find the no. of subarrays that have atmost k-1 different integers(lets call it count2)\n3. return count1-count2.\n\nWhy does this works?\n\ncount1 (the no. of subarrays that have atmost k different integers)will also contain count2 (the no. of subarrays that have atmost k-1 different integers). So when we subtract count2 from count1 we will be only left with the no. of subarrays that have exactly k different elements.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n     $$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n     $$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n   int countSubarray(vector<int>& nums,int k)\n   {\n     unordered_map<int,int> mp;\n\n        int i=0,j=0;\n        int count=0;\n\n        \n        while(j<nums.size())\n        {\n            mp[nums[j]]++;\n\n            while(mp.size()>k && i<=j)\n            {\n                mp[nums[i]]--;\n                if(mp[nums[i]]==0)\n                mp.erase(nums[i]);\n\n                i++;\n            }\n\n\n            count+=j-i+1;\n\n            j++;\n\n\n\n        }\n\n\n        return count;\n\n\n   }\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n\n       \n        int count1=countSubarray(nums,k);\n        int count2=countSubarray(nums,k-1);\n\n\n        return count1-count2;\n\n        \n\n\n        \n    }\n};\n```
['Two Pointers', 'Ordered Map', 'Sliding Window', 'C++']