Sliding Window Method || Beginner Friendly || Explanation || Efficient Method ||
Intuition\nTo find the number of subarrays with exactly \( k \) distinct integers, we want to effectively count the valid subarrays while managing the distinct 
# Intuition\nTo find the number of subarrays with exactly \\( k \\) distinct integers, we want to effectively count the valid subarrays while managing the distinct integers within a certain range. \n\n# Traditional Sliding Window Method\nA basic sliding window approach would involve:\n1. Expanding the window by moving the right pointer to include more elements.\n2. Checking the distinct count whenever we expand the window.\n3. If the count exceeds \\( k \\), moving the left pointer to shrink the window until we have at most \\( k \\) distinct integers.\n4. Counting valid subarrays for each valid configuration.\n\nHowever, simply counting valid subarrays for \\( k \\) distinct integers directly can lead to inefficiencies because:\n- It may involve nested loops, resulting in \\( O(n^2) \\) time complexity when checking all subarrays.\n\n# Optimized Approach\n1. **Two Helper Functions**: We utilize the helper function `less_k` to count the number of subarrays with at most \\( k \\) distinct integers. The main function then uses:\n   \n**subarraysWithKDistinct(k) = less_k(k) - less_k(k - 1)**\n\n   This avoids counting duplicates and simplifies our counting process.\n\n2. **Counting Distinct Integers**: By using a hash map to track the counts of distinct integers in the current window, we efficiently manage the size of our window without recalculating distinct counts from scratch.\n\n# Why the Traditional Method Might Not Work\nThe traditional sliding window method may struggle with:\n- **Efficiency**: Continuously recalculating distinct integers as the window expands or contracts can lead to increased computation time.\n- **Count Overlap**: Counting all configurations directly without separating by distinct counts can lead to overcounting or missing valid subarrays.\n\nBy using the optimized approach, we ensure:\n- **Linear Time Complexity**: Each element is processed a limited number of times, allowing us to maintain efficiency.\n- **Clear Counting Logic**: By counting at most \\( k \\) distinct integers and deriving the exact count for \\( k \\) distinct integers, we avoid redundancy.\n\n# Complexity\n- Time complexity:\n  - The optimized approach runs in \\( O(n) \\) time, processing each element effectively.\n\n- Space complexity:\n  - The space complexity remains \\( O(n) \\) due to the hash map used for counting distinct integers.\n\n## Summary\nIn summary, while the traditional sliding window approach can be a good start, it is not always efficient for counting distinct elements in subarrays. The optimized method using helper functions allows for a more efficient solution that scales better with larger inputs.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int less_k(vector<int>& nums, int k){\n        int n = nums.size(), l = 0, r = 0, count = 0;\n        unordered_map<int, int> seen;\n\n        while(r < n){\n            seen[nums[r]]++;\n\n            while(seen.size() > k){\n                seen[nums[l]]--;\n                if(seen[nums[l]] == 0)\n                    seen.erase(nums[l]);\n                l++;\n            }\n\n            count += r - l + 1;\n            r++;\n        }\n\n        return count;\n    }\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        return less_k(nums, k) - less_k(nums, k-1);\n    }\n};\n```\n```Java []\nclass Solution {\n    private int less_k(int[] nums, int k) {\n        int n = nums.length, l = 0, r = 0, count = 0;\n        HashMap<Integer, Integer> seen = new HashMap<>();\n\n        while (r < n) {\n            seen.put(nums[r], seen.getOrDefault(nums[r], 0) + 1);\n\n            while (seen.size() > k) {\n                seen.put(nums[l], seen.get(nums[l]) - 1);\n                if (seen.get(nums[l]) == 0)\n                    seen.remove(nums[l]);\n                l++;\n            }\n\n            count += r - l + 1;\n            r++;\n        }\n\n        return count;\n    }\n\n    public int subarraysWithKDistinct(int[] nums, int k) {\n        return less_k(nums, k) - less_k(nums, k - 1);\n    }\n}\n```\n``` python3 []\nclass Solution:\n    def less_k(self, nums, k):\n        n = len(nums)\n        l, r, count = 0, 0, 0\n        seen = defaultdict(int)\n\n        while r < n:\n            seen[nums[r]] += 1\n\n            while len(seen) > k:\n                seen[nums[l]] -= 1\n                if seen[nums[l]] == 0:\n                    del seen[nums[l]]\n                l += 1\n\n            count += r - l + 1\n            r += 1\n\n        return count\n    \n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        return self.less_k(nums, k) - self.less_k(nums, k-1)\n```
['C++', 'Java', 'Python3']