Stretches With Exactly K Kinds
HardSliding Window
Problem
A seed bank stores packets in a row, and nums[i] is the plant species of packet i. A botanist wants contiguous stretches of packets that contain exactly `k` different species.
Return the number of non-empty subarrays of nums with exactly k distinct values.
Example 1
- Input:
- nums = [4, 4, 2, 4, 3], k = 2
- Output:
- 6
[4,2], [4,4,2], [2,4], [4,2,4], [4,4,2,4] and [4,3].
Example 2
- Input:
- nums = [1, 2, 3], k = 3
- Output:
- 1
Constraints
- 1 ≤ nums.length ≤ 2·10^4
- 1 ≤ nums[i] ≤ nums.length
- 1 ≤ k ≤ nums.length
Hint
Show the first hint
For a fixed right end, the valid left edges for 'exactly k' form a range, not a prefix. That makes one window awkward.
Walkthrough
How to approach it
01Clarify before coding
- Distinct values, not distinct positions? Yes, count different species.
- What if k exceeds the number of distinct values in the array? The answer is 0.
- How big can the answer get? Up to about n²/2 = 2·10^8, fine in 64 bits.
02Brute force
For each start, extend right with a set and count ends where the set size is exactly k; stop once it exceeds k.
Cost: O(n²) time, 2·10^8 steps for n = 2·10^4: too slow for an interview answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.