Count Distinct Subarray Elements — Problem Statement & Solution Guide
Problem Description
You are provided with an array of integers nums and a target integer k. Your task is to determine the total number of contiguous subarrays that contain exactly k distinct elements. A subarray is defined as a non-empty sequence of elements that are adjacent in the original array. The distinctness is determined by the unique values present within the subarray, regardless of their frequency.
For instance, if the subarray is [1, 2, 2, 3], the distinct elements are {1, 2, 3}, so the count of distinct elements is 3. If k is 3, this subarray contributes 1 to the final count. If k is 2, it does not.
The solution must efficiently handle large input sizes, implying that a brute-force approach checking every possible subarray is not feasible. You are expected to utilize a sliding window technique combined with a frequency map to maintain the count of distinct elements as the window expands and contracts.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Distinct Subarray Elements"
WHY DOES IT MATTER?
The sliding‑window pattern is essential because it turns a combinatorial counting problem into a linear scan, eliminating the need for nested loops. It leverages the fact that the property being tracked (distinct count) changes in a predictable way as the window expands or contracts, allowing constant‑time updates.
OPTIMIZATION CHALLENGE
The core insight is that the number of subarrays ending at a given index can be computed directly from the left boundary of the valid window, avoiding enumeration of all subarrays. This reduces the complexity from quadratic to linear and the space from O(n^2) to O(k).
REAL-WORLD CONNECTION
Think of a streaming data pipeline that must detect bursts of unique user actions within a moving time window. The sliding window efficiently updates the count of distinct users as new events arrive and old events expire, similar to how the algorithm updates the distinct element count as pointers move.
When explaining this to an interviewer, emphasize the monotonicity of the distinct count and the two‑pointer invariant. Show a small example on paper to illustrate how the left pointer moves only when necessary, and how the contribution (right-left+1) accumulates.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem of counting subarrays with exactly k distinct elements can be reduced to a classic sliding‑window counting problem. A naive approach would enumerate all O(n^2) subarrays and count distinct values inside each, leading to O(n^3) time or O(n^2) with hashing, which is infeasible for large arrays. The optimal solution observes that the number of subarrays with exactly k distinct elements equals the number of subarrays with at most k distinct elements minus the number of subarrays with at most k-1 distinct elements. For each bound, a two‑pointer (left/right) window maintains a frequency map of elements inside the window. While expanding the right pointer, we increment the count of the new element; if the window exceeds the allowed distinct count, we shrink from the left until the constraint is satisfied. At each step, the number of valid subarrays ending at the current right index is (right – left + 1). Summing these contributions yields the count of subarrays with at most k distinct elements in linear time.
This sliding‑window paradigm is powerful because it transforms a global counting problem into a local, incremental update that runs in O(n) time and O(k) space. The key insight is that the property “at most k distinct” is monotonic with respect to window expansion: adding an element can only increase the distinct count, never decrease it. This monotonicity guarantees that once the window violates the constraint, moving the left pointer forward will eventually restore it, allowing the algorithm to maintain a single pass over the array.
Interview Questions on This Problem
Q1How would you modify the sliding window approach if the array contains negative numbers and you need to count subarrays with exactly k distinct values?
The sliding window logic remains unchanged because the algorithm only relies on equality of values, not their sign. However, you must use a hash map or dictionary that supports negative keys, such as a standard unordered_map in C++ or a dict in Python. Ensure that the frequency updates correctly handle negative keys and that the distinct count is updated when a key’s count transitions from 0 to 1 or from 1 to 0.
Q2A fintech company asks: can you extend this algorithm to count subarrays where the sum of elements is also within a given range [L,R] while maintaining exactly k distinct elements?
Yes, but the problem becomes more complex. You would need a two‑dimensional sliding window or a combination of two pointers and a prefix sum array. One approach is to maintain two windows: one for the distinct constraint and another for the sum constraint, adjusting both left pointers appropriately. This typically leads to O(n) time if both constraints are monotonic, but careful handling of overlapping windows is required.
Q3During a high‑growth startup interview, you are asked to explain why the time complexity is O(n) and not O(n log n). What justification would you give?
The algorithm processes each element at most twice: once when the right pointer includes it and once when the left pointer excludes it. All operations inside the loop—hash map insert, delete, and lookup—are O(1) on average. Therefore, the total work is linear in the array length, yielding O(n) time. There is no need for sorting or binary search, which would introduce a log n factor.
Examples
Input
nums = [1, 2, 1, 2, 3], k = 2
Output
7
Explanation: Let's enumerate the subarrays with exactly 2 distinct elements: 1. [1, 2] -> {1, 2} 2. [2, 1] -> {1, 2} 3. [1, 2] -> {1, 2} 4. [2, 3] -> {2, 3} 5. [1, 2, 1] -> {1, 2} 6. [2, 1, 2] -> {1, 2} 7. [1, 2, 3] -> {1, 2, 3} (Wait, this has 3 distinct. Let's re-evaluate carefully.) Let's list all subarrays: - Length 1: [1](1), [2](1), [1](1), [2](1), [3](1) -> 0 with k=2 - Length 2: [1,2](2), [2,1](2), [1,2](2), [2,3](2) -> 4 with k=2 - Length 3: [1,2,1](2), [2,1,2](2), [1,2,3](3) -> 2 with k=2 - Length 4: [1,2,1,2](2), [2,1,2,3](3) -> 1 with k=2 - Length 5: [1,2,1,2,3](3) -> 0 with k=2 Total = 4 + 2 + 1 = 7.
Input
nums = [1, 1, 1, 1], k = 1
Output
10
Explanation: All subarrays consist only of the element 1. Thus, every subarray has exactly 1 distinct element. The total number of subarrays in an array of length n is n*(n+1)/2. Here n=4, so total subarrays = 4*5/2 = 10. Since k=1, all 10 subarrays are valid.
Input
nums = [1, 2, 3, 4, 5], k = 3
Output
3
Explanation: We need subarrays with exactly 3 distinct elements. Since all elements are unique, a subarray of length L has L distinct elements. Thus, we need subarrays of length exactly 3. In an array of length 5, the number of subarrays of length 3 is 5 - 3 + 1 = 3. These are: [1,2,3], [2,3,4], [3,4,5]. Each has exactly 3 distinct elements. Total = 3.
Input
nums = [1, 2, 1, 3, 2], k = 4
Output
0
Explanation: The maximum number of distinct elements in any subarray is the total number of distinct elements in the entire array, which is {1, 2, 3} = 3. Since k=4 is greater than the maximum possible distinct count (3), no subarray can have exactly 4 distinct elements. Thus, the answer is 0.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^5
Optimal Approach & Strategy
Use two sliding windows to count subarrays with at most k and at most k-1 distinct elements. Each window runs in O(n) time with a hash map, and the final answer is the difference of the two counts, achieving O(n) time and O(k) space.
Brute Force Approach
Enumerate all O(n^2) subarrays, use a hash set to count distinct elements for each subarray, and increment the answer if the count equals k. This approach runs in O(n^3) time or O(n^2) with hashing, which is too slow for large inputs.
Verified Code Solutions
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var countSubarrays = function(nums, k) {
const atMost = (k) => {
if (k < 0) return 0;
const freq = new Map();
let distinct = 0, left = 0, count = 0;
for (let right = 0; right < nums.length; right++) {
freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
if (freq.get(nums[right]) === 1) distinct++;
while (distinct > k) {
freq.set(nums[left], freq.get(nums[left]) - 1);
if (freq.get(nums[left]) === 0) distinct--;
left++;
}
count += right - left + 1;
}
return count;
};
return atMost(k) - atMost(k - 1);
};class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
auto atMost = [&](int k) {
if (k < 0) return 0;
unordered_map<int, int> freq;
int distinct = 0, left = 0, count = 0;
for (int right = 0; right < nums.size(); ++right) {
if (freq[nums[right]]++ == 0) distinct++;
while (distinct > k) {
if (--freq[nums[left]] == 0) distinct--;
left++;
}
count += right - left + 1;
}
return count;
};
return atMost(k) - atMost(k - 1);
}
};class Solution {
public int countSubarrays(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int k) {
if (k < 0) return 0;
Map<Integer, Integer> freq = new HashMap<>();
int distinct = 0, left = 0, count = 0;
for (int right = 0; right < nums.length; right++) {
freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);
if (freq.get(nums[right]) == 1) distinct++;
while (distinct > k) {
freq.put(nums[left], freq.get(nums[left]) - 1);
if (freq.get(nums[left]) == 0) distinct--;
left++;
}
count += right - left + 1;
}
return count;
}
}class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
def at_most(k: int) -> int:
if k < 0:
return 0
freq = {}
distinct = 0
left = 0
count = 0
for right in range(len(nums)):
freq[nums[right]] = freq.get(nums[right], 0) + 1
if freq[nums[right]] == 1:
distinct += 1
while distinct > k:
freq[nums[left]] -= 1
if freq[nums[left]] == 0:
distinct -= 1
left += 1
count += right - left + 1
return count
return at_most(k) - at_most(k - 1)/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var countSubarrays = function(nums, k) {
const atMost = (k) => {
if (k < 0) return 0;
const freq = new Map();
let distinct = 0, left = 0, count = 0;
for (let right = 0; right < nums.length; right++) {
freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
if (freq.get(nums[right]) === 1) distinct++;
while (distinct > k) {
freq.set(nums[left], freq.get(nums[left]) - 1);
if (freq.get(nums[left]) === 0) distinct--;
left++;
}
count += right - left + 1;
}
return count;
};
return atMost(k) - atMost(k - 1);
};Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.