Frequency Map + Window
Track counts of what is inside the window to answer "at most k distinct" style questions.
Decision · step 2 of 17Frequency 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.
What you will see
Counts rise and fall as the window moves; the distinct count drives shrinking.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(k) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Cells announce index, value and whether they are inside the window; each step announces the window bounds and the running value.
Reduced motion: The window frame snaps to its new bounds with a crossfade.