The sliding window trick, and the one input that breaks it

Most of us learned the sliding window as a recipe: grow the right edge, shrink the left when things go bad. The recipe's fine. The trouble starts when you don't know why it works, because then you'll happily run it on an input where it's wrong and never notice.

The slow version

Find the longest run of consecutive entries with sum at most K, all numbers positive. The first thing anyone writes:

best = 0
for i in range(n):
    total = 0
    for j in range(i, n):
        total += a[j]
        if total <= K:
            best = max(best, j - i + 1)

That visits about n²/2 pairs. Fine for a thousand numbers, about a minute for 100,000, well over an hour for a million.

Most of those runs were dead on arrival. If a run starting at i already sums past K, making it longer can't fix it, but the inner loop keeps going to the end anyway.

Why the window can skip them

Positive numbers give you two facts. Adding an element on the right can only push the sum up. Removing one on the left can only bring it down.

So if [lo, hi] is over budget, every longer run containing it is over budget too, and the only repair is to move lo right. Once lo has passed an index, no later window wants it back: a window starting further left would contain one you already know is too big.

Both edges only move forward. Each index enters once and leaves at most once, so the whole scan is at most 2n steps.

def longest_run(a, K):
    lo = total = best = 0
    for hi, x in enumerate(a):
        total += x
        while total > K:
            total -= a[lo]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

Here it is on a = [3, 1, 2, 1, 4, 1, 1] with K = 5:

Add	Window	Sum	What happens	Longest
3	[3]	3	fits	1
1	[3, 1]	4	fits	2
2	[3, 1, 2]	6	too big: drop 3, sum 3	2
1	[1, 2, 1]	4	fits	3
4	[1, 2, 1, 4]	8	drop 1 and 2, sum 5	3
1	[1, 4, 1]	6	drop 1, sum 5	3
1	[4, 1, 1]	6	drop 4, sum 2	3

The answer is 3, and the left edge never moved backwards.

The input that breaks it

Allow negative numbers. Shortest run with sum at least 8 in [1, -5, 4, 4]: the answer is [4, 4], length 2.

A window that grows until it reaches 8 adds 1, then −5, then 4, then 4. The running total peaks at 4, never reaches 8, and the window reports that no such run exists. So you get a wrong answer, and nothing tells you.

The second fact is what broke. Dropping the −5 from the left would have raised the sum, so "shrink when invalid, grow when valid" no longer points the right way. That version needs prefix sums and a monotonic deque of candidate starts.

So before I reach for a window I ask one thing: if this window is invalid, is every larger one invalid too? If the answer's no, I use something else.

There's a longer version with a step-through of the window moving here: https://geodesicpartners.co.uk/coding-sliding-window-why