class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return SubarraysWithAtMostKDistinct(A, K) - SubarraysWithAtMostKDistinct(A, K - 1);
    }
private:
    int SubarraysWithAtMostKDistinct(const vector<int>& A, int K) {
        if (K <= 0) return 0;
        int distinct_subarrs = 0;
        int curr_distinct = 0;
        int lo = 0;
        int hi = 0;

        vector<int> count(A.size() + 1);

        while (hi < A.size()) {
            while (hi < A.size() && curr_distinct <= K) {
                if (count[A[hi]] == 0) ++curr_distinct;
                ++count[A[hi]];
                ++hi;
                if (curr_distinct <= K) distinct_subarrs += (hi - lo);
            }

            if (curr_distinct <= K) break;

            while (curr_distinct > K) {
                --count[A[lo]];
                if (count[A[lo]] == 0) --curr_distinct;
                ++lo;
            }

            distinct_subarrs += (hi - lo);
        }

        return distinct_subarrs;
    }
};