Count ‘Em Like a Pro: Subarrays, Not Sheep
IntuitionThe problem requires us to count the number of subarrays that contain exactly k distinct integers. A direct approach using brute force would involve ch
# Intuition
The problem requires us to count the number of subarrays that contain exactly `k` distinct integers. A direct approach using brute force would involve checking all possible subarrays, which is inefficient. Instead, we can leverage the **Sliding Window + Two-Pointer** technique to count the number of subarrays with at most `k` distinct integers and subtract the count of subarrays with at most `k-1` distinct integers. This efficiently gives the count of subarrays with exactly `k` distinct integers.

---

# Approach
1. **Define a Helper Function `findsubarrays(goal)`**:  
   - This function calculates the number of subarrays that contain **at most** `goal` distinct integers.  
   - We maintain a **sliding window** using two pointers (`l` and `r`).  
   - A dictionary `uniquenums` keeps track of the frequency of elements in the current window.  
   - Expand the right pointer `r`, adding elements to the window.  
   - If the number of distinct elements exceeds `goal`, shrink the window from the left (`l`) until we have at most `goal` distinct numbers again.  
   - The count of valid subarrays ending at `r` is `r - l + 1`, which is added to `ans`.  

2. **Compute the Final Answer**:  
   - The number of subarrays with exactly `k` distinct integers is found by subtracting:  
     \[
    `findsubarrays(k)` - `findsubarrays(k-1)`
     \]
   - This works because `findsubarrays(k)` gives all subarrays with at most `k` distinct integers, and `findsubarrays(k-1)` removes those that contain at most `k-1` distinct integers.

---

# Complexity
- Time complexity:
  - The function iterates through `nums` while maintaining a dynamic window, ensuring that each element is processed at most twice (once when expanding, once when contracting).  
  - Thus, the time complexity is **\(O(n)\)**.

- Space complexity:
  - We use a dictionary (`uniquenums`) to store at most `k` elements, leading to a worst-case space complexity of **\(O(k)\)**.



# Code
```python3 []
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def findsubarrays(goal):
            ans=0
            uniquenums={}
            l=0
            for r in range(len(nums)):
                if nums[r] in uniquenums:
                    uniquenums[nums[r]]+=1
                else:
                    uniquenums[nums[r]]=1
                if len(uniquenums)>goal:
                    while(uniquenums[nums[l]]!=1):
                        uniquenums[nums[l]]-=1
                        l+=1
                    uniquenums.pop(nums[l])
                    l+=1
                ans+=r-l+1
            return ans
        return findsubarrays(k)-findsubarrays(k-1)
                

```
![DALL·E 2025-01-08 22.24.48 - A highly detailed and humorous digital illustration of two animated pointer characters (one red, one blue) riding a conveyor belt filled with numbers,.webp](https://assets.leetcode.com/users/images/1c0ee4ee-3582-459e-be51-74f18fa2eac4_1736355334.5355651.webp)


['Two Pointers', 'Sliding Window', 'Python3']