Frequency Map + Window
Track counts of what is inside the window to answer "at most k distinct" style questions.
Frequency Map Window: At most 2 distinct
Grow right to index 0. 1 enters, a new key, so the map now has 1 distinct. Within 2, so the window is valid.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(k)