--- title: 'Sliding Window' source: 'https://academia.sh/en/courses/advanced-algorithms/sliding-window' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # Sliding Window Incremental computation over a contiguous subarray; the 10 inputs where a negative value breaks the shrink rule and why the precondition belongs to the window, not the rule. The previous lesson placed two pointers at the array's two ends and met them in the middle; its precondition was order. This lesson's pattern keeps the pointers moving in the **same direction**. The region between them is a **window**: as the right pointer advances the window grows, and once a condition is met the left pointer advances, shrinking it. The gain comes from the sum never being recomputed from zero as the window slides; the entering value is added, the leaving value is subtracted. Its precondition never looks at order at all: **no value may be negative**. This lesson counts the inputs where that precondition breaks and shows that the precondition actually belongs not to the window but to the **shrink rule**. ## Problem, Oracle, and Pattern The problem is this: what is the length of the **shortest contiguous subarray** whose sum is not below the target. The oracle starts from every possible starting position, expands rightward, and stops the moment it first exceeds the target; it tries every starting point. The pattern advances in a single pass: it adds the right-end value to the sum, and as long as the sum exceeds the target, it narrows the window by subtracting from the left end. **PP10.** The corpus is the previous lesson's corpus: seed `20260218`, 40 arrays, 12 values each, values between −9 and 20. **All forty** of the forty arrays contain a negative value. **PP11.** The corpus satisfying the precondition is the **absolute value** of the same arrays' values. The only difference between the two corpora is sign; length, position, and generator are the same. **PP12.** The target is 25, and a subarray does not have to hit the target exactly; "not below the target" is sufficient. **PP13.** The oracle is brute force and is counted as always correct. The answer is a length; if no subarray hits the target, the answer is undefined. ```python SEED = 20260218 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def corpus(seed=SEED, n=40, length=12): r = generator(seed) return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]} for i in range(n)] class Counter: def __init__(self): self.step = 0 def count(self): self.step += 1 def oracle_shortest(array, target, s): """Tries every contiguous subarray. Always correct.""" best = None for i in range(len(array)): total = 0 for j in range(i, len(array)): s.count() total += array[j] if total >= target and (best is None or j - i + 1 < best): best = j - i + 1 break return best def pattern_sliding_window(array, target, s): """PRECONDITION: no value may be negative.""" left, total, best = 0, 0, None for right in range(len(array)): s.count() total += array[right] while total >= target: if best is None or right - left + 1 < best: best = right - left + 1 total -= array[left] left += 1 s.count() return best def measure(items, target): diverging, pk, ok = [], 0, 0 for k in items: s1, s2 = Counter(), Counter() a = pattern_sliding_window(k["array"], target, s1) b = oracle_shortest(k["array"], target, s2) pk, ok = pk + s1.step, ok + s2.step if a != b: diverging.append(k["no"]) return {"diverging": len(diverging), "first_diverging": diverging[:6], "pattern_step": pk, "oracle_step": ok, "ratio": round(ok / pk, 2)} K = corpus() P = [dict(k, array=[abs(x) for x in k["array"]]) for k in K] print("corpus:", len(K), "arrays | contain a negative value:", sum(1 for k in K if any(x < 0 for x in k["array"]))) for ad, items in (("precondition holds", P), ("precondition broken", K)): print(f" {ad}", measure(items, 25)) ``` ``` corpus: 40 arrays | contain a negative value: 40 precondition holds {'diverging': 0, 'first_diverging': [], 'pattern_step': 867, 'oracle_step': 2396, 'ratio': 2.76} precondition broken {'diverging': 10, 'first_diverging': [2, 12, 13, 15, 24, 26], 'pattern_step': 761, 'oracle_step': 2462, 'ratio': 3.24} ``` When the precondition holds, the pattern spends **867** steps and matches the oracle on 40 of 40 inputs; the oracle spends **2396** steps, a ratio of **2.76**. On the corpus containing negative values, diverging inputs come to **10**. This number is lower than the previous lesson's 25, and that low count is this lesson's most dangerous feature. The pattern still gives the correct answer on three quarters of the inputs. If a test set were chosen at random, the odds of a clean result would be high; the defect surfaces not through observation but through the **oracle**. The second row's ratio is also worth noting: **3.24**, **higher** than the 2.76 seen when the precondition holds. The pattern spends fewer steps on the broken input (761 versus 867), because negative values pull the sum down and the shrink loop runs less often. **Fewer steps does not mean a better answer.** ## What the Shrink Rule Rests On The pattern's one risky line is the `while total >= target` loop. This loop assumes that subtracting a value from the left will **decrease** the sum. That is true for non-negative values; the sum decreases monotonically as the left end advances, and the moment the loop first breaks its condition, the shortest window for that starting point has been found. When a negative value is subtracted, the sum **increases**. At that moment the window has narrowed but the sum has grown; the pattern counts this as progress and never takes the left end back. If a shorter solution exists among the skipped starting points, it is never seen. **PP14.** The pattern never **backtracks** the left end; each position leaves the left end at most once. The pattern's linear step count comes from this no-backtracking rule, and the rule cannot be relaxed. ```python def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def corpus(seed): r = generator(seed) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] def oracle_shortest(array, target): best = None for i in range(len(array)): total = 0 for j in range(i, len(array)): total += array[j] if total >= target and (best is None or j - i + 1 < best): best = j - i + 1 break return best def pattern_sliding_window(array, target): left, total, best = 0, 0, None for right in range(len(array)): total += array[right] while total >= target: if best is None or right - left + 1 < best: best = right - left + 1 total -= array[left] left += 1 return best second = corpus(20260218)[1] print("input 2:", second) print(" pattern:", pattern_sliding_window(second, 25), "| oracle:", oracle_shortest(second, 25)) print(" absolute value:", [abs(x) for x in second]) print(" pattern:", pattern_sliding_window([abs(x) for x in second], 25), "| oracle:", oracle_shortest([abs(x) for x in second], 25)) print() print("seed target precondition diverging/40 ratio") for seed in (20260218, 20260219): for target in (25, 15): K = corpus(seed) pool = (("holds ", [[abs(x) for x in d] for d in K]), ("broken ", K)) for ad, items in pool: diverging = sum(1 for d in items if pattern_sliding_window(d, target) != oracle_shortest(d, target)) print(f"{seed} {target:5d} {ad} {diverging:8d} {diverging / 40:.4f}") ``` ``` input 2: [-6, 15, 10, 11, 6, -5, -4, 3, 2, 17, -8, 5] pattern: 3 | oracle: 2 absolute value: [6, 15, 10, 11, 6, 5, 4, 3, 2, 17, 8, 5] pattern: 2 | oracle: 2 seed target precondition diverging/40 ratio 20260218 25 holds 0 0.0000 20260218 25 broken 10 0.2500 20260218 15 holds 0 0.0000 20260218 15 broken 6 0.1500 20260219 25 holds 0 0.0000 20260219 25 broken 8 0.2000 20260219 15 holds 0 0.0000 20260219 15 broken 6 0.1500 ``` On the second input, the oracle says **2**, the pattern says **3**. The correct answer is the pair `15 + 10`; the pattern cannot see this pair, because once the left end dropped the value `-6`, the sum grew and the window locked in the wrong place. The pattern's output is still a length, still plausible, still wrong. **PP15.** The second corpus comes from seed `20260219`. If the diverging-input ratio does not hold its order of magnitude, the result depends on the corpus and is written up that way. In the second corpus, diverging inputs for target 25 are **8**, versus **10** in the first; for target 15 both give **6**. All four measurements fall between 0.15 and 0.25, that is, **the same order of magnitude**. The result does not depend on the corpus. On the four rows where the precondition holds, diverging inputs are **zero**. ## The Precondition Belongs to the Rule, Not the Window The name sliding window covers two separate patterns at once, and their preconditions are not the same. The form above is **variable-size**: the window grows until a condition is met, and shrinks once it is. There is also a **fixed-size** form: the window is always k wide, one value enters from the right, one value leaves from the left. In the fixed-size form there is no shrink rule; the window does not narrow by checking a condition, it only slides. So the sum does not need to decrease monotonically either. **PP16.** The fixed-size window uses only an **incremental sum**: one addition, one subtraction. The pattern's step count is independent of k; the oracle's step count grows with k. ```python def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def corpus(seed=20260218): r = generator(seed) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Counter: def __init__(self): self.step = 0 def count(self): self.step += 1 def oracle_fixed(array, k, s): """Recomputes every window's sum from zero.""" best = None for i in range(len(array) - k + 1): total = 0 for j in range(i, i + k): s.count() total += array[j] if best is None or total > best: best = total return best def pattern_fixed(array, k, s): """Fixed-size window: one value enters, one leaves. No sign precondition.""" total, best = 0, None for right in range(len(array)): s.count() total += array[right] if right >= k: total -= array[right - k] if right >= k - 1 and (best is None or total > best): best = total return best print("k input diverging/40 pattern oracle ratio") for k in (3, 4, 6): for ad, prepare in (("no negatives", lambda d: [abs(x) for x in d]), ("negatives ", list)): diverging, pk, ok = 0, 0, 0 for array in corpus(): d = prepare(array) s1, s2 = Counter(), Counter() diverging += (pattern_fixed(d, k, s1) != oracle_fixed(d, k, s2)) pk, ok = pk + s1.step, ok + s2.step print(f"{k} {ad} {diverging:12d} {pk:5d} {ok:5d} {ok / pk:5.2f}") ``` ``` k input diverging/40 pattern oracle ratio 3 no negatives 0 480 1200 2.50 3 negatives 0 480 1200 2.50 4 no negatives 0 480 1440 3.00 4 negatives 0 480 1440 3.00 6 no negatives 0 480 1680 3.50 6 negatives 0 480 1680 3.50 ``` All six rows give zero diverging inputs. Negative values do not affect the fixed-size window at all; the pattern's step count is **480** at all three k values, the oracle's step count grows with k, and the ratio climbs from 2.50 to 3.50. This is the lesson's structural result: **the precondition belongs not to the pattern's name, but to a single rule inside it.** The sentence "sliding window does not work with negative values" is false; the correct sentence is "the shrink rule, which rests on the assumption that the sum decreases monotonically, does not work with negative values." Learning a pattern together with its precondition means knowing that rule, not knowing the pattern's name. ## Three Numbers | Metric | Oracle | Pattern | Diverging input | |---|---|---|---| | Variable window, precondition holds | 2396 steps | 867 steps | **0/40** | | Variable window, precondition broken | 2462 steps | 761 steps | **10/40** | | Fixed window (k=4), input with negatives | 1440 steps | 480 steps | **0/40** | The second row is where the pattern spends the fewest steps, and it is the only broken row. The third row gives zero divergence on the same input, because the pattern changed. ## A Check Restores Correctness, Not the Speedup Checking the precondition is cheap: looking for a negative value in an array is at most n comparisons and stops at the first negative found. If the check fails, the work falls to the oracle. This arrangement's correctness is complete; what needs asking is how much speedup is left. **PP17.** The checked pattern charges the check's steps to its own account too; when the work is handed off to the oracle, the oracle's steps are added to the pattern's step count as well. ```python def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def corpus(seed=20260218): r = generator(seed) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Counter: def __init__(self): self.step = 0 def count(self): self.step += 1 def oracle_shortest(array, target, s): best = None for i in range(len(array)): total = 0 for j in range(i, len(array)): s.count() total += array[j] if total >= target and (best is None or j - i + 1 < best): best = j - i + 1 break return best def pattern_sliding_window(array, target, s): left, total, best = 0, 0, None for right in range(len(array)): s.count() total += array[right] while total >= target: if best is None or right - left + 1 < best: best = right - left + 1 total -= array[left] left += 1 s.count() return best def checked(array, target, s): """Tests the precondition; falls back to the oracle if it fails.""" for x in array: s.count() if x < 0: return oracle_shortest(array, target, s) return pattern_sliding_window(array, target, s) for ad, prepare in (("no negatives", lambda d: [abs(x) for x in d]), ("negatives ", list)): diverging, checked_step, oracle_step = 0, 0, 0 for array in corpus(): d = prepare(array) s1, s2 = Counter(), Counter() diverging += (checked(d, 25, s1) != oracle_shortest(d, 25, s2)) checked_step += s1.step oracle_step += s2.step print(f"{ad} diverging {diverging}/40 checked pattern {checked_step:5d}" f" oracle {oracle_step:5d} ratio {oracle_step / checked_step:.2f}") ``` ``` no negatives diverging 0/40 checked pattern 1347 oracle 2396 ratio 1.78 negatives diverging 0/40 checked pattern 2568 oracle 2462 ratio 0.96 ``` Diverging inputs are **zero** in both rows. But the second row's ratio is **0.96**: on the corpus with negative values, the checked pattern spends **more** steps than the oracle. The reason is plain — all forty of the forty arrays fail the check, the work falls to the oracle all forty times, and the check's 106 steps pile on top. On the corpus where the precondition holds, the ratio stays at 1.78 — the check writes off a loss there too, from 2.76 down to 1.78. The reading that follows is this: **a precondition check is a correctness tool, not a performance tool.** Without knowing what share of inputs satisfy the precondition, nothing can be said about what the checked pattern will gain; in this corpus that share is zero, and the pattern has turned entirely into the oracle. ## Summary - Sliding window keeps two pointers moving in the same direction and updates the sum incrementally instead of recomputing it from zero. - The variable-size form's shrink rule assumes the sum decreases when a value is subtracted from the left; that assumption holds only for non-negative values. - On the corpus with negative values, the pattern diverges from the oracle on **10 inputs** and does so with **fewer steps**; fewer steps is not a sign of correctness. - In the second corpus, diverging inputs are 8; because the ratio holds its order of magnitude, the result does not depend on the corpus. - The fixed-size window carries no shrink rule and is unaffected by negative values: in all six measurements, diverging inputs are zero. ## Next Step Both patterns worked on a single array, with the position count known. The next pattern also advances its pointers in the same direction, but at **different speeds** and on a structure of unknown length: every node has a successor, and whether an end exists is not known in advance. The next lesson measures cycle detection and the middle element on this structure; its precondition is that progress really is one-directional, and when that precondition breaks, the pattern does not merely give a wrong answer — it may never stop at all.