◄ WORLD V · SONNY 5DART 324 · a helldive at the net

THE SLIDING WINDOW grow, shrink, slide — the general one-pass window technique

The sliding window is the umbrella technique beneath much of streaming: maintain a contiguous window over the stream, growing it from the right and shrinking it from the left to preserve some invariant (a sum below a cap, no repeated element, at most k distinct). Because each endpoint only ever moves forward, the whole scan is one pass — a window that looks quadratic (all subarrays) resolved in O(n). Here the fixed-width case: over a stream, keep the running sum of the current window and report the maximum window sum, adding the entrant and dropping the leaver so the work per step never depends on the window's width.

THE TECHNIQUE two forward-only bounds; maintain the window's invariant in one pass

A stream and a window of 2. The demo maintains the running window sum and reports the maximum — each endpoint moving only forward: live demo


HISTORY & CREDIT the sliding-window / caterpillar method

“Checking every subarray is quadratic.” — when the endpoints only move forward, a sliding window checks the relevant ones in a single linear pass. The caterpillar crawls once. cited

technique · the sliding-window / “caterpillar” method for contiguous-subarray problems.
variants · fixed width (running sum), variable width (grow/shrink on an invariant), at-most-k-distinct.
kin · the two-pointer (dart 317) is the same forward-only idea on sorted data.
now · longest-substring-without-repeats, minimum-window-substring, rate limiting, streaming aggregates.

A window that only ever crawls forward; the invariant held as it grows and shrinks. Every relevant span, in one pass. sliding window

RECOMMEND FOR I-13 the max window sum, on the compiler

On the canonical compiler, the maximum window-2 sum over [1,3,2,5] is 7 (the window [2,5]):

$ i13 run op_slidingwindow.i13 # max sum of a width-2 window RUN OK · 244 step(s) · peak stack 6 · call depth 6 max_window_sum = 7 -- add the entrant, drop the leaver; one forward pass
Recommend: the sliding window is the batch's umbrella technique — the general shape that the monotonic queue, two-pointer, and moving averages are special cases of. i13 reports the max window-2 sum 7. The supplement to correctness: a correct all-subarrays scan is quadratic; forward-only endpoints make it one pass. Not a keeper (forward-only movement is a technique, not a structural property a correct alternative cannot have), but the connective tissue that shows the batch is one idea seen from many angles: touch each element a bounded number of times, carry a bounded summary, never look back.