Code Implementation

from collections import defaultdict

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        def atMostK(nums, k):
            count = defaultdict(int)
            res = left = 0
            for right, num in enumerate(nums):
                if count[num] == 0:
                    k -= 1
                count[num] += 1
                while k < 0:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        k += 1
                    left += 1
                res += right - left + 1
            return res
        return atMostK(nums, k) - atMostK(nums, k-1)
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
private:
    int atMostK(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int left = 0, res = 0;
        for (int right = 0; right < nums.size(); ++right) {
            if (count[nums[right]] == 0) --k;
            ++count[nums[right]];
            while (k < 0) {
                --count[nums[left]];
                if (count[nums[left]] == 0) ++k;
                ++left;
            }
            res += right - left + 1;
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
    private int atMostK(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0, left = 0;
        for (int right = 0; right < nums.length; ++right) {
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
            if (count.get(nums[right]) == 1) k--;
            while (k < 0) {
                count.put(nums[left], count.get(nums[left]) - 1);
                if (count.get(nums[left]) == 0) k++;
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }
}
      

var subarraysWithKDistinct = function(nums, k) {
    function atMostK(nums, k) {
        let count = new Map();
        let res = 0, left = 0;
        for (let right = 0; right < nums.length; ++right) {
            count.set(nums[right], (count.get(nums[right]) || 0) + 1);
            if (count.get(nums[right]) === 1) k--;
            while (k < 0) {
                count.set(nums[left], count.get(nums[left]) - 1);
                if (count.get(nums[left]) === 0) k++;
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }
    return atMostK(nums, k) - atMostK(nums, k - 1);
};
      

Problem Description

Given an integer array nums and an integer k, your task is to find the number of contiguous subarrays in nums that contain exactly k different integers.

Key constraints:

• You must count all subarrays (not just unique ones) that have exactly k distinct integers.
• Elements in nums can be reused in multiple subarrays.
• Each subarray must be contiguous (no skipping elements).
• There is always at least one valid solution if k is within the range of the number of unique elements in nums.

Thought Process

The brute-force way to solve this problem is to consider every possible subarray of nums, count how many distinct numbers it contains, and increment our answer if that count is exactly k.

However, this approach is inefficient for large arrays because checking all subarrays is slow. Instead, we look for ways to optimize. By observing that the problem is about contiguous subarrays and the number of distinct elements, we can use a sliding window technique to efficiently count subarrays with at most k distinct elements.

The main insight is that the number of subarrays with exactly k distinct elements equals the number of subarrays with at most k distinct elements minus the number with at most k-1 distinct elements.

Solution Approach

• Sliding Window for At Most K: Use two pointers (left and right) to maintain a window of elements. As you expand right, keep track of the count of each number in the current window using a hash map (or dictionary).
• Counting Distincts: Each time a new number is added (i.e., its count changes from 0 to 1), decrease k by 1. If k becomes negative, shrink the window from the left until you have at most k distinct numbers again.
• Counting Subarrays: For each valid window, the number of subarrays ending at right is right - left + 1.
• Exactly K Distinct: The answer is atMostK(nums, k) - atMostK(nums, k-1), which counts subarrays with exactly k distinct elements.
• Why Hash Map? The hash map allows us to efficiently update and check the count of each number as the window slides.
• Why Two Calls? atMostK(nums, k) counts all subarrays with up to k distinct elements. Subtracting atMostK(nums, k-1) removes those with fewer than k distinct elements, leaving only those with exactly k.

Example Walkthrough

Let's use nums = [1, 2, 1, 2, 3] and k = 2.

1. First, calculate atMostK(nums, 2):
   • Window [1]: 1 distinct → valid (count: 1)
   • Window [1,2]: 2 distinct → valid (count: 2)
   • Window [1,2,1]: 2 distinct → valid (count: 3)
   • Window [1,2,1,2]: 2 distinct → valid (count: 4)
   • Window [1,2,1,2,3]: 3 distinct → invalid, shrink window
   • After shrinking, count subarrays ending at each position with at most 2 distinct elements.
2. Then, calculate atMostK(nums, 1):
   • Only subarrays with 1 distinct element are counted.
3. Subtract the two results to get the number of subarrays with exactly 2 distinct elements. In this example, the answer is 7.

The solution efficiently counts valid subarrays by expanding and shrinking the window as needed, without checking all possible subarrays individually.

Time and Space Complexity

• Brute-force approach: Time complexity is O(n²) or worse, since you check all subarrays and count unique elements each time.
• Optimized approach (sliding window): Each element is added and removed from the window at most once, so the time complexity is O(n).
• Space complexity: O(k) for the hash map, since at most k unique elements are tracked at any time.
• The optimized approach is much faster for large arrays, making it suitable for competitive programming or interviews.

Summary

This problem can be efficiently solved using a sliding window and hash map to count subarrays with at most k and k-1 distinct elements. The key insight is that the difference between these two counts gives us the number of subarrays with exactly k different integers. This approach is both efficient and elegant, transforming a potentially slow brute-force problem into a linear-time solution.