Easy to Understand Solution ✅ | Using 3 Pointer Approach | ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nWe use the sliding window technique to efficiently find all subarrays with exactly k di
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe use the `sliding window technique` to efficiently find all subarrays with exactly k distinct elements.\n\nAs we iterate through the array, we maintain a window represented by three pointers: `right`, `left_far` and `left_near`.\n\n- `left_far:` Tracks the left wall of the largest possible window with k distinct elements.\n- `left_near:` Tracks the left wall of the smallest possible window with k distinct elements.\n\nBy using these three pointers, we effectively maintain the boundaries of the current window and adjust them based on the number of distinct elements within the window.\n\nWhen the number of distinct elements in the window exceeds k, we shrink the window from the left by moving `left_near` to the right until we have exactly `k` distinct elements (`left_far` is updated accordingly).\n\nAfter ensuring that the window contains exactly `k` distinct elements, we count the number of subarrays within the valid window.\n\nThe difference between left_near and left_far (plus one) gives us the count of subarrays with exactly` k` distinct elements ending at the current position.\n\n##### Advantages of Two Pointers:\n- Using two pointers (left_far and left_near) simplifies the process of adjusting the window boundaries.\n- It allows us to efficiently track both the smallest and largest possible windows with k distinct elements without the need for nested loops or additional data structures.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization:**\n- Initialize an unordered map `freq` to store the frequency of elements in the current window.\n- Initialize `ans` to count the number of good subarrays.\n- Initialize two pointers `left_far` and `left_near` to track the left wall of the window with `k` distinct elements.\n2. **Sliding Window Technique:**\n- Iterate through the array using the `right` pointer.\n- Update the frequency of the current element `nums[right]` in the `freq` map.\n3. **Shrink the Window from the Left:**\n- If the number of distinct elements in the window exceeds `k`, shrink the window from the left to find `left_far`.\n- While the size of the `freq` map is greater than `k`:\n    - Decrement the frequency of the element at `nums[left_near]`.\n    - If the frequency becomes zero, remove the element from the `freq` map.\n    - Move the `left_near` pointer to the right.\n    - Update `left_far` to `left_near` (the smallest window with `k` distinct elements).\n4. **Adjust left_near:**\n- If the window has exactly `k` distinct elements and there are extra occurrences of an element, shrink the window from the left to find `left_near`.\n- While the size of the `freq` map is equal to `k` and the frequency of the element at `nums[left_near]` is greater than `1`:\n    - Decrement the frequency of the element at `nums[left_near]`.\n    - Move the `left_near` pointer to the right.\n5. **Count Good Subarrays:**\n- If the window has exactly `k` distinct elements, update `ans` by adding the count of subarrays within the valid window (`left_near - left_far + 1`).\n6. **Return the Result:**\n- After processing all elements, return the final `ans`, which represents the count of good subarrays with exactly `k` distinct elements.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(n)`, where `n` is the length of the input array nums\n\nThis is because we traverse the array only once using the sliding window technique.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(n)` due to the usage of the unordered map `freq`, which can store at most `n` elements\n\n# Code\n```\nclass Solution {\npublic:\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        unordered_map<int, int> freq;\n        int ans = 0;\n        int left_far = 0, left_near = 0;\n        // left_far => left wall of the largest possible window with k distinct elements\n        // left_near => left wall of the smallest possible window with k distinct elements\n\n        for(int right = 0; right < nums.size(); right++){\n            freq[nums[right]]++;\n\n            // shrink the window from the left if number of distinct elements exceeds k to get left_far\n            while(freq.size() > k){\n                freq[nums[left_near]]--;\n                if(freq[nums[left_near]] == 0){\n                    freq.erase(nums[left_near]);\n                }\n                left_near++;\n                left_far = left_near;\n            }\n\n            // shrink the window from the left if there are extra occurrences of an element to get left_near\n            while(freq.size() == k && freq[nums[left_near]]>1){\n                freq[nums[left_near]]--;\n                left_near++;\n            }\n\n            if(freq.size() == k){\n                ans += left_near - left_far + 1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Sliding Window', 'C++']