Sliding Window Frequency Maps
Asked of: Software Engineer
Last updated
![Four-frame horizontal infographic tracing a sliding-window over [A, B, C, A, B, A] with left/right pointers, highlighted window, frequency map counts, a deletion when a count reaches zero, and one-line captions.](https://ik.imagekit.io/9osfw19dn/cheatsheets/concepts/sliding-window-frequency-maps_D4F5tHOQ8.png?tr=w-1360,q-95)
What's being tested
These problems test sliding window reasoning over contiguous arrays/strings with a mutable frequency map that tracks whether the current window satisfies constraints. Interviewers are looking for clean O(n) two-pointer code, correct shrinking logic, and awareness of when a hash map, counter, or fixed-size array is the right state structure.
Patterns & templates
-
At-most-k distinct window — expand
right, incrementfreq[x], shrink whilelen(freq) > k; update answer after restoring validity. -
Bounded flips / replacements — track invalid count, e.g. zeros flipped; shrink while
zeros > k; answer ismax(ans, right-left+1). -
Frequency map cleanup — when
freq[x] == 0, deletex; stale keys makedistinctconstraints fail silently. -
Longest vs maximum sum window — for length, update after shrink; for sum/count objectives, maintain rolling aggregate alongside
freq. -
2D-to-1D reduction — for matrix variants, fix row/column boundaries, compress into arrays, then apply the same window logic.
-
LRU cache contrast — use hash map + doubly linked list for
get/putinO(1); do not confuse this with sliding-window frequency state.
Common pitfalls
Pitfall: Shrinking only once with
ifinstead of repeatedly withwhileleaves the window invalid when multiple removals are required.
Pitfall: Updating the answer before enforcing the constraint can record an impossible window with too many distinct types or flips.
Pitfall: Forgetting to delete zero-count entries causes
len(freq)to overcount distinct elements.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- String And Sliding Window AlgorithmsCoding & Algorithms
- Sliding Window And K-Flip OptimizationCoding & Algorithms
- Arrays, Sliding Windows, DP And Stack PatternsCoding & Algorithms
- Sliding Window, Binary Search, and Prefix ReasoningCoding & Algorithms
- Intervals, Sliding Windows, And Time-Ordered StateCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms