Sliding window count subarrays with at most K  distinct elements||15ms Beats 99.87%
Intuition\n Describe your first thoughts on how to solve this problem. \ncount subarrays with at most K  distinct elements. it makes problem  much easier!\n\ngo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ncount subarrays with at most K  distinct elements. it makes problem  much easier!\n```\ngoodLessEqualK(nums, k)-goodLessEqualK(nums, k-1)\n```\nThe rest is the same method, same pattern, used for several days.\n2 C++ codes are provided, the second one is the dual version for the 1st one & even faster. 1 python code is provided.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/Z113uN6sKDc?si=QvC_REca7V0vt6tW](https://youtu.be/Z113uN6sKDc?si=QvC_REca7V0vt6tW)\nThe following questions can be solved sliding window:\n[713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/solutions/4930759/2c-sliding-windows30ms-beats-9992/)\n[2302. Count Subarrays With Score Less Than K](https://leetcode.com/problems/count-subarrays-with-score-less-than-k/solutions/4932340/sliding-windows-like-leetcode-713-44ms-beats-100/)\n[2958. Length of Longest Subarray With at Most K Frequency](https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/solutions/4935191/sliding-window-hash-map128ms-beats-9978/)\n[2962. Count Subarrays Where Max Element Appears at Least K Times\n](https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/solutions/4939830/sliding-window-vs-combinatorical-formula-59ms-beats-100/)\n\n\nThese problems can be solved by the following pattern:\n```\nfor(int l,r=0; r<n; r++){\n    do_something_by_adding(nums[r]);\n    while (!check_condition(k)){\n        do_something_by_removing(nums[l]);\n        l++;\n    }\n    update_the_answer();\n}\n```\nLet\'s consider the testcase=`nums=[1,2,1,2,3,1,2,4,8,2], k=3`. The process for that is modified from the submitted python code:\n```\n--------\nProceed goodLessEqualK(nums, k) with k= 3\nr= 0 freq= {1: 1} dist= 1\n\t=>freq= {1: 1} adding  1 to cnt\nr= 1 freq= {1: 1, 2: 1} dist= 2\n\t=>freq= {1: 1, 2: 1} adding  2 to cnt\nr= 2 freq= {1: 2, 2: 1} dist= 2\n\t=>freq= {1: 2, 2: 1} adding  3 to cnt\nr= 3 freq= {1: 2, 2: 2} dist= 2\n\t=>freq= {1: 2, 2: 2} adding  4 to cnt\nr= 4 freq= {1: 2, 2: 2, 3: 1} dist= 3\n\t=>freq= {1: 2, 2: 2, 3: 1} adding  5 to cnt\nr= 5 freq= {1: 3, 2: 2, 3: 1} dist= 3\n\t=>freq= {1: 3, 2: 2, 3: 1} adding  6 to cnt\nr= 6 freq= {1: 3, 2: 3, 3: 1} dist= 3\n\t=>freq= {1: 3, 2: 3, 3: 1} adding  7 to cnt\nr= 7 freq= {1: 3, 2: 3, 3: 1, 4: 1} dist= 4\n\tfreq[ 1 ]-=1\n\tmove l  to l= 1 , dist= 4\n\tfreq[ 2 ]-=1\n\tmove l  to l= 2 , dist= 4\n\tfreq[ 1 ]-=1\n\tmove l  to l= 3 , dist= 4\n\tfreq[ 2 ]-=1\n\tmove l  to l= 4 , dist= 4\n\tfreq[ 3 ]-=1\n\tmove l  to l= 5 , dist= 3\n\t=>freq= {1: 1, 2: 1, 4: 1} adding  3 to cnt\nr= 8 freq= {1: 1, 2: 1, 4: 1, 8: 1} dist= 4\n\tfreq[ 1 ]-=1\n\tmove l  to l= 6 , dist= 3\n\t=>freq= {2: 1, 4: 1, 8: 1} adding  3 to cnt\nr= 9 freq= {2: 2, 4: 1, 8: 1} dist= 3\n\t=>freq= {2: 2, 4: 1, 8: 1} adding  4 to cnt\ncnt= 38\n--------\nProceed goodLessEqualK(nums, k) with k= 2\nr= 0 freq= {1: 1} dist= 1\n\t=>freq= {1: 1} adding  1 to cnt\nr= 1 freq= {1: 1, 2: 1} dist= 2\n\t=>freq= {1: 1, 2: 1} adding  2 to cnt\nr= 2 freq= {1: 2, 2: 1} dist= 2\n\t=>freq= {1: 2, 2: 1} adding  3 to cnt\nr= 3 freq= {1: 2, 2: 2} dist= 2\n\t=>freq= {1: 2, 2: 2} adding  4 to cnt\nr= 4 freq= {1: 2, 2: 2, 3: 1} dist= 3\n\tfreq[ 1 ]-=1\n\tmove l  to l= 1 , dist= 3\n\tfreq[ 2 ]-=1\n\tmove l  to l= 2 , dist= 3\n\tfreq[ 1 ]-=1\n\tmove l  to l= 3 , dist= 2\n\t=>freq= {2: 1, 3: 1} adding  2 to cnt\nr= 5 freq= {2: 1, 3: 1, 1: 1} dist= 3\n\tfreq[ 2 ]-=1\n\tmove l  to l= 4 , dist= 2\n\t=>freq= {3: 1, 1: 1} adding  2 to cnt\nr= 6 freq= {3: 1, 1: 1, 2: 1} dist= 3\n\tfreq[ 3 ]-=1\n\tmove l  to l= 5 , dist= 2\n\t=>freq= {1: 1, 2: 1} adding  2 to cnt\nr= 7 freq= {1: 1, 2: 1, 4: 1} dist= 3\n\tfreq[ 1 ]-=1\n\tmove l  to l= 6 , dist= 2\n\t=>freq= {2: 1, 4: 1} adding  2 to cnt\nr= 8 freq= {2: 1, 4: 1, 8: 1} dist= 3\n\tfreq[ 2 ]-=1\n\tmove l  to l= 7 , dist= 2\n\t=>freq= {4: 1, 8: 1} adding  2 to cnt\nr= 9 freq= {4: 1, 8: 1, 2: 1} dist= 3\n\tfreq[ 4 ]-=1\n\tmove l  to l= 8 , dist= 2\n\t=>freq= {8: 1, 2: 1} adding  2 to cnt\ncnt= 22\n=> ans=38-22=16\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(|freq|)$$ where $|freq|\\leq n$\n# Code ||C++ 23ms Beats 99.34%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int n;\n    int goodLessEqualK(vector<int>& nums, int k){\n        int distinct=0;\n        int freq[20001]={0};//array is much faster than unordered_map\n        int cnt=0;\n        for(int l=0, r=0; r<n; r++){\n            int x=nums[r];\n            distinct+=(++freq[x]==1);\n            while(distinct>k){\n                int y=nums[l];\n                distinct-=(--freq[y]==0);\n                l++;\n            }\n            cnt+=(r-l+1);//nums[l..r] has k distinct numbers, with len=r-l+1\n        }\n        return cnt;\n    }\n\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        n=nums.size();\n        return (k==1)?goodLessEqualK(nums, 1):goodLessEqualK(nums, k)-goodLessEqualK(nums, k-1);\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Python code written in the film\n```\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        """\n        count subarrays with at most K distinct elements. it makes problem much easier!\n        goodLessEqualK(nums, k)-goodLessEqualK(nums, k-1)\n\n        """\n        def goodLessEqualK(nums, k):\n            dist=0\n            freq=[0]*20001\n            cnt=0\n            l=0\n            n=len(nums)\n            for r in range(n):\n                x=nums[r]\n                freq[x]+=1\n                if freq[x]==1: dist+=1\n                while dist>k:\n                    y=nums[l]\n                    freq[y]-=1\n                    if freq[y]==0: dist-=1\n                    l+=1\n                cnt+=(r-l+1)\n            return cnt\n        \n        if k==1: return goodLessEqualK(nums, k)\n        else: return goodLessEqualK(nums, k)-goodLessEqualK(nums, k-1)\n        \n```\n# C++ dual version||15ms Beats 99.87%\nDifferent from the 1st one; the nested loop with outer loop moves l; & the inner loop moves r.\n```\n    //dual version\n    int goodLessEqualK2(vector<int>& nums, int k){\n        int distinct=0;\n        short freq[20001]={0};// 16-bit int is enough\n        int cnt=0;\n        for(int l=0, r=0; l<n; l++){\n            while (distinct<=k && r<n){\n                int x=nums[r++];\n                distinct+=(++freq[x]==1);\n            }\n            cnt+=(r-l);\n            if (distinct>k){\n                int y=nums[l];\n                distinct-=(--freq[y]==0);\n                cnt--;//1 too many\n            } \n        }\n        return cnt;\n    }\n```
['Sliding Window', 'C++', 'Python3']