Skip to content

3859. Count Subarrays With K Distinct Integers

Description

You are given an integer array nums and two integers k and m.

Return an integer denoting the count of subarrays of nums such that:

  • The subarray contains exactly k distinct integers.
  • Within the subarray, each distinct integer appears at least m times.

 

Example 1:

Input: nums = [1,2,1,2,2], k = 2, m = 2

Output: 2

Explanation:

The possible subarrays with k = 2 distinct integers, each appearing at least m = 2 times are:

Subarray Distinct
numbers		 Frequency
[1, 2, 1, 2] {1, 2} → 2 {1: 2, 2: 2}
[1, 2, 1, 2, 2] {1, 2} → 2 {1: 2, 2: 3}

Thus, the answer is 2.

Example 2:

Input: nums = [3,1,2,4], k = 2, m = 1

Output: 3

Explanation:

The possible subarrays with k = 2 distinct integers, each appearing at least m = 1 times are:

Subarray Distinct
numbers		 Frequency
[3, 1] {3, 1} → 2 {3: 1, 1: 1}
[1, 2] {1, 2} → 2 {1: 1, 2: 1}
[2, 4] {2, 4} → 2 {2: 1, 4: 1}

Thus, the answer is 3.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k, m <= nums.length

Solutions

Solution 1

Thinking

A subarray must contain exactly \(k\) distinct values, each appearing at least \(m\) times. \(n \le 10^5\) forbids enumerating intervals.

Exactly \(k\) kinds equals at least \(k\) minus at least \(k+1\), together with a window constraint that at least \(k\) values have frequency \(m\).

Two pointers track distinct count and how many values have reached \(m\). Once both \(\textit{lim}\) kinds and \(t \ge k\) hold, move the left end. Every start before that left end is valid.

\(f(k)-f(k+1)\) is the exact-\(k\) count.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def countSubarrays(self, nums: list[int], k: int, m: int) -> int:
        def f(lim: int) -> int:
            cnt = Counter()
            t = 0
            ans = l = 0
            for x in nums:
                cnt[x] += 1
                if cnt[x] == m:
                    t += 1
                while len(cnt) >= lim and t >= k:
                    y = nums[l]
                    cnt[y] -= 1
                    if cnt[y] == m - 1:
                        t -= 1
                    if cnt[y] == 0:
                        cnt.pop(y)
                    l += 1
                ans += l
            return ans

        return f(k) - f(k + 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    private int[] nums;
    private int k;
    private int m;

    public long countSubarrays(int[] nums, int k, int m) {
        this.nums = nums;
        this.k = k;
        this.m = m;
        return f(k) - f(k + 1);
    }

    private long f(int lim) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long ans = 0;
        int l = 0;
        int t = 0;

        for (int x : nums) {
            if (cnt.merge(x, 1, Integer::sum) == m) {
                t++;
            }

            while (cnt.size() >= lim && t >= k) {
                int y = nums[l++];
                int cur = cnt.merge(y, -1, Integer::sum);
                if (cur == m - 1) {
                    --t;
                }
                if (cur == 0) {
                    cnt.remove(y);
                }
            }

            ans += l;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k, int m) {
        auto f = [&](int lim) -> long long {
            unordered_map<int, int> cnt;
            long long ans = 0;
            int l = 0;
            int t = 0;

            for (int x : nums) {
                if (++cnt[x] == m) {
                    ++t;
                }

                while (cnt.size() >= lim && t >= k) {
                    int y = nums[l++];
                    if (--cnt[y] == m - 1) {
                        --t;
                    }
                    if (cnt[y] == 0) {
                        cnt.erase(y);
                    }
                }

                ans += l;
            }

            return ans;
        };

        return f(k) - f(k + 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func countSubarrays(nums []int, k int, m int) int64 {
    f := func(lim int) int64 {
        cnt := make(map[int]int)
        var ans int64
        l := 0
        t := 0

        for _, x := range nums {
            cnt[x]++
            if cnt[x] == m {
                t++
            }

            for len(cnt) >= lim && t >= k {
                y := nums[l]
                l++
                cnt[y]--
                if cnt[y] == m-1 {
                    t--
                }
                if cnt[y] == 0 {
                    delete(cnt, y)
                }
            }

            ans += int64(l)
        }

        return ans
    }

    return f(k) - f(k+1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function countSubarrays(nums: number[], k: number, m: number): number {
    const f = (lim: number): number => {
        const cnt = new Map<number, number>();
        let ans = 0;
        let l = 0;
        let t = 0;

        for (const x of nums) {
            cnt.set(x, (cnt.get(x) ?? 0) + 1);
            if (cnt.get(x) === m) {
                t++;
            }

            while (cnt.size >= lim && t >= k) {
                const y = nums[l++];
                cnt.set(y, cnt.get(y)! - 1);

                if (cnt.get(y) === m - 1) {
                    t--;
                }

                if (cnt.get(y) === 0) {
                    cnt.delete(y);
                }
            }

            ans += l;
        }

        return ans;
    };

    return f(k) - f(k + 1);
}

Comments