Posted on

Description

Submission

class Solution {
public:
    int subarraysWithAtMostKDistinct(vector<int>& A, int K) {
        map<int, int> m;
        int counter = 0;
        int res = 0;
        
        for(int i = 0, j = 0; j < A.size();) {
            if(++m[A[j++]] == 1) counter++;
            
            while(counter > K) {
                if(--m[A[i++]] == 0) counter--;
            }

            res += (j-i);
        }
        
        return res;
    }
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return subarraysWithAtMostKDistinct(A, K) -
            subarraysWithAtMostKDistinct(A, K - 1);
    }

};

Leave a Reply

Your email address will not be published. Required fields are marked *