Simplified algorithm explained with visual example🔥 | C++ ✔| Java ✔|
Please Upvote if u like it \uD83D\uDE0A\uD83D\uDE3F\n\n\n---\n\n# Example\nLet\'s take the following example\n\nInput: nums = [1,2,1,2,3], k = 2\nOutput: 7\n\n\
Please Upvote if u like it \uD83D\uDE0A\uD83D\uDE3F\n\n\n---\n\n# Example\nLet\'s take the following example\n```\nInput: nums = [1,2,1,2,3], k = 2\nOutput: 7\n\n```\n## let\'s try to solve it \n\n```\nstep 1\n```\n![Screenshot (3428).png](https://assets.leetcode.com/users/images/d4056ce0-f0b7-4746-8e7a-a7907b1a7ba4_1711767854.2710075.png)\n```\nstep 2\n```\n![Screenshot (3429).png](https://assets.leetcode.com/users/images/dce8d19f-6a6c-43b4-bef3-7ca7e796baa0_1711767885.1905174.png)\n```\nstep 3\n```\n![Screenshot (3430).png](https://assets.leetcode.com/users/images/14fc764c-aa32-44da-87ff-8b5f00dda681_1711767904.2452812.png)\n```\nstep4\n```\n![Screenshot (3433).png](https://assets.leetcode.com/users/images/3e25b391-bab0-473d-8c5b-0609fd7f2bca_1711767924.469314.png)\n\n# Now Idea ?\uD83E\uDD14 (Actual Idea)\n![Screenshot (3445).png](https://assets.leetcode.com/users/images/bc72cc27-8a8b-41a1-933e-38b89db767e3_1711771595.9466925.png)\n\n![Screenshot (3444)idea.png](https://assets.leetcode.com/users/images/7ced03d6-7507-4b41-8191-05b7cd63e457_1711767979.0176315.png)\n\n\n\n# Finding number of subarrays with atmost k unique elements (here  k=2) \n\n```\nStep 1\n```\n![Screenshot (3434).png](https://assets.leetcode.com/users/images/b6292cf9-a121-48ce-9dfb-dbf6c42497b7_1711768057.7202573.png)\n```\nStep 2\n```\n![Screenshot (3435).png](https://assets.leetcode.com/users/images/4560c872-caa8-4a43-8d37-54b5c9f4e581_1711768075.0835717.png)\n```\nStep 3\n```\n![Screenshot (3436).png](https://assets.leetcode.com/users/images/22e02b8e-7a43-4fed-8fab-9166965bd1d8_1711768090.8973205.png)\n```\nStep 4\n```\n![Screenshot (3437).png](https://assets.leetcode.com/users/images/4f7fd039-48a8-4d84-b4e8-feecb778010d_1711768103.252895.png)\n\n```\nStep 5 (correction - left index = 1 , not 0)\n```\n![Screenshot (3440).png](https://assets.leetcode.com/users/images/16909ed0-f7ae-40bd-a592-e629d55ca029_1711768153.147926.png)\n```\nStep 6\n```\n![Screenshot (3442).png](https://assets.leetcode.com/users/images/664cca58-1920-4607-bbab-e6401b4ef9f1_1711768225.092187.png)\n```\nStep 7\n```\n![Screenshot (3443).png](https://assets.leetcode.com/users/images/d175460a-024d-4340-8a5c-e64f239aa3cd_1711768262.9856195.png)\n\n \n\n### Now in similar way we have to calculate  Finding number of subarrays with atmost (k-1) unique elements (which is 5 in this case )\n### so 12 - 5 = 7 (that is the answer)\n\n---\n\n\n# Algorithm\n1. **Overall Approach**:\n   - The solution utilizes a sliding window technique to count the number of subarrays with exactly `k` distinct integers.\n\n2. **Counting Subarrays with `k` Distinct Integers**:\n   - The `subarraysWithKDistinct` function computes the difference between the count of subarrays with at most `k` distinct integers and the count of subarrays with at most `k-1` distinct integers.\n\n3. **Counting Subarrays with At Most `k` Distinct Integers**:\n   - The `subarray_with_atmost_k` helper function calculates the count of subarrays with at most `k` distinct integers.\n   - It initializes a sliding window with `left` and `right` pointers.\n   - It maintains a hashmap `map` to track the frequency of integers within the window.\n   - The `right` pointer moves to the right, updating the frequency of the current element in `map`.\n   - If the count of distinct integers exceeds `k`, the `left` pointer is adjusted to shrink the window until the count becomes at most `k`.\n   - The size of each valid subarray ending at the current position (`right`) is added to the answer.\n\n4. **Returning the Result**:\n   - After computing the count of subarrays with exactly `k` distinct integers, the result is returned.\n\n\n---\n\n\n# Code in C++\n```\nclass Solution {\npublic:\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        int sub_with_max_element_k = subarray_with_atmost_k(nums,k);\n        int reduced_sub_with_max_k = subarray_with_atmost_k(nums,k-1);\n        return (sub_with_max_element_k - reduced_sub_with_max_k);\n    }\n    int subarray_with_atmost_k(vector<int>& nums,int k){\n        unordered_map<int,int> map;\n        int left = 0 , right = 0,ans = 0;\n        while(right<nums.size()){\n            map[nums[right]]++;\n            while(map.size()>k){\n                map[nums[left]]--;\n                if(map[nums[left]]==0)map.erase(nums[left]);\n                left++;\n            }\n            ans += right-left+1; // basically the size of subarray;\n            right++;\n        }\n        return ans;\n    }\n};\n```\n\n---\n\n\n# code in java\n```\nclass Solution {\n    public int subarraysWithKDistinct(int[] nums, int k) {\n        int subWithMaxK = subarrayWithAtMostK(nums, k);\n        int reducedSubWithMaxK = subarrayWithAtMostK(nums, k - 1);\n        return subWithMaxK - reducedSubWithMaxK;\n    }\n    \n    public int subarrayWithAtMostK(int[] nums, int k) {\n        HashMap<Integer, Integer> map = new HashMap<>();\n        int left = 0, right = 0, ans = 0;\n        \n        while (right < nums.length) {\n            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);\n            \n            while (map.size() > k) {\n                map.put(nums[left], map.get(nums[left]) - 1);\n                if (map.get(nums[left]) == 0) {\n                    map.remove(nums[left]);\n                }\n                left++;\n            }\n            \n            ans += right - left + 1; // Size of subarray\n            right++;\n        }\n        \n        return ans;\n    }\n}\n```
['Array', 'Hash Table', 'Sliding Window', 'Counting', 'C++', 'Java']