C++ | Sliding Window | Faster than 96% with Explanation | O(n)
At first the problem seems to be tricky. We need to calculate number of Subarrays with exactly K distinct elements and this is where we feel defeated by our int
At first the problem seems to be tricky. We need to calculate number of Subarrays with ```exactly K distinct elements``` and this is where we feel defeated by our intuition. We need to somehow drop this word!\n\n```\n\t(exact K) = (atmost K) - (atmost K - 1)\n```\n\nThe above equation makes problem simpler.\n\n**Solution to number of Subarrays with Atmost K distinct elements**\nwe just need two pointers `left` and `right` and a container which can store the numbers in between these pointers and give results to queries like how many distinct elements it has. So a `map` data structure comes into picture. `(unordered_map will also work.)`\n\nNow, we\'ll keep populating map with elements untill the either `size of map < k` or `right` pointer pointes to an element which is already in our `map`. otherwise `right` pointer is pointing to `(k+1)th` distinct element so we will start reducing our window size. \n\nAlso we\'ll use following formula to `count number of subarrays` starting at index `left` and ends before index `right`.\n```\n\tnumberOfSubarrays = right - left  // starting at index left\n```\nThat\'s it.\n\n**Time Complexity** : O(n)\n**Space complexity** : O(n)\n\n**Implementation 1: (normal)**\n\n```\nclass Solution {\npublic:\n    int subarraysWithAtmostKDistinct(vector<int>& values, int k)\n    {\n        unordered_map<int,int> occurences;\n        int ans = 0;\n        int j = 0;\n        int n = values.size();\n        for(int i=0; i<n; i++)\n        {\n            while(j<n && (occurences.size() < k || occurences.count(values[j])))\n            {\n                occurences[values[j]]++;\n                j++;\n            }\n            ans += j - i; // number of subarrays starting at index i\n            // and ends before j\n            occurences[values[i]]--;\n            if(occurences[values[i]] == 0)\n                occurences.erase(values[i]); \n        }\n        return ans;\n    }\n    \n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        // results will be difference in the\n        // number of subarrays with atmost (k-1) distinct elements and\n        // number of subarrays with atmost (k) distinct elements\n        // Time complexity: O(n)\n        \n        int atmostKminus1 = subarraysWithAtmostKDistinct(nums, k-1);\n        int atmostK = subarraysWithAtmostKDistinct(nums, k);\n        if(k==1)\n            atmostKminus1 = 0; // as there would not be any distinct element in a subarray\n        // of size 0\n        return (atmostK - atmostKminus1);\n    }\n};\n```\n\n\n**Implementation 2: Beats 96% of CPP Solution**\nSince the range of nums[i] is `1 <= nums[i] <= nums.length() `. We can use `vector` instead of `map` and thus improving the execution time by exploiting fast random access time of arrays.  \n\n```\nclass MyMap {\npublic:\n    // we\'ll use array implemetation of map\n    // with minimum required functionality\n    \n    vector<int> counter;\n    int distinctElements = 0;\n    \n    MyMap() : distinctElements(0) {}\n    MyMap(int n)\n    {\n        // map of capacity of n elements\n        counter.resize(n+1, 0);\n    }\n    \n    // setter functions\n    void insertOne(int val)\n    {\n        if(!counter[val])\n        {\n            distinctElements++;\n        }\n        \n        counter[val]++; // increment distinct element count if it is not present initially\n    } \n    \n    void eraseOne(int val)\n    {\n        if(counter[val] == 1)\n        {\n            distinctElements--;\n        }\n        counter[val]--;\n    }\n    \n    // getter functions\n    int size()\n    {\n       return distinctElements; \n    }\n    \n    bool count(int val)\n    {\n       return counter[val]; \n    }\n};\nclass Solution {\npublic:\n    int subarraysWithAtmostKDistinct(vector<int>& values, int k)\n    {\n        int ans = 0;\n        int j = 0;\n        int n = values.size();\n        MyMap occurences = MyMap(n);\n        for(int i=0; i<n; i++)\n        {\n            while(j<n && (occurences.size() < k || occurences.count(values[j])))\n            {\n                occurences.insertOne(values[j]);\n                j++;\n            }\n            ans += j - i; // number of subarrays starting at index i\n            // and ends before j\n            occurences.eraseOne(values[i]); \n        }\n        return ans;\n    }\n    \n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        // results will be difference in the\n        // number of subarrays with atmost (k-1) distinct elements and\n        // number of subarrays with atmost (k) distinct elements\n        // Time complexity: O(n)\n        \n        int atmostKminus1 = subarraysWithAtmostKDistinct(nums, k-1);\n        int atmostK = subarraysWithAtmostKDistinct(nums, k);\n        if(k==1)\n            atmostKminus1 = 0; // as there would not be any distinct element in a subarray\n        // of size 0\n        return (atmostK - atmostKminus1);\n    }\n};\n```
[]