#992
Subarrays with K Different Integers
Hard atMost(k) − atMost(k−1)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count subarrays that contain exactly k distinct integers.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count subarrays with exactly k distinct numbers.
Why this works: same trick: exactly k = atMost(k) - atMost(k-1).
Example: [1, 2, 1, 2, 3], k = 2
atMost(2) = 12, atMost(1) = 5answer 7
✦Hints open one at a time
Exactly k = at most k − at most (k − 1).
Counting "at most k distinct" is a standard variable window with a count map.
↗Approach
atMost(k): expand right, track counts and number of distinct values; while distinct > k, shrink. Add r - left + 1 for each r. Answer = atMost(k) − atMost(k − 1). Values are at most n, so an int array works as the map.
</>Solution (Java)
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
int[] count = new int[nums.length + 1];
int left = 0, distinct = 0, total = 0;
for (int r = 0; r < nums.length; r++) {
if (count[nums[r]]++ == 0) distinct++;
while (distinct > k) {
if (--count[nums[left++]] == 0) distinct--;
}
total += r - left + 1;
}
return total;
}
}!Common mistake
Trying to count exactly-k windows directly with one window — you miss subarrays that start in the middle of a run.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Sliding Window
🎬 Episode 10: video coming soon