Sliding Window

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.

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.

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.

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.

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.