Subarrays with K Different Integers
Problem
Given an integer array nums and an integer k, return the number of subarrays with exactly k distinct integers.
- 1 ≤ nums.length ≤ 2 * 10⁴
- 1 ≤ nums[i], k ≤ nums.length
Example
nums = [1,2,1,2,3], k = 27The subarrays with exactly 2 distinct integers are: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], and [1,2,1,2]. The algorithm uses a helper function to count subarrays with at most k distinct integers and subtracts the count of subarrays with at most k-1 distinct integers to get the exact count. For k=2, atMost(2) counts all subarrays with up to 2 distinct integers, and atMost(1) counts those with up to 1 distinct integer. Their difference yields the count of subarrays with exactly 2 distinct integers.
Approach
Straightforward Solution
A brute-force approach would enumerate all subarrays and count distinct integers in each, resulting in O(n^2) or worse time complexity, which is too slow for large inputs.
Core Observation
The number of subarrays with exactly k distinct integers equals the number of subarrays with at most k distinct integers minus the number of subarrays with at most k-1 distinct integers. This transforms the problem into counting subarrays with at most k distinct integers, which can be efficiently done using a sliding window.
Path to Optimal
PreviewThe key insight is to use the sliding window technique to count subarrays with at most k distinct integers in O(n) time…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a helper function atMost(k) that uses a sliding window to count subarrays with at most k distinct integers. The main function returns atMost(k) - atMost(k - 1)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each element is visited at most twice: once when expanding the right pointer and once when moving the left pointer. The frequency map operations are O(1) on average, resulting in an overall linear time complexity.
Space
O(n)
The frequency map stores counts of elements currently in the sliding window. In the worst case, it can hold all distinct elements in nums, which is O(n). This auxiliary space is necessary to track distinct counts efficiently.
Pattern Spotlight
Sliding Window (Counting Subarrays with Constraints)
When counting subarrays with an exact number of distinct elements, transform the problem into the difference of counts of subarrays with at most k and at most k-1 distinct elements, enabling efficient linear-time sliding window solutions.
Solution
| 1 | class Solution: |
| 2 | def subarraysWithKDistinct(self, nums, k): |
| 3 | |
| 4 | def atMost(k): |
| 5 | count = {} |
| 6 | left = 0 |
| 7 | res = 0 |
| 8 | |
| 9 | for right, n in enumerate(nums): |
| 10 | |
| 11 | count[n] = count.get(n, 0) + 1 |
| 12 | |
| 13 | while len(count) > k: |
| 14 | count[nums[left]] -= 1 |
| 15 | |
| 16 | if count[nums[left]] == 0: |
| 17 | del count[nums[left]] |
| 18 | |
| 19 | left += 1 |
| 20 | |
| 21 | res += right - left + 1 |
| 22 | |
| 23 | return res |
| 24 | |
| 25 | return atMost(k) - atMost(k - 1) |
Step-by-Step Solution
Count Subarrays with At Most K Distinct Integers Using Sliding Window
| 4 | def atMost(k): |
| 5 | count = {} |
| 6 | left = 0 |
| 7 | res = 0 |
| 9 | for right, n in enumerate(nums): |
| 11 | count[n] = count.get(n, 0) + 1 |
| 13 | while len(count) > k: |
| 14 | count[nums[left]] -= 1 |
| 16 | if count[nums[left]] == 0: |
| 17 | del count[nums[left]] |
| 19 | left += 1 |
| 21 | res += right - left + 1 |
| 23 | return res |
Objective
To count the number of subarrays with at most k distinct integers by expanding and contracting a sliding window.
Key Insight
The sliding window maintains a frequency map of elements within the window and adjusts its left boundary to ensure the window contains at most k distinct integers. For each right pointer position, the number of valid subarrays ending at that position is the window size (right - left + 1). Summing these counts yields the total number of subarrays with at most k distinct integers. This approach avoids enumerating all subarrays explicitly, achieving linear time complexity.
Interview Quick-Check
Core Logic
The sliding window expands the right pointer and contracts the left pointer to maintain at most k distinct integers, counting valid subarrays by window size at each step.
State & Boundaries
The while loop condition ensures the window never exceeds k distinct integers by removing elements from the left until the constraint is satisfied.
Common Pitfalls & Bugs
Forgetting to delete keys from the frequency map when their count drops to zero can cause incorrect distinct counts and infinite loops.
Complexity
Each element is added and removed from the frequency map at most once, ensuring O(n) time complexity.
Calculate Exact Count by Subtracting Counts of At Most K and K-1
To compute the number of subarrays with exactly k distinct integers by subtracting counts of subarrays with at most k-1 distinct integers from those with at most k.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
return atMost(k) - atMost(k - 1)Return the difference between counts of subarrays with at most k and at most k-1 distinct integers.
This subtraction isolates the count of subarrays with exactly k distinct integers, leveraging the helper function's results and the inclusion-exclusion principle.
while len(count) > k:While the window contains more than k distinct integers, shrink it from the left.
This loop enforces the constraint of at most k distinct integers by moving the left pointer forward and updating frequencies accordingly.
del count[nums[left]]Delete the element from the frequency map so the distinct count remains accurate.
Removing elements whose count becomes zero ensures the dictionary size accurately represents the number of distinct elements in the window, which is required for the len(count) constraint check.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does subtracting the count of subarrays with at most k-1 distinct integers from the count of subarrays with at most k distinct integers yield the count of subarrays with exactly k distinct integers?
See the answer with Pro.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Subarrays with K Different Integers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subarrays with K Different Integers drill