The challenge
Count nonempty contiguous subarrays containing exactly k distinct values.
Integer array; k ≥ 0. Empty input or k = 0 returns 0.
Example
[1, 2, 1, 2, 3], k = 2 → 7.
Use the walkthrough below to inspect the input and each state change.
See Exactly K distinct, step by step
Expand, shrink, and inspect the window state.
5 elements · zero-based indicesk = 2
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 32
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: [1,2,1,2,3] · k = 2
Current window is empty.
Put it into code
Exactly k is not preserved by removing a left element. Count at most k and at most k − 1 independently, then subtract.
Indices are zero-based. C++ uses C++17 or later.
def exactly_k_distinct(nums, k):
def at_most(budget):
if budget < 0:
return 0
count = {}
left = total = 0
for right, value in enumerate(nums):
count[value] = count.get(value, 0) + 1
while len(count) > budget:
old = nums[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
total += right - left + 1
return total
return at_most(k) - at_most(k - 1)#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
long long exactly_k_distinct(const vector<int>& nums, int k) {
auto at_most = [&](int budget) -> long long {
if (budget < 0) return 0;
unordered_map<int, int> count;
int left = 0;
long long total = 0;
for (int r = 0; r < (int)nums.size(); ++r) {
++count[nums[r]];
while ((int)count.size() > budget) {
int old = nums[left++];
if (--count[old] == 0) count.erase(old);
}
total += r - left + 1;
}
return total;
};
return at_most(k) - at_most(k - 1);
}