Subarrays with K Different Integers
MediumatMost(k) minus atMost(k-1), again
Problem
Count subarrays with exactly k distinct integers.
Count windows with at most k distinct minus at most k-1 — the difference has exactly k.
The idea
A window cannot directly enforce 'exactly k distinct', but it handles 'at most k' comfortably with a frequency map. Subtracting the at-most-(k-1) count leaves precisely the subarrays with k distinct values.
The trick
- Two runs of the same helper; do not try to write an exact-k window.
- In atMost, each right edge contributes (right - left + 1) subarrays.
- O(n) per run, so O(n) overall.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — nums=[1,2,1,2,3], k=2 Values: 1, 2, 1, 2, 3.
1atMost(k): window with <=k distinct, counting subarrays2answer = atMost(k) - atMost(k-1)Input
- array
- [1, 2, 1, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 1, 2, 3], k = 2
- Output:
- 7
- Explanation:
- 7 subarrays have exactly 2 distinct values.
Example 2
- Input:
- nums = [1, 2, 1, 3, 4], k = 3
- Output:
- 3
- Explanation:
- 3 subarrays have exactly 3 distinct.
Example 3
- Input:
- nums = [1, 1, 1], k = 1
- Output:
- 6
- Explanation:
- All 6 windows have 1 distinct.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.