Problem Statement

Given an array nums of positive integers, call a (contiguous, not necessarily distinct) subarray of nums good if the number of different integers in that subarray is exactly k.

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

Return the number of good subarrays of nums.

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].

Note:

1. 1 <= nums.length <= 20000
2. 1 <= nums[i] <= nums.length
3. 1 <= k <= nums.length

Problem Link

Subarrays with K Different Integers - LeetCode

Reference Video

https://www.youtube.com/watch?v=shsYUyF7pEs

Code

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        
        return kMostDistinct(nums,k) - kMostDistinct(nums,k-1);
    }
    
    int kMostDistinct(vector<int> &nums, int k)
    {
        unordered_map<int,int> m;
        
        int i = 0;
        int n = nums.size();
        int res = 0;
        
        for(int j=0;j<n;j++)
        {
            if(m[nums[j]]==0)
                k--;
            
            m[nums[j]]++;
            
            while(k<0)
            {
                m[nums[i]]--;
                if(m[nums[i]]==0)
                    k++;
                i++;
            }
            
            res+=(j-i+1);
            
            
        }
        return res;
        
    }
};

Why the number of contiguous subarrays is equal to the sum of lengths. Why does that work?

We want to find all valid contiguous subarrays that[1,2,1,2,3] would produce with at most K different integers.You will notice though -- that when we say at most K different integers -- we only use K to help us find the valid windows (ex. [1,2,1,2] and [2,3])Once we have those valid windows though, we don't really care what K is (that's because at most means 0 to K unique Integers, which literally means any contiguous subarray now). So, stop thinking about how K will affect the subarrays to understand the summation of lengths.