Subarrays with K Different Integers
Count the contiguous subarrays that contain exactly k distinct values. A sliding window problem whose trick is computing "exactly k" as "at most k" minus "at most k - 1". Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums and an integer k. Count how many contiguous, non-empty subarrays of nums contain exactly k different values.
Subarrays are counted by position: two subarrays with the same contents at different positions count separately.
Example 1
- Input
- nums = [4, 4, 7, 4, 8], k = 3
- Output
- 3
The subarrays with values {4, 7, 8} are [4, 4, 7, 4, 8], [4, 7, 4, 8] and [7, 4, 8].
Example 2
- Input
- nums = [2, 2, 2, 2], k = 1
- Output
- 10
Every one of the 4 + 3 + 2 + 1 = 10 subarrays has exactly one distinct value.
Example 3
- Input
- nums = [1, 2, 3, 4, 5], k = 5
- Output
- 1
Only the whole array contains all five values.
Constraints
- 1 ≤ nums.length ≤ 2 · 10⁴
- 1 ≤ nums[i] ≤ nums.length
- 1 ≤ k ≤ nums.length
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Subarrays with K Different Integers in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Subarrays with K Different Integers
Pattern: Sliding window: exactly k = at most k - at most (k - 1)
A sliding window is natural for "subarrays with a condition on distinct values", but "exactly k" is awkward: when the window has k distinct values, extending it might keep it at k or push it past, and shrinking it might keep it at k or drop below. There is no single place to stop.
"At most k" is easy, though. For each right end r, shrink the left end until the window has at most k distinct values. Then every start from left to r works, adding r - left + 1 subarrays. Since every subarray with exactly k distinct values is one with at most k but not at most k - 1:
exactly(k) = atMost(k) - atMost(k - 1).
Approach 1: Every start, extend right
For each start index, walk right adding values to a set. Count while the set has exactly k values and stop once it exceeds k. Simple, but long stretches with few distinct values make it quadratic.
Time O(n²) · Space O(n)
Approach 2: Two "at most" sliding windows
Write atMost(m): keep a count map for the window [left, r]. For each r, add nums[r]; while the map has more than m keys, remove nums[left] (deleting keys that reach 0) and move left right. Add r - left + 1 to the total.
The answer is atMost(k) - atMost(k - 1). Each pointer moves at most n times per call.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Every start, extend right | O(n²) | O(n) |
| Two "at most" sliding windows | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Subarrays with K Different Integers solution in Python
def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
def at_most(m):
counts = {}
left = total = 0
for right, x in enumerate(nums):
counts[x] = counts.get(x, 0) + 1
while len(counts) > m:
y = nums[left]
counts[y] -= 1
if counts[y] == 0:
del counts[y]
left += 1
total += right - left + 1
return total
return at_most(k) - at_most(k - 1)Subarrays with K Different Integers solution in JavaScript
function subarraysWithKDistinct(nums, k) {
const atMost = (m) => {
const counts = new Map();
let left = 0;
let total = 0;
for (let right = 0; right < nums.length; right++) {
counts.set(nums[right], (counts.get(nums[right]) ?? 0) + 1);
while (counts.size > m) {
const y = nums[left++];
const c = counts.get(y) - 1;
if (c === 0) counts.delete(y);
else counts.set(y, c);
}
total += right - left + 1;
}
return total;
};
return atMost(k) - atMost(k - 1);
}Common mistakes
- Trying to count "exactly k" with a single window and missing subarrays whose left end could move further while staying at k.
- Forgetting to delete a key when its count reaches zero, so the number of distinct values never drops.
- Adding 1 per valid window instead of `r - left + 1`, which counts windows instead of subarrays.
- Overflowing a 32-bit counter. The number of subarrays can be about n² / 2.
What interviewers look for
Say why "exactly k" resists a direct window, then introduce the subtraction trick. This is the insight interviewers are waiting for, and it reappears in "count subarrays with exactly k odd numbers" and "binary subarrays with sum".
When you write atMost, explain the r - left + 1 term: every subarray ending at r that starts at or after left also satisfies the condition, because removing elements can't add distinct values.
Follow-up questions
Can you do it in a single pass?
Yes. Keep two left pointers: `far`, the smallest start with at most k distinct values, and `near`, the smallest start with at most k - 1. For each right end, the subarrays with exactly k distinct values are the starts from `far` to `near - 1`, so add `near - far`. It is the same idea fused into one loop.
What if the values were large or negative?
Nothing changes except the count structure: use a hash map instead of an array indexed by value. The algorithm only relies on counting occurrences.
How would you find the longest subarray with at most k distinct values?
Use the same at-most window and track the maximum of `r - left + 1` instead of summing it. That is the "longest substring with at most k distinct characters" problem.
Companies that ask Subarrays with K Different Integers
Subarrays with K Different Integers is tagged by 116 companies in our interview dataset. The score shows how often it comes up at each company.
- Vtex100%
- Tokyo Electron100%
- Mcafee100%
- Dxc Technology98%
- Bd91%
- JPMorgan Chase91%
- Zapposcom89%
- Boston Scientific87%
- Hashedin87%
- ASML85%
- Springworks Therapeutics83%
- Wepay83%
- Thermo Fisher Scientific81%
- Doximity81%
- Panasonic81%
- Cabaletta Bio79%
- Bungie77%
- Forto77%
- Anthropic77%
- Elevance Health75%
- Bairesdev75%
- Servicetitan75%
- Udaan75%
- Twist Bioscience74%
and 92 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required