Move two boundaries through ordered data and reuse the overlap to update totals or search contiguous intervals.
Sliding window algorithm
A sliding window algorithm tracks a contiguous range of an ordered sequence by moving its left and right boundaries forward. When the ranges overlap, it can carry forward work from the previous range. A market-data monitor, for example, can update its recent cancellation count by adding newly included observations and subtracting expired ones, without recounting every observation in the window.
Remove the oldest, add the newest
Suppose a feed delivers five synthetic cancellation counts in order: 2, 1, 4, 3 and 0. The monitor uses the latest three observations and waits for a full window. The first two observations produce no output. At observation 3, the first total is 7. At observation 4, the count of 2 expires and the count of 3 enters, taking the total to 8. At observation 5, the count of 1 expires and the new count of 0 brings the total back to 7.
Three rows highlight observations 1 through 3, 2 through 4 and 3 through 5 of the synthetic counts 2, 1, 4, 3 and 0. The first sum is 7 cancellations. Removing 2 and adding 3 makes 8. Removing 1 and adding 0 makes 7.
The overlap is carried forward. Each move expires one count on the left and admits one on the right.
For observations x1 through xn and a width of k, let St be the sum of the full window ending at observation t. Initialise Sk by adding the first k values. Each subsequent update is
St=St−1−xt−k+xt,t=k+1,…,n.
This takes O(n) time overall because each step after initialisation does constant work. If the input is an array, the expired value is available by index and the sum uses constant auxiliary space, excluding stored outputs. A one-pass stream can keep the latest k observations in a FIFO buffer so it knows what to subtract next. For arbitrary ranges over a static sequence, prefix sums allow direct lookups. The update also depends on the statistic. If the current maximum expires, subtracting it reveals nothing about the next maximum. A monotonic deque retains candidates for that job. Competitive Programmer’s Handbook, Chapter 8
The last three observations can cover different amounts of time
A count window keeps the latest k observations. A time window keeps the observations whose timestamps fall within a stated duration and endpoint convention. Suppose the five counts arrived and became usable at 09:30:00, :01, :06, :09 and :20. At 09:30:09 the last three observations contribute 8 cancellations. An eight-second window open on the left and closed on the right keeps only the counts at :06 and :09, for 7 cancellations. The count at :01 lies exactly at the excluded cutoff. With ordered timestamps, the left boundary can advance past several expired observations at once, even as one new observation enters. pandas windowing guide
A trailing window can still introduce look-ahead bias if a backtest filters by event time and ignores when each record became usable. A trade stamped before the cutoff but delivered after it was unavailable to that decision. Likewise, a window that includes the session's final closing bar can feed a decision only once the completed bar has arrived and been processed. The SelfMadeQuant lesson on observation, event and availability timestamps works through the timing from receipt to order arrival (public preview, full lesson for members).
When the window width depends on the values
A different use of the same two boundaries is to search for the longest contiguous interval that satisfies a cap. With nonnegative increments, extending to the right cannot reduce the sum. If the sum exceeds the cap, the algorithm can advance the left boundary until the sum fits. Starts discarded this way cannot become feasible at a later right boundary. Each boundary crosses each observation at most once, even if the left boundary moves several times in one update. With a running sum, the total work is O(n). USACO Guide, “Solution – Books”
That discard rule can fail for signed cash flows. With a cap of 4 and values of +6 and −4, the first value alone breaches the cap, but the pair totals 2 and fits. Discarding the first value on the initial breach misses the longest feasible interval. The fixed-width sum update still works with signed values, and time-based expiry uses timestamp order regardless of the signs. It is the greedy discard rule that needs the monotonic constraint.
