visual walkthrough
Subarrays with K Different Integers
The hardest application of the at-most trick.
The idea
Subarrays with at most m different numbers form a nice sliding-window problem: shrinking the window can only reduce the number of distinct values. "Exactly k" is then atMost(k) minus atMost(k − 1).
A map of counts tells the window when a value has fully left.
Complexity
| approach | time | space |
|---|---|---|
| Try every subarray | O(n²) | O(n) |
| atMost(k) − atMost(k−1) | O(n) | O(k) |