subarraysWithKDistinct

 avatar
unknown
c_cpp
a year ago
791 B
4
Indexable
class Solution {
public:

    int subarraysWithAtmostK(vector<int>& nums, int k) {
            map<int,int> numFrequency;
            int count = 0;
            int i = 0 , j = 0, n = nums.size();
            while( j < n )
            {
                numFrequency[nums[j]]++;

                while( i <= j &&  numFrequency.size() > k )
                {
                    numFrequency[nums[i]]--;
                    if( numFrequency[nums[i]] == 0 ) numFrequency.erase(nums[i]);
                    i++;
                }

                count += j-i+1;
                j++;
            }

            return count;
        }

    int subarraysWithKDistinct(vector<int>& nums, int k) {
        
        return subarraysWithAtmostK(nums,k) - subarraysWithAtmostK(nums,k-1) ;


    }
};
Editor is loading...
Leave a Comment