Best/Easiest Java Solution 🔥
Intuition\nThe problem requires finding the number of subarrays with exactly k distinct elements. To solve this, we can utilize a sliding window approach. By ma
# Intuition\nThe problem requires finding the number of subarrays with exactly k distinct elements. To solve this, we can utilize a sliding window approach. By maintaining two pointers (left and right) to define the current window, we can efficiently count the number of subarrays that satisfy the condition. We expand the window to the right while keeping track of the count of distinct elements within the window. If the count exceeds k, we shrink the window from the left until the count is equal to k again. At each step, we update the count of subarrays that meet the condition.\n\n# Approach\n1. We define a helper method subarrayWithAtMostK to find the number of subarrays with at most k distinct elements. This method will be utilized to find both the total number of subarrays and the number of subarrays with at most (k-1) distinct elements.\n2. We use a HashMap to keep track of the count of each element within the current window.\n3. We initialize two pointers, left and right, to define the current window.\n4. We iterate through the array, expanding the window to the right. At each step, we update the count of distinct elements within the window.\n5. If the count exceeds k, we shrink the window from the left until the count is equal to k again.\n6. At each step, we update the count of subarrays that satisfy the condition by adding the size of the current subarray (right - left + 1) to the answer.\n7. Finally, we return the total count of subarrays satisfying the condition.\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nimport java.util.HashMap;\n\npublic class Solution {\n    // Main method to find the number of subarrays with exactly k distinct elements\n    public int subarraysWithKDistinct(int[] nums, int k) {\n        // Find the number of subarrays with at most k distinct elements\n        int subWithMaxK = subarrayWithAtMostK(nums, k);\n        // Find the number of subarrays with at most (k - 1) distinct elements\n        int reducedSubWithMaxK = subarrayWithAtMostK(nums, k - 1);\n        // The difference between the two gives the number of subarrays with exactly k distinct elements\n        return subWithMaxK - reducedSubWithMaxK;\n    }\n    \n    // Helper method to find the number of subarrays with at most k distinct elements\n    public int subarrayWithAtMostK(int[] nums, int k) {\n        // HashMap to store the count of each element in the current window\n        HashMap<Integer, Integer> map = new HashMap<>();\n        // Pointers to track the current window\n        int left = 0, right = 0;\n        // Variable to store the count of subarrays satisfying the condition\n        int ans = 0;\n        \n        // Expand the window to the right until it reaches the end of the array\n        while (right < nums.length) {\n            // Include the current element in the window and update its count in the map\n            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);\n            \n            // If the number of distinct elements in the window exceeds k, shrink the window from the left\n            while (map.size() > k) {\n                // Decrease the count of the element at the left pointer\n                map.put(nums[left], map.get(nums[left]) - 1);\n                // If the count becomes 0, remove the element from the map\n                if (map.get(nums[left]) == 0) {\n                    map.remove(nums[left]);\n                }\n                // Move the left pointer to the right\n                left++;\n            }\n            \n            // Count the subarrays ending at the current right pointer and add it to the answer\n            // The number of subarrays is equal to the size of the window (right - left + 1)\n            ans += right - left + 1; // Size of subarray\n            // Move the right pointer to the right\n            right++;\n        }\n        \n        // Return the total count of subarrays satisfying the condition\n        return ans;\n    }\n}\n\n```
['Java']