Sliding window (Hashmap/Two pointer) with details - Python
This problem with involve knowledge from hashmap, two pointers, and sliding window.\n\nIt is hard to compute directly the subarray with exactly k different inte
This problem with involve knowledge from hashmap, two pointers, and sliding window.\n\nIt is hard to compute directly the subarray with **exactly** `k` different integers, but it will be easier to count the number of subarrays with **at most** `k` different integers. \n\nWe will introduce a new subarray to help us:\n* **Nice subarray** is an array where the number of different integers in that array is **at most** `k`\n\nAfter we get the number of nice subarrays, we can get the number of good arrays using the difference of nice subarrays for `k` and `k-1`.\ne.g. # of subarrays with exactly 3 different integers = # of subarrays with at most 3 different integers - # of subarrays with at most 2 different integers.\n\n# **Here is the idea:**\n1. We need two pointers as the left and right part of our sliding window.\n2. If the right pointer is pointing to a value that exists in the hashmap, this means that we can expand the width of our sliding window. \n3. Then we need to check if the hashmap is containing too many elements (exceed k). If so, we need to shrink our sliding window by deleting the first element inside it, which is `nums[left]`.\n4. Add the number of nice subarrays we get in the above steps.\n\n**Let\'s start with a step-by-step example:**\n```\nnums = [1, 3, 1, 4]\nk = 2\noutput (good subarrays) = 4\n```\n\n* **Step 1:** \n\t* left = 0, right = 0\n\t* hashmap = {1 : 1}\n\t* Nice subarrays = 1\n`[1]`\n\n* **Step 2:**\n\t* left = 0, right = 1\n\t* hashmap = {1 : 1, 3 : 1}\n\t* Nice subarrays = 2 + 1 = 3\n`[1], [3], [1,3]`\n\n* **Step 3:**\n\t* left = 0, right = 2\n\t* hashmap = {1 : 2, 3 : 1}\n\t* Nice subarrays = 3 + 3 = 6\n`[1], [3], [1,3], [1], [1,3,1], [3,1]`\n\n* **Step 4:**\n\t* left = 0, right = 3\n\t* hashmap = {1: 2, 3 : 1, 4 : 1}\n-> Note that The length of hashmap exceeds `k`! So we need to delete the first element in our sliding window\n\n* **Step 5:**\n\t* left = 1, right = 3\n\t* hashmap = {1 : 1, 3 : 1, 4 : 1}\n\tThe length of hashmap still exceed `k`, so we will shrink our sliding window one more times\n\t\n* **Step 6:**\n\t* left = 2, right = 3\n\t* hashmap = {1 : 1, 4: 1}\n\t* Nice subarrays = 2 + 6 = 8\n\t`[1], [3], [1,3], [1], [1,3,1], [3,1], [1,4], [4]`\n\t\nWe can see that for `k = 2`, the number of nice subarrays will be 8. If `k = 1`, we can easily see that the number of it will be 4. So the number of good subarrays (output) will be 8 - 4 = 4.\n\n```\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        \n        def atMostKDistinct(nums, k):\n            niceSubarray = 0\n            hashmap = {}\n            left, right = 0, 0\n            \n            while right < len(nums):\n                if nums[right] in hashmap:\n                    hashmap[nums[right]] += 1\n                else:\n                    hashmap[nums[right]] = 1\n            \n                while len(hashmap) > k:\n                    hashmap[nums[left]] -= 1\n                    if hashmap[nums[left]] == 0:\n                        del hashmap[nums[left]]\n                    left += 1\n                \n                niceSubarray += right - left + 1\n                right += 1\n                \n            return niceSubarray\n        \n        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1)\n```
['Two Pointers', 'Sliding Window', 'Python']