Sliding window

Take War and Peace in the original Russian and run a window of a thousand words along it: first words one to a thousand, then two to 1001, and so on to the end. How many distinct words are in each window? There are 435 thousand windows, and recounting each one afresh is 435 million operations. But if you remember what lies in the window, each shift needs two: one word came in, one went out. Here is what came out.

In a thousand-word window Tolstoy has from 353 to 683 distinct words. The most varied place is in the fourth volume, the scene where Kutuzov talks to the soldiers: narration, description, speech, all mixed together. The most monotonous is the second part of the epilogue, the reasoning about freedom and necessity: the same words, «поступок» (act), «причина» (cause), «время» (time), «большему или меньшему» (to a greater or lesser), repeat again and again. The window length changes the numbers but not the picture: the epilogue is monotonous at any window.

The idea

A window of width w shifts by one element: one comes in on the right, one goes out on the left. If the answer for the window can be corrected by these two elements (add and subtract, increment and decrement a counter), then all windows take O(n) operations rather than O(n·w), as when recomputing each window afresh.

For a sum and a mean the correction is obvious: add the element that came in, subtract the one that left. For the number of distinct words the window keeps a counter for each word; the number of distinct ones changes only when a counter passes through zero. The maximum is harder: when the largest element leaves, the next largest cannot be found so simply. For this there is the monotonic queue, which keeps only those that may still become the maximum, or a queue on two stacks, as in the problem on the strongest earthquake in a month.

The moving average

The most common window in real life is the moving average: the mean over the last w days, computed for each day. Below are 85 years of Almaty’s daily mean temperature. Move the window width.

With a window of a few days the line follows the weather. With a month’s window the seasons remain: a wave from −4° on average in January to +22° in July. With a year’s window the seasons disappear (the window always holds exactly one of each month), and slow changes from year to year show. Each position of the window takes one addition and one subtraction, while without the window a ten-year mean would need a hundred million additions.

The reanalysis is a model estimate, and its first decades have less data, so the early years of the series deserve more caution: the warmest year in the series comes out as 1941, and that is more likely a feature of the reanalysis of those years than the weather.

Time windows

A window need not be measured in elements. “How many requests in the last minute”, “how many events in a day” is a time window: its right edge is the current event, and its left edge is pulled up while the window is longer than the given span. The window may hold zero events or a thousand: it is the same two pointers, only the boundary is counted in seconds.

The busiest day in the earthquake catalogue for 2015–2025 begins on 29 July 2025 with a magnitude 8.8 earthquake off Kamchatka: in the next 24 hours, 166 shocks of magnitude five or more, and 38 in the busiest hour. Rate limiters in web services work the same way: they keep a window of recent requests and refuse when it holds more than allowed. This is the article’s second problem.

Code

Moving averages for windows of a week, a year and a decade: the coldest and warmest periods and how many additions it took.

Time windows on the earthquake catalogue: the busiest hour, day and week.

Vocabulary richness: a window with counters in a hash table.

What it costs

O(n) shifts, each O(1) for a sum and mean, O(1) on average for counters in a hash table, O(1) amortised for the maximum in a monotonic queue. Memory is O(1) for a sum, O(w) for whatever must be remembered about the window’s contents.

There are two subtleties. The first is floating-point numbers: if fractional values are added and subtracted thousands of times, error accumulates, and the moving sum slowly drifts. It is cured with integers (as here: the temperature is stored in tenths of a degree), with periodic recomputation from scratch, or with Kahan summation. The second is the boundary of a time window: whether an event that happened exactly T seconds ago is in it changes the answer, and must be decided explicitly.

If windows have different widths and queries about them arrive out of order, a sliding window does not fit: then prefix sums are needed for sums, or a segment tree for maxima.

Problems

In the first, a window with counters looks for the most varied and the most monotonous place in a text; the tests are volumes of War and Peace and an English translation. In the second, a time window limits the rate of earthquake alerts.