💥 [EASY] SOLUTION WITH INTUITION AND EXPLANATION
Intuition\nThe problem asks us to find the number of subarrays with exactly k distinct integers. One of the first thoughts is to use the sliding window techniqu
# Intuition\nThe problem asks us to find the number of subarrays with exactly `k` distinct integers. One of the first thoughts is to use the sliding window technique. The sliding window allows us to efficiently count subarrays that meet the condition by shrinking and expanding the window size dynamically.\n\n# Approach\nWe can solve the problem by using a helper function that counts the subarrays with at most `k` distinct integers. The key idea here is that the number of subarrays with exactly `k` distinct integers can be calculated as:\n\n* ```subarrays with exactly k distinct integers = subarrays with at most k distinct integers - subarrays with at most (k - 1) distinct integers```\n\n### Steps:\n1. **Sliding Window**: We maintain a sliding window with two pointers (`l` for left and `r` for right). The window should include up to `k` distinct integers. We use a frequency map to track the count of integers within the window.\n2. **Shrinking Window**: When the size of the window exceeds `k` distinct integers, we increment the left pointer `l` until the number of distinct integers in the window is again `k`.\n3. **Counting Subarrays**: For each valid window, we add the number of subarrays that end at the current index `r` to the count. This is computed as `r - l + 1`.\n4. **Final Answer**: To get the result, we compute the difference between the number of subarrays with at most `k` distinct integers and the number of subarrays with at most `k-1` distinct integers.\n\n# Complexity\n- **Time complexity**:  \n  The time complexity is $$O(n)$$, where `n` is the length of the input array `arr`. This is because each element is processed at most twice (once when expanding the window, and once when contracting it).\n  \n- **Space complexity**:  \n  The space complexity is $$O(k)$$, due to the space required for the frequency map which stores up to `k` distinct elements.\n\n# Code\n```java\nclass Solution {\n    private int helper(int[] arr, int k){\n        int count = 0;\n        Map<Integer, Integer> map = new HashMap<>();\n\n        int l = 0, r = 0;\n\n        while(r < arr.length){\n            map.put(arr[r], map.getOrDefault(arr[r], 0) + 1);\n\n            while(map.size() > k && l <= r){\n                int leftInt = arr[l];\n                map.put(leftInt, map.get(leftInt) - 1);\n                if(map.get(leftInt) == 0) map.remove(leftInt);\n                l++;\n            }\n\n            count += r - l + 1;\n\n            r++;\n        }\n        return count;\n    }\n\n    public int subarraysWithKDistinct(int[] arr, int k) {\n        return helper(arr, k) - helper(arr, k - 1);\n    }\n}\n```
['Array', 'Hash Table', 'Recursion', 'Sliding Window', 'Counting', 'Java']