Count Subarrays With K Distinct Integers solution and explanation
3 more videos on this problem
LeetCode Problem 3859 | Count Subarrays With K Distinct IntegersRepovive TV · 44:00 · 712 views
3859. Count Subarrays With K Distinct Integers (Leetcode Hard)Programming Live with Larry · 35:18 · 481 views
weekly contest 491 | leetcode 3856 | leetcode 3857 | leetcode 3858 | leetcode 3859 | DSACode With Vick · 38:53 · 440 views
Master the Sliding Window! 🚀 LeetCode 3859: Count Subarrays With K Distinct IntegersCodingHelp · 13:53 · 54 views
The problem
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
kdistinct integers. - Within the subarray, each distinct integer appears at least
mtimes.
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 <= 1051 <= nums[i] <= 1051 <= k, m <= nums.length
Approach overview
Problem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays contain exactly k distinct integers. The challenge is efficiently tracking unique elements while expanding and shrinking subarray boundaries.
Approach 1: Brute Force with Set Tracking (O(n²) time, O(n) space)
Start every subarray from index i. Extend the right boundary one element at a time and track unique numbers using a set or hash map. Each extension updates the number of distinct elements. When the count becomes exactly k, increment the result. Stop extending once the count exceeds k. This approach checks all possible starting positions, which leads to quadratic time complexity. Useful for understanding the problem but too slow for large inputs.
Approach 2: Sliding Window with At-Most Trick (O(n) time, O(n) space)
The key observation: counting subarrays with exactly k distinct elements can be reduced to counting subarrays with at most k distinct elements. The formula is:
exactly(k) = atMost(k) - atMost(k-1)
Implement a sliding window using two pointers and a frequency hash table. Expand the right pointer and update counts. When distinct elements exceed k, shrink the left pointer until the window becomes valid again. For each valid position, add the window length contribution (right - left + 1). This counts all subarrays ending at right that satisfy the constraint.
The helper function atMost(k) runs once for k and once for k-1. Each element enters and leaves the window at most once, giving linear complexity. This technique is a classic pattern combining sliding window with frequency counting on an array.
Approach 3: Sliding Window with Two Left Pointers (O(n) time, O(n) space)
Another optimized strategy maintains two sliding windows simultaneously: one tracking at most k distinct elements and another tracking at most k-1. Both windows expand with the same right pointer but shrink independently. The difference between their valid starting indices directly gives the number of subarrays ending at the current index with exactly k distinct elements. This avoids calling a helper function twice but follows the same underlying logic.
Recommended for interviews: The sliding window atMost(k) - atMost(k-1) technique is the expected solution. It demonstrates strong understanding of window invariants, frequency maps, and counting strategies. Brute force shows baseline reasoning, but the linear sliding window solution is what interviewers want to see for hard array problems.
Solution
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)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;
}
}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);
}
};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);
}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)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set | O(n²) | O(n) | Conceptual understanding or very small arrays |
| Sliding Window (atMost(k) - atMost(k-1)) | O(n) | O(n) | General optimal solution for unsorted arrays |
| Dual Sliding Windows | O(n) | O(n) | Alternative linear method without calling helper twice |
Frequently asked questions
Is Count Subarrays With K Distinct Integers easy or hard?
The problem is typically labeled Hard because the direct brute-force idea is simple but inefficient. The real challenge is recognizing the atMost(K) − atMost(K−1) transformation and implementing a correct sliding window with frequency tracking.
Count Subarrays With K Distinct Integers Python/Java solution
Most implementations use the sliding window atMost technique. A helper function counts subarrays with at most K distinct values using a hash map and two pointers. The final answer is computed as atMost(K) minus atMost(K-1), and the same logic translates directly to Python, Java, C++, Go, or TypeScript.
How to solve Count Subarrays With K Distinct Integers in O(n)?
Use a sliding window with a frequency hash map to count subarrays with at most K distinct elements. Then compute the result using exactly(k) = atMost(k) − atMost(k−1). Each window expansion and contraction updates the distinct count while maintaining valid boundaries, resulting in linear traversal.
What is the best approach for Count Subarrays With K Distinct Integers?
The most efficient approach uses a sliding window with the formula exactly(k) = atMost(k) − atMost(k−1). A hash map tracks element frequencies while two pointers maintain a valid window. This method processes each element at most twice, giving O(n) time complexity and O(n) space.
Is Count Subarrays With K Distinct Integers asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests sliding window patterns, hash map usage, and subarray counting logic. Interviewers often expect the optimized O(n) sliding window solution.
What data structure is used in Count Subarrays With K Distinct Integers?
A hash table (or hash map) stores element frequencies inside a sliding window. Two pointers track the window boundaries, while the map quickly updates counts as elements enter or leave the window.
What is the time complexity of Count Subarrays With K Distinct Integers?
The optimal sliding window solution runs in O(n) time because each element is added and removed from the window at most once. The hash map operations are constant on average. Space complexity is O(n) in the worst case if all elements in the array are distinct.