992. Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

• For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.
 

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

• $1<=nums.length<=2\ast 10^4$
• 1 <= nums[i], k <= nums.length

From: LeetCode
Link: 992. Subarrays with K Different Integers

Solution:

Ideas:

• We convert the problem into:
  Exactly K distinct = AtMost(K) − AtMost(K−1).

• Define a helper function atMostKDistinct():

  • Use sliding window (two pointers).
  • Maintain a freq[] array to count occurrences.
  • Track current number of distinct elements.

• Expand the window with right:

  • Add nums[right] to frequency.
  • If it’s a new number → increase distinct.

• If distinct > k:

  • Shrink from the left.
  • Decrease frequency.
  • If a number count becomes 0 → decrease distinct.

• For each valid window:

  • Number of valid subarrays ending at right is
    right - left + 1.
  • Add this to result.

Code:

static long long atMostKDistinct(const int* nums, int n, int k) {
    if (k < 0) return 0;

    // nums[i] is in [1, n], so we can use a direct frequency array of size n+1.
    int *freq = (int*)calloc((size_t)n + 1, sizeof(int));
    if (!freq) return 0; // out of memory fallback

    int left = 0;
    int distinct = 0;
    long long ans = 0;

    for (int right = 0; right < n; ++right) {
        int x = nums[right];
        if (freq[x] == 0) distinct++;
        freq[x]++;

        while (distinct > k) {
            int y = nums[left++];
            freq[y]--;
            if (freq[y] == 0) distinct--;
        }

        // all subarrays ending at right with start in [left..right] are valid
        ans += (right - left + 1);
    }

    free(freq);
    return ans;
}

int subarraysWithKDistinct(int* nums, int numsSize, int k) {
    // exactly k = atMost(k) - atMost(k-1)
    long long res = atMostKDistinct(nums, numsSize, k) - atMostKDistinct(nums, numsSize, k - 1);
    return (int)res; // result fits in 32-bit for given constraints
}