C++/Java/Python | 🚀 ✅ Fully Explained | ✅Sliding Window | ✅ Hash Map | ✅Easy to Understand
Intuition\nThe given code solution computes the number of subarrays in a given array \'nums\' that have exactly \'k\' distinct elements. It first calculates the
# Intuition\nThe given code solution computes the number of subarrays in a given array \'nums\' that have exactly \'k\' distinct elements. It first calculates the count of subarrays with at most \'k\' distinct elements using the subArray function. Then it calculates the count of subarrays with at most \'k-1\' distinct elements using the same subArray function and subtracts it from the previous count. This gives the required count of subarrays with exactly \'k\' distinct elements.\n\n# Approach\nThe code solution uses the sliding window technique to calculate the count of subarrays with at most \'k\' distinct elements. It initializes an unordered map to store the count of distinct elements in the current subarray. It also initializes \'count\', \'start\', and \'end\' to 0. The \'end\' pointer moves through the array while the count of distinct elements in the current subarray is less than or equal to \'k\'. If it becomes greater than \'k\', then the \'start\' pointer moves forward, and the count of the element at the \'start\' index is decreased until the count of distinct elements becomes less than or equal to \'k\' again. At each step, the count of subarrays is updated by adding the length of the current subarray (i.e., \'end-start+1\') to the \'count\'. Finally, the \'count\' is returned.\n\nThe function subarraysWithKDistinct calls the subArray function twice and subtracts the count of subarrays with at most \'k-1\' distinct elements from the count of subarrays with at most \'k\' distinct elements. This gives the required count of subarrays with exactly \'k\' distinct elements.\n\n# Complexity\n- Time complexity: The time complexity of the subArray function is O(n), where \'n\' is the length of the input array \'nums\'. This is because each element in the array is visited at most twice (once by the \'end\' pointer and once by the \'start\' pointer), and the map operations are constant time on average. The time complexity of the subarraysWithKDistinct function is also O(n) because it calls the subArray function twice.\n\n- Space complexity: The space complexity of the subArray function is O(k), where \'k\' is the maximum number of distinct elements that can be present in a subarray. This is because the map can store at most \'k\' key-value pairs. The space complexity of the subarraysWithKDistinct function is also O(k) because it calls the subArray function twice.\n\n# C++\n```\nclass Solution {\npublic:\n    int subArray(vector<int>& nums, int k) {\n        int n = nums.size();\n        unordered_map<int, int> map;  // create an unordered map to store the count of each number in the current subarray\n        int count = 0, start = 0, end = 0;  // initialize variables for count of valid subarrays, start and end index of subarray\n        while (end < n) {  // loop through the array from the start to end index\n            map[nums[end]]++;  // add the current element to the map and increment its count\n            while (map.size() > k) {  // if the number of distinct elements in the map is greater than k, move the start index and remove elements from the map\n                map[nums[start]]--;  // decrement the count of the element at the start index\n                if (map[nums[start]] == 0) {  // if the count of the element at the start index becomes 0, remove it from the map\n                    map.erase(nums[start]);\n                }\n                start++;  // increment the start index to move the window\n            }\n            count += end - start + 1;  // add the count of valid subarrays for the current subarray to the total count\n            end++;  // increment the end index to move the window\n        }\n        return count;  // return the total count of valid subarrays\n    }\n    int subarraysWithKDistinct(vector<int>& nums, int k) {\n        // return the count of subarrays with exactly k distinct elements minus the count of subarrays with less than k distinct elements\n        return subArray(nums, k) - subArray(nums, k - 1);\n    }\n};\n\n```\n# JAVA\n```\nclass Solution {\n    public int subArray(List<Integer> nums, int k) {\n        int n = nums.size();\n        Map<Integer, Integer> map = new HashMap<>(); // create a map to store the count of each number in the current subarray\n        int count = 0, start = 0, end = 0; // initialize variables for count of valid subarrays, start and end index of subarray\n        while (end < n) { // loop through the array from the start to end index\n            map.put(nums.get(end), map.getOrDefault(nums.get(end), 0) + 1); // add the current element to the map and increment its count\n            while (map.size() > k) { // if the number of distinct elements in the map is greater than k, move the start index and remove elements from the map\n                map.put(nums.get(start), map.get(nums.get(start)) - 1); // decrement the count of the element at the start index\n                if (map.get(nums.get(start)) == 0) { // if the count of the element at the start index becomes 0, remove it from the map\n                    map.remove(nums.get(start));\n                }\n                start++; // increment the start index to move the window\n            }\n            count += end - start + 1; // add the count of valid subarrays for the current subarray to the total count\n            end++; // increment the end index to move the window\n        }\n        return count; // return the total count of valid subarrays\n    }\n    \n    public int subarraysWithKDistinct(int[] nums, int k) {\n        List<Integer> list = new ArrayList<>(); // convert the input array to a list\n        for (int num : nums) {\n            list.add(num);\n        }\n        // return the count of subarrays with exactly k distinct elements minus the count of subarrays with less than k distinct elements\n        return subArray(list, k) - subArray(list, k - 1);\n    }\n}\n\n```\n# Python\n```\nclass Solution(object):\n    def subArray(self, nums, k):\n        n = len(nums)\n        map = {}\n        count = 0\n        start = 0\n        end = 0\n        while end < n:\n            map[nums[end]] = map.get(nums[end], 0) + 1\n            while len(map) > k:\n                map[nums[start]] -= 1\n                if map[nums[start]] == 0:\n                    del map[nums[start]]\n                start += 1\n            count += end - start + 1\n            end += 1\n        return count\n    \n    def subarraysWithKDistinct(self, nums, k):\n        return self.subArray(nums, k) - self.subArray(nums, k - 1)\n\n\n```\n\n# Thank You\n
['Hash Table', 'Sliding Window', 'C++']