Fixed-size vs variable-size windows

A fixed window has a size given by the question (k items); each step adds one item and removes one. A variable window grows on the right and shrinks on the left until a rule holds again, and the answer is a longest or shortest valid window. Both are O(n) because each item enters and leaves once.

Fixed: 'every k consecutive', 'average of k', 'rearranged pattern of length m'.

Variable: 'longest with at most', 'shortest with at least', 'no repeats'.

The variable window needs a monotonic rule: if a window breaks it, every bigger window containing it breaks it too.

Common mistakes

• Using a variable window when the rule is not monotonic (for example sums with negative numbers).
• Re-summing each fixed window, which is O(n·k).

Name the monotonic rule out loud. It is the condition that makes shrinking correct.

Follow-up questions

Think of your answer first, then open the hint.

1. How do rate limiters use windows?

   Show hint

   Fixed-window counters reset per period; sliding-window logs or counters smooth the edges between periods.

2. What changes for 'exactly k'?

   Show hint

   Often 'at most k' minus 'at most k - 1'.

Similar on Backend: Rate limiting with a token bucket Rate limiters reuse the same two shapes: a fixed window counts requests per period, a sliding window counts the last N seconds. Here the window runs over an array instead of a clock.