Subarrays with K Different Integers [Hard] — Sliding Window Subtract

Problem Statement

Given array nums and integer k, return the number of good subarrays (subarrays with exactly k different integers).

Input: nums=[1,2,1,2,3], k=2 → Output: 7

Intuition

exactly(k) = atMost(k) - atMost(k-1). atMost(k) counts subarrays with at most k distinct using a shrinkable sliding window.

Solutions

Python

from collections import defaultdict

def subarraysWithKDistinct(nums: list[int], k: int) -> int:
    def at_most(k):
        count = defaultdict(int)
        left = res = 0
        for right, val in enumerate(nums):
            count[val] += 1
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            res += right - left + 1
        return res
    return at_most(k) - at_most(k-1)

C++

int subarraysWithKDistinct(vector<int>& nums, int k) {
    auto atMost=[&](int k){
        unordered_map<int,int> cnt; int l=0,res=0;
        for(int r=0;r<nums.size();r++){
            cnt[nums[r]]++;
            while(cnt.size()>k){if(--cnt[nums[l]]==0)cnt.erase(nums[l]);l++;}
            res+=r-l+1;
        }
        return res;};
    return atMost(k)-atMost(k-1);
}

Complexity

Time: O(n)
Space: O(k)