Subarrays with K Different Integers — Problem & Solution
Subarrays with K Different Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Subarrays with K Different Integers is a hard coding problem on arrays, hash table and two pointers, asked in Amazon, Google, Microsoft and Morgan Stanley interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Two Pointers, Counting, Sliding Window
- Asked at: Amazon, Google, Microsoft, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Count the subarrays of nums containing exactly k distinct integers.
Example 1
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2].
Example 2
Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: [1,2,1,3], [2,1,3] and [1,3,4].
Example 3
Input: nums = [5,5,5], k = 1
Output: 6
Explanation: Every subarray of a constant array has one distinct value.
Constraints
1 <= nums.length <= 200001 <= nums[i], k <= nums.length
Hints for Subarrays with K Different Integers
Hint 1
A window with exactly
kdistinct values is not monotone, so a single sliding window cannot count it directly.Hint 2
A window with at most
kdistinct values is monotone — shrinking it never raises the distinct count.Hint 3
exactly(k) = atMost(k) − atMost(k − 1).
How to solve Subarrays with K Different Integers
The 'exactly k' predicate is not monotone in the window's left edge, which breaks the usual two-pointer count. The 'at most k' predicate is, so count that twice and subtract.
Approach
- Write
atMost(limit): sliderover the array, tally the values, and shrink fromlwhile more thanlimitdistinct values are in the window. - Each
rcontributesr - l + 1subarrays — every window ending atrand starting at or afterl. - Return
atMost(k) - atMost(k - 1).
Why it works
For a fixed right end, the set of valid left ends under 'at most limit' is a contiguous suffix, so r - l + 1 counts them all in constant time and l never moves backwards. Every subarray with at most k distinct values either has exactly k or at most k-1, and the two cases are disjoint, so the subtraction isolates the exact count.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Trying to maintain 'exactly k' with one window undercounts — the valid left ends form a range, not a suffix.
atMost(0)must be 0, not a crash, whenk = 1.- Decrementing the tally without dropping zero entries leaves the distinct count wrong.
Reference solution
Python
from typing import List
def subarraysWithKDistinct(nums: List[int], k: int) -> int:
def at_most(limit: int) -> int:
if limit < 0:
return 0
cnt = {}
distinct = 0
l = 0
res = 0
for r, v in enumerate(nums):
cnt[v] = cnt.get(v, 0) + 1
if cnt[v] == 1:
distinct += 1
while distinct > limit:
u = nums[l]
cnt[u] -= 1
if cnt[u] == 0:
distinct -= 1
l += 1
res += r - l + 1
return res
return at_most(k) - at_most(k - 1)Java
private static int atMostKDistinct(int[] nums, int limit) {
if (limit < 0) return 0;
int[] cnt = new int[nums.length + 1];
int distinct = 0, l = 0, res = 0;
for (int r = 0; r < nums.length; r++) {
if (cnt[nums[r]]++ == 0) distinct++;
while (distinct > limit) {
if (--cnt[nums[l]] == 0) distinct--;
l++;
}
res += r - l + 1;
}
return res;
}
public static int subarraysWithKDistinct(int[] nums, int k) {
return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}C++
static int atMostKDistinct(vector<int>& nums, int limit) {
if (limit < 0) return 0;
vector<int> cnt(nums.size() + 1, 0);
int distinct = 0, l = 0, res = 0;
for (int r = 0; r < (int) nums.size(); r++) {
if (cnt[nums[r]]++ == 0) distinct++;
while (distinct > limit) {
if (--cnt[nums[l]] == 0) distinct--;
l++;
}
res += r - l + 1;
}
return res;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}JavaScript
var subarraysWithKDistinct = function(nums, k) {
var atMost = function(limit) {
if (limit < 0) return 0;
var cnt = {};
var distinct = 0, l = 0, res = 0;
for (var r = 0; r < nums.length; r++) {
var v = nums[r];
cnt[v] = (cnt[v] || 0) + 1;
if (cnt[v] === 1) distinct++;
while (distinct > limit) {
var u = nums[l];
cnt[u]--;
if (cnt[u] === 0) distinct--;
l++;
}
res += r - l + 1;
}
return res;
};
return atMost(k) - atMost(k - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets