AlgoScope

Frequency Map + Window

Track counts of what is inside the window to answer "at most k distinct" style questions.

Sliding window, pattern, intermediate
The right end moves to index 0 and 1 enters. 1 distinct values inside. That is allowed.active 0-0102112233435462728leftright
The right end moves to index 0 and 1 enters. 1 distinct values inside. That is allowed.active 0-0102112233435462728leftright

Frequency Map Window: At most 2 distinct

Decision, step 2 of 17

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)