Subarrays with K Different Integers

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
private:
    int atMost(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int,int> freq;
        int left = 0, count = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            ++freq[nums[right]];
            while ((int)freq.size() > k) {
                if (--freq[nums[left]] == 0) freq.erase(nums[left]);
                ++left;
            }
            count += right - left + 1; // # of subarrays ending at `right` with ≤ k distinct
        }
        return count;
    }
};

func subarraysWithKDistinct(nums []int, k int) int {
    return atMostKDistinct(nums, k) - atMostKDistinct(nums, k-1)
}

func atMostKDistinct(nums []int, k int) int {
    if k < 0 {
        return 0
    }
    freq := map[int]int{}
    left, count := 0, 0
    for right := 0; right < len(nums); right++ {
        freq[nums[right]]++
        for len(freq) > k {
            freq[nums[left]]--
            if freq[nums[left]] == 0 {
                delete(freq, nums[left])
            }
            left++
        }
        count += right - left + 1 // # of subarrays ending at right with ≤ k distinct
    }
    return count
}

from collections import defaultdict
from typing import List

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        return self._at_most(nums, k) - self._at_most(nums, k - 1)

    def _at_most(self, nums: List[int], k: int) -> int:
        if k < 0:
            return 0
        freq: dict = defaultdict(int)
        left = count = 0
        for right, x in enumerate(nums):
            freq[x] += 1
            while len(freq) > k:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            count += right - left + 1
        return count

function subarraysWithKDistinct(nums, k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

function atMost(nums, k) {
    if (k < 0) return 0;
    const freq = new Map();
    let left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        while (freq.size > k) {
            const v = freq.get(nums[left]) - 1;
            if (v === 0) freq.delete(nums[left]);
            else freq.set(nums[left], v);
            left++;
        }
        count += right - left + 1; // # of subarrays ending at right with ≤ k distinct
    }
    return count;
}

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        if (k < 0) return 0;
        Map<Integer, Integer> freq = new HashMap<>();
        int left = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            freq.merge(nums[right], 1, Integer::sum);
            while (freq.size() > k) {
                int v = freq.get(nums[left]) - 1;
                if (v == 0) freq.remove(nums[left]);
                else freq.put(nums[left], v);
                left++;
            }
            count += right - left + 1; // # of subarrays ending at right with <= k distinct
        }
        return count;
    }
}

function subarraysWithKDistinct(nums: number[], k: number): number {
    return atMost(nums, k) - atMost(nums, k - 1);
}

function atMost(nums: number[], k: number): number {
    if (k < 0) return 0;
    const freq = new Map<number, number>();
    let left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        while (freq.size > k) {
            const v = freq.get(nums[left])! - 1;
            if (v === 0) freq.delete(nums[left]);
            else freq.set(nums[left], v);
            left++;
        }
        count += right - left + 1; // # of subarrays ending at right with <= k distinct
    }
    return count;
}