# 992-subarrays-with-k-different-integers


Try it on <a href='https://leetcode.com/problems/992-subarrays-with-k-different-integers'>leetcode</a>

## Description
<div class="description">
<div><p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good subarrays</strong> of </em><code>nums</code>.</p>

<p>A <strong>good array</strong> is an array where the number of different integers in that array is exactly <code>k</code>.</p>

<ul>
	<li>For example, <code>[1,2,3,1,2]</code> has <code>3</code> different integers: <code>1</code>, <code>2</code>, and <code>3</code>.</li>
</ul>

<p>A <strong>subarray</strong> is a <strong>contiguous</strong> part of an array.</p>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre><strong>Input:</strong> nums = [1,2,1,2,3], k = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
</pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> nums = [1,2,1,3,4], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= nums.length</code></li>
</ul>
</div>
</div>

## Solution(Python)
```Python
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        return self.subarraysWithAtmostKDistinct(
            nums, k
        ) - self.subarraysWithAtmostKDistinct(nums, k - 1)

    def subarraysWithAtmostKDistinct(self, nums: List[int], k: int) -> int:
        cnt = 0
        n = len(nums)

        # for left in range(n):
        #     hashmap = set()
        #     for right in range(left,n):
        #         hashmap.add(nums[right])
        #         if len(hashmap) > k:
        #             break
        #         cnt +=1
        #
        # Time Complexity : O(n^2)

        left, right = 0, 0
        size = 0
        hashmap = {}
        while right < n:
            if nums[right] not in hashmap:
                hashmap[nums[right]] = 1
            else:
                hashmap[nums[right]] += 1

            if hashmap[nums[right]] == 1:
                size += 1

            while size > k:
                hashmap[nums[left]] -= 1
                if hashmap[nums[left]] == 0:
                    size -= 1
                left += 1

            cnt += right - left + 1
            right += 1

        return cnt
        # Time complexity : O(N)

```