Sliding Window: A Running Answer for a Contiguous Run

The sliding window pattern keeps a running answer, such as a sum or a set of counts, for a contiguous run of an array, and updates it as the run moves instead of recomputing it. A contiguous run is a stretch of neighbouring elements with none skipped, and the window is the run between two indices, start and end. The cue is a property of the problem: the answer is a contiguous run, and taking in one more element can only push the run towards breaking its rule, never back. A sum of non-negative costs that must stay within a budget has that property, because adding a cost can only raise the sum.

A fixed window keeps the same length and slides one step at a time. A variable window grows by moving end to the right and shrinks by moving start to the right, only while the rule is broken. Its invariant is that the window between start and end always satisfies the rule once the shrinking stops.

Daily costs of 2 1 3 1 1 1 4 must be covered from a budget of 6, and the question is the longest run of consecutive days that fits.

Start only ever moves right, and so does end, so each element enters the window once and leaves it at most once. The pass is O(n) time for n elements and O(1) extra space for a sum, against O(n²) for trying every start and extending it.

A caterpillar on a branch moves the same way: the head reaches forward and the tail catches up. The likeness breaks at length. A caterpillar stays about the same length, while a variable window can stretch over the whole array or shrink to nothing.

The pattern rests on the rule moving one way. With negative costs, dropping the leftmost element can raise the sum, and the shrinking step no longer finds the right window.