Sliding windows: fixed and variable

A sliding window is a stretch of consecutive items in an array or a string, marked by two indices, left and right, that only ever move forward. Instead of adding up or recounting every stretch from scratch, you keep one running summary of what is inside the window, such as its total, and update it as an item enters on the right or leaves on the left. A fixed window always holds k items, so every step adds one item and removes one. A variable window grows on the right and shrinks on the left whenever it breaks a rule, such as “the total is at most 20”. Either way, a scan that looked at every stretch, O(n·k) or O(n²), becomes O(n). This lesson solves one problem completely with a fixed window, in Python, JavaScript and C++, then builds the variable window and shows a kind of input that breaks it: values below zero.

When a window fits the problem

A window is two pointers that move the same way, like the reader–writer pair of the two-pointers overview, except that what matters here is the stretch between them. Two things have to be true before a window can help.

1. The answer concerns a contiguous stretch. The wording usually says so: “consecutive days”, “a substring”, “a subarray”, “a run of”, “within any 10 minutes”. A subsequence may skip items, so it is not a window, and neither is “any two items” (a job for hashing or two pointers) or “any subset”.
2. The summary changes by a small, exact step when one item enters or leaves. A total, a count, a table of letter counts and the number of distinct values in such a table all do. The largest value does not: when the maximum leaves the window, nothing in the old summary says what the new maximum is. Windows that need the maximum keep a queue of candidate positions instead, a monotonic deque.

A variable window needs a third property, monotone validity: if a window obeys the rule, every shorter window inside it obeys it too. “At most 20 mm of rain” behaves like that, because rainfall is never negative, and so do “no repeated letter” and “at most k distinct values”. Questions about the shortest window turn it round: if a window obeys the rule (“at least 100 mm”, “contains every required letter”), every longer window that contains it obeys it too. Either form is what lets the window throw items away on the left and never look at them again.

A problem solved in full: the wettest week

For the log [12, 0, 35, 4, 0, 61, 8, 17, 0, 3] and k = 3 the answer is (86, 5): days 5, 6 and 7 hold 61 + 8 + 17 = 86 mm. With k = 1 it is the wettest single day, (61, 5), and with k = 10 the whole log, (140, 0).

The brute force, and why it is too slow

Add up each of the n − k + 1 stretches on its own and keep the largest. It is short and plainly right, and it does (n − k + 1) × k additions. That is worst near k = n / 2: at n = 100,000 and k = 50,000 it is 50,001 × 50,000, about 2.5 billion additions. A common planning figure is 10⁸ simple steps a second for compiled code and 10⁷ for CPython (the lesson on constraints explains where it comes from), so even compiled code would need tens of seconds, far beyond a time limit of a few seconds.

What to notice

Two neighbouring stretches share k − 1 days. Moving from days 4–6 to days 5–7 removes day 4 and adds day 7, and nothing else changes:

So no stretch needs adding up twice. Keep one total, and at each step add the day that enters and subtract the day that leaves.

The window, and why it is right

The loop keeps one statement true, its invariant: after the step for day right, total is the sum of the k days that end at right, and best_total is the largest such sum so far, with best_start the earliest first day that reaches it.

• Before the loop the first k days are added up directly, so the statement holds for right = k − 1.
• Each step adds rain[right] and subtracts rain[right - k]. That turns the sum of days right − k to right − 1 into the sum of days right − k + 1 to right, which is exactly the next window.
• Ties go to the earliest stretch, because best_total changes only when a total is strictly larger.
• At the end every one of the n − k + 1 windows has been compared once, so best_total is the answer.

The work is k additions for the first window and then two per step, k + 2(n − k) in all, which is at most 2n: O(n) time and O(1) extra memory, whatever k is. The lesson on dry runs and invariants shows how to state and check an invariant like this one in a round.

Code in Python and JavaScript

"""The wettest k consecutive days of a rain log, two ways: a brute force and a fixed-size sliding window."""


def wettest_brute(rain, k):
    """Add up every stretch of k days from scratch. Returns (total, first day of the stretch)."""
    totals = [sum(rain[start:start + k]) for start in range(len(rain) - k + 1)]
    best_total = max(totals)
    return best_total, totals.index(best_total)  # index() finds the earliest stretch with that total


def wettest_window(rain, k):
    """Slide one window of k days along the log: add the day that enters, subtract the day that leaves."""
    total = sum(rain[:k])  # the first window: days 0 to k - 1
    best_total, best_start = total, 0
    for right in range(k, len(rain)):
        total += rain[right] - rain[right - k]  # day `right` enters, day `right - k` leaves
        if total > best_total:  # strictly greater, so the earliest stretch wins a tie
            best_total, best_start = total, right - k + 1
    return best_total, best_start


def season(days, seed):
    """A made-up rain log in whole millimetres, the same on every computer: multiply by 48271 and keep the remainder
    modulo 2**31 - 1, the random generator that C++ calls std::minstd_rand."""
    state, rain = seed, []
    for _ in range(days):
        state = state * 48271 % 2_147_483_647
        rain.append(0 if state % 5 < 2 else 1 + state // 5 % 90)  # about two days in five stay dry
    return rain


sample = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3]
log = season(122, seed=7)
print("first days of the season:", log[:10])
print("log       k  brute force  window")
for name, rain, k in [("sample", sample, 3), ("sample", sample, 1), ("sample", sample, 10), ("season", log, 7)]:
    # a typical k, the smallest, k = n (a single window), and a week of the made-up season
    print(f"{name:<8}{k:>3}  {str(wettest_brute(rain, k)):<11}  {wettest_window(rain, k)}")

first days of the season: [80, 52, 33, 86, 0, 7, 0, 0, 0, 87]
log       k  brute force  window
sample    3  (86, 5)      (86, 5)
sample    1  (61, 5)      (61, 5)
sample   10  (140, 0)     (140, 0)
season    7  (362, 82)    (362, 82)

// The wettest k consecutive days of a rain log, two ways: a brute force and a fixed-size sliding window.

// Add up every stretch of k days from scratch. Returns [total, first day of the stretch].
function wettestBrute(rain, k) {
  const totals = [];
  for (let start = 0; start + k <= rain.length; start++) {
    totals.push(rain.slice(start, start + k).reduce((sum, mm) => sum + mm, 0));
  }
  const bestTotal = totals.reduce((a, b) => Math.max(a, b)); // not Math.max(...totals): long arrays overflow the call
  return [bestTotal, totals.indexOf(bestTotal)]; // indexOf() finds the earliest stretch with that total
}

// Slide one window of k days along the log: add the day that enters, subtract the day that leaves.
function wettestWindow(rain, k) {
  let total = 0;
  for (let day = 0; day < k; day++) total += rain[day]; // the first window: days 0 to k - 1
  let bestTotal = total;
  let bestStart = 0;
  for (let right = k; right < rain.length; right++) {
    total += rain[right] - rain[right - k]; // day `right` enters, day `right - k` leaves
    if (total > bestTotal) {
      // strictly greater, so the earliest stretch wins a tie
      bestTotal = total;
      bestStart = right - k + 1;
    }
  }
  return [bestTotal, bestStart];
}

// A made-up rain log in whole millimetres, the same on every computer: multiply by 48271 and keep the remainder
// modulo 2 ** 31 - 1, the random generator that C++ calls std::minstd_rand. Every product stays below 2 ** 53, so
// plain numbers keep it exact.
function season(days, seed) {
  let state = seed;
  const rain = [];
  for (let i = 0; i < days; i++) {
    state = (state * 48271) % 2147483647;
    rain.push(state % 5 < 2 ? 0 : 1 + (Math.floor(state / 5) % 90)); // about two days in five stay dry
  }
  return rain;
}

const pair = ([total, start]) => `(${total}, ${start})`;
const sample = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3];
const log = season(122, 7);
console.log(`first days of the season: [${log.slice(0, 10).join(", ")}]`);
console.log("log       k  brute force  window");
for (const [name, rain, k] of [["sample", sample, 3], ["sample", sample, 1], ["sample", sample, 10], ["season", log, 7]]) {
  // a typical k, the smallest, k = n (a single window), and a week of the made-up season
  console.log(`${name.padEnd(8)}${String(k).padStart(3)}  ${pair(wettestBrute(rain, k)).padEnd(11)}  ${pair(wettestWindow(rain, k))}`);
}

first days of the season: [80, 52, 33, 86, 0, 7, 0, 0, 0, 87]
log       k  brute force  window
sample    3  (86, 5)      (86, 5)
sample    1  (61, 5)      (61, 5)
sample   10  (140, 0)     (140, 0)
season    7  (362, 82)    (362, 82)

Both programs print the same lines. The brute force and the window agree on the sample for k = 3, for k = 1 and for k = n, and on a made-up season of 122 days, whose wettest week starts on day 82 with 362 mm. The season comes from a small random generator written out in each language: multiply by 48,271 and keep the remainder after dividing by 2³¹ − 1. The C++ standard defines the same generator as std::minstd_rand, so every language gets the same log from the same seed. JavaScript stores numbers as 64-bit floating point, which is exact for whole numbers below 2⁵³, and no product the generator forms comes near that.

Three details of the code are worth saying aloud. Python’s rain[start:start + k] copies k items before sum adds them, and Python’s time-complexity table lists a slice as O(j − i), so the brute force really is O(n·k) even though its inner loop is hidden. The JavaScript brute force finds the largest total with reduce, because MDN warns that spreading a long array into Math.max can fail or return a wrong result. And Python’s own documentation uses the same idea: the moving_average recipe of collections keeps a running sum s and updates it with s += elem - d.popleft(). The sliding_window recipe of itertools yields each run of n items from a deque with a maximum length instead; building each tuple copies all n items, so when you only need a total it costs as much as the brute force.

The same window in C++

// The wettest k consecutive days of a rain log with a fixed-size sliding window (C++23).
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

// Returns {total, first day} of the wettest k consecutive days. Needs 1 <= k <= rain.size(): with a larger k the
// first loop would read past the end of the vector. Check it as k > rain.size(), never as rain.size() - k < 0:
// rain.size() is unsigned, so the subtraction wraps around to a huge number and is never below zero.
std::pair<long long, std::size_t> wettest_window(const std::vector<int>& rain, std::size_t k) {
    long long total = 0;
    for (std::size_t day = 0; day < k; ++day) total += rain[day];  // the first window: days 0 to k - 1
    long long best_total = total;
    std::size_t best_start = 0;
    for (std::size_t right = k; right < rain.size(); ++right) {
        total += rain[right] - rain[right - k];  // day `right` enters, day `right - k` leaves
        if (total > best_total) {                // strictly greater, so the earliest stretch wins a tie
            best_total = total;
            best_start = right - k + 1;
        }
    }
    return {best_total, best_start};
}

// The same made-up rain log as the Python and JavaScript versions: they write out by hand the generator that the
// standard library calls std::minstd_rand (multiply by 48271, keep the remainder modulo 2^31 - 1).
std::vector<int> season(int days, std::uint_fast32_t seed) {
    std::minstd_rand next(seed);
    std::vector<int> rain;
    for (int i = 0; i < days; ++i) {
        const auto state = next();
        rain.push_back(state % 5 < 2 ? 0 : static_cast<int>(1 + state / 5 % 90));  // about two days in five stay dry
    }
    return rain;
}

int main() {
    const std::vector<int> sample{12, 0, 35, 4, 0, 61, 8, 17, 0, 3};
    const std::vector<int> season_log = season(122, 7);
    struct Case { const char* name; const std::vector<int>& rain; std::size_t k; };
    const Case cases[] = {{"sample", sample, 3}, {"sample", sample, 1}, {"sample", sample, 10}, {"season", season_log, 7}};
    std::cout << "log       k  window\n";
    for (const Case& c : cases) {
        auto [total, start] = wettest_window(c.rain, c.k);
        std::cout << std::left << std::setw(8) << c.name << std::right << std::setw(3) << c.k << "  (" << total << ", "
                  << start << ")\n";
    }
}

"""Builds wettest_week.cpp with clang++ (C++23, warnings, AddressSanitizer and UndefinedBehaviorSanitizer) and runs
it, printing each command and what it printed, as a terminal shows them."""
import subprocess

COMMANDS = [
    "clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined wettest_week.cpp -o wettest_week",
    "./wettest_week",
]

for command in COMMANDS:
    print(f"$ {command}")
    result = subprocess.run(command, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)
    print(result.stdout, end="")
    if result.returncode != 0:
        print(f"[exit status {result.returncode}]")
        break

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined wettest_week.cpp -o wettest_week
$ ./wettest_week
log       k  window
sample    3  (86, 5)
sample    1  (61, 5)
sample   10  (140, 0)
season    7  (362, 82)

The C++ version prints the same results. The build turns on the compiler’s warnings and two run-time checkers: AddressSanitizer, which reports any read or write outside the vector, and UndefinedBehaviorSanitizer, which reports arithmetic that the standard leaves undefined, such as a signed overflow. The build printed no warning, and the run printed no report. C++ adds one trap of its own: rain.size() is unsigned, so a guard written as rain.size() - k < 0 can never be true, because the subtraction wraps around to a huge positive number. Compare k > rain.size() instead.

A dry run

In a live round, trace the window on the sample before you trust it, one row per step:

"""A dry run of the fixed window on the sample log: one row per step, with the day that enters and the day that leaves."""
rain = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3]
k = 3

total = sum(rain[:k])  # the first window, days 0-2: 12 + 0 + 35
best_total, best_start = total, 0
print("days  enters  leaves  total  best")
print(f"0-2   {'':>6}  {'':>6}  {total:>5}  {best_total} (day {best_start})")
for right in range(k, len(rain)):
    total += rain[right] - rain[right - k]
    if total > best_total:
        best_total, best_start = total, right - k + 1
    days = f"{right - k + 1}-{right}"
    print(f"{days:<4}  {rain[right]:>6}  {rain[right - k]:>6}  {total:>5}  {best_total} (day {best_start})")

days  enters  leaves  total  best
0-2                      47  47 (day 0)
1-3        4      12     39  47 (day 0)
2-4        0       0     39  47 (day 0)
3-5       61      35     65  65 (day 3)
4-6        8       4     69  69 (day 4)
5-7       17       0     86  86 (day 5)
6-8        0      61     25  86 (day 5)
7-9        3       8     20  86 (day 5)

Read a row aloud: “day 5 enters with 61 mm and day 2 leaves with 35, so the total rises by 26, from 39 to 65, which beats 47.” Each total is the previous one plus the day that enters minus the day that leaves, and the best changes only on rows where the new total is larger. If your own code prints a different table, the first row that differs points at the bug.

Edge cases and the usual bugs

• k = n: one window. The loop body never runs and the first window is the answer, as the k = 10 line shows.
• k = 1: the largest single value.
• Ties: > keeps the earliest stretch and >= the latest; check which one the problem asks for.
• The wrong day leaves: the day that leaves the window ending at right is right - k. Subtracting rain[right - k + 1] removes a day that is still inside.
• Starting the best at 0: harmless for rainfall, wrong when values can be below zero, such as night temperatures. Start from the first window instead; the exercise at the end has readings below zero to catch this.
• k larger than n: there is no window at all. The limits here rule it out; when they do not, check it first.

How much work the window saves

"""How many daily values each version adds or subtracts, counted while its loops run."""


def brute_force_steps(n, k):
    steps = 0
    for start in range(n - k + 1):  # every stretch of k days ...
        for day in range(start, start + k):  # ... is added up from scratch
            steps += 1
    return steps


def window_steps(n, k):
    steps = 0
    for day in range(k):  # the first window is added up once
        steps += 1
    for right in range(k, n):  # then each step adds one day and subtracts one
        steps += 2
    return steps


print(f"{'n':>7}  {'k':>6}  {'brute force':>13}  {'window':>7}")
for n, k in [(10, 3), (122, 7), (122, 61), (2_000, 1_000)]:
    print(f"{n:>7,}  {k:>6,}  {brute_force_steps(n, k):>13,}  {window_steps(n, k):>7,}")

# The problem's limits, from the formulas that the counts above follow: (n - k + 1) * k and k + 2 * (n - k).
n, k = 100_000, 50_000
print("at the limits, from the formulas:")
print(f"{n:>7,}  {k:>6,}  {(n - k + 1) * k:>13,}  {k + 2 * (n - k):>7,}")

      n       k    brute force   window
     10       3             24       17
    122       7            812      237
    122      61          3,782      183
  2,000   1,000      1,001,000    3,000
at the limits, from the formulas:
100,000  50,000  2,500,050,000  150,000

The brute force’s count grows with n × k, the window’s only with n. On the 122-day season with k = 7 the brute force does 812 additions against the window’s 237; with k = 61 it does 3,782 against 183; at n = 2,000 and k = 1,000 it does 1,001,000 against 3,000. At the problem’s limits the formulas give about 2.5 billion against 150,000.

The variable window: grow on the right, shrink on the left

When the question is “the longest stretch that obeys a rule” or “the shortest stretch that reaches a goal”, the length is the unknown. The variable window moves right on by one item at every step and moves left on only when it has to:

Here it is twice, on the same rain log: the longest spell whose total stays within a limit, and the shortest stretch that collects at least a target, say for a tank that has to fill.

"""Variable-size windows over a rain log, where no day is below zero: the longest spell that stays under a limit,
and the shortest stretch that reaches a target."""


def longest_within(rain, limit):
    """The longest stretch of consecutive days whose total is at most `limit`. Returns (length, first day)."""
    best_len, best_start = 0, 0
    total = left = 0
    for right, mm in enumerate(rain):
        total += mm  # day `right` enters
        while total > limit:  # too wet: drop days from the left until the window fits again
            total -= rain[left]
            left += 1
        if right - left + 1 > best_len:  # the window is valid here, so it is a candidate
            best_len, best_start = right - left + 1, left
    return best_len, best_start


def shortest_reaching(rain, target):
    """The fewest consecutive days whose total is at least `target` (1 or more). Returns (length, first day),
    or (0, -1) when even the whole log falls short."""
    best_len, best_start = 0, -1
    total = left = 0
    for right, mm in enumerate(rain):
        total += mm
        while total >= target:  # valid: record it, then see whether a shorter window ending here still is
            if best_len == 0 or right - left + 1 < best_len:
                best_len, best_start = right - left + 1, left
            total -= rain[left]
            left += 1
    return best_len, best_start


sample = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3]
print("longest within 20 mm:", longest_within(sample, 20))
print("longest within 0 mm:", longest_within(sample, 0))
print("shortest reaching 100 mm:", shortest_reaching(sample, 100))
print("shortest reaching 200 mm:", shortest_reaching(sample, 200))

longest within 20 mm: (3, 7)
longest within 0 mm: (1, 1)
shortest reaching 100 mm: (4, 2)
shortest reaching 200 mm: (0, -1)

// Variable-size windows over a rain log, where no day is below zero: the longest spell that stays under a limit,
// and the shortest stretch that reaches a target.

// The longest stretch of consecutive days whose total is at most `limit`. Returns [length, first day].
function longestWithin(rain, limit) {
  let bestLen = 0;
  let bestStart = 0;
  let total = 0;
  let left = 0;
  for (let right = 0; right < rain.length; right++) {
    total += rain[right]; // day `right` enters
    while (total > limit) {
      // too wet: drop days from the left until the window fits again
      total -= rain[left];
      left++;
    }
    if (right - left + 1 > bestLen) {
      // the window is valid here, so it is a candidate
      bestLen = right - left + 1;
      bestStart = left;
    }
  }
  return [bestLen, bestStart];
}

// The fewest consecutive days whose total is at least `target` (1 or more). Returns [length, first day],
// or [0, -1] when even the whole log falls short.
function shortestReaching(rain, target) {
  let bestLen = 0;
  let bestStart = -1;
  let total = 0;
  let left = 0;
  for (let right = 0; right < rain.length; right++) {
    total += rain[right];
    while (total >= target) {
      // valid: record it, then see whether a shorter window ending here still is
      if (bestLen === 0 || right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      total -= rain[left];
      left++;
    }
  }
  return [bestLen, bestStart];
}

const pair = ([length, start]) => `(${length}, ${start})`;
const sample = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3];
console.log("longest within 20 mm:", pair(longestWithin(sample, 20)));
console.log("longest within 0 mm:", pair(longestWithin(sample, 0)));
console.log("shortest reaching 100 mm:", pair(shortestReaching(sample, 100)));
console.log("shortest reaching 200 mm:", pair(shortestReaching(sample, 200)));

longest within 20 mm: (3, 7)
longest within 0 mm: (1, 1)
shortest reaching 100 mm: (4, 2)
shortest reaching 200 mm: (0, -1)

The two functions differ in where they record a candidate. longest_within records after its while loop, once the window fits again. shortest_reaching records inside the loop, on every window that still reaches the target, and then shrinks it to see whether a shorter one does too. On the sample, the longest stretch with at most 20 mm is days 7 to 9 (17 + 0 + 3 = 20), and the shortest with at least 100 mm is days 2 to 5 (35 + 4 + 0 + 61). A limit of 0 asks for the longest run of completely dry days: a single day, because no two dry days of the sample are neighbours. A target of 200 mm is never reached, so that answer is (0, -1).

Why dropping days is safe. No day has negative rainfall, so if days left to right hold more than the limit, every longer stretch that starts at left and ends at right or later holds at least as much. Day left can never start an answer again, and the window drops it for good.

Why a loop inside a loop is still O(n). right moves n times. left only moves forward and never passes right + 1, so over the whole run it moves at most n times, however those moves are spread over the steps. The while loop therefore runs at most n times in total, not n times per step. This dry run counts the moves:

"""A dry run of the variable window: the longest spell of the sample log with at most 20 mm in total."""
rain = [12, 0, 35, 4, 0, 61, 8, 17, 0, 3]
limit = 20

best_len, best_start = 0, 0
total = left = 0
left_moves = 0
print("day  mm  dropped      window  total")
for right, mm in enumerate(rain):
    total += mm  # day `right` enters
    dropped = []
    while total > limit:
        dropped.append(rain[left])
        total -= rain[left]
        left += 1
        left_moves += 1
    if right - left + 1 > best_len:
        best_len, best_start = right - left + 1, left
    window = f"{left}-{right}" if left <= right else "empty"
    print(f"{right:>3}  {mm:>2}  {str(dropped) if dropped else '-':<11}  {window:<6}  {total:>5}")
print(f"longest: {best_len} days, from day {best_start}")
print(f"right moved {len(rain)} times, left {left_moves} times")
print(f"{len(rain) + left_moves} moves in all; the bound is {2 * len(rain)}")

day  mm  dropped      window  total
  0  12  -            0-0        12
  1   0  -            0-1        12
  2  35  [12, 0, 35]  empty       0
  3   4  -            3-3         4
  4   0  -            3-4         4
  5  61  [4, 0, 61]   empty       0
  6   8  -            6-6         8
  7  17  [8]          7-7        17
  8   0  -            7-8        17
  9   3  -            7-9        20
longest: 3 days, from day 7
right moved 10 times, left 7 times
17 moves in all; the bound is 20

On day 2, 35 mm arrive and three days leave at once, day 2 itself among them, so the window is empty for a moment; on most days nothing leaves. Ten moves of right and seven of left make 17 moves for 10 days, within the bound of 20.

When the window breaks: values below zero

Now let values fall. A water tank logs its level change each hour, inflow minus use, and the question is whether some stretch of consecutive hours changes the level by exactly 2. When no change is negative, a variable window answers it: grow, shrink while the total is above the target, and stop when it equals the target. On [5, -3, 4] it gets it wrong:

"""A stretch of hours whose changes add up to exactly `target`: a variable window, a brute force and prefix sums.
Each returns (first hour, last hour) of a stretch it finds, or None."""


def stretch_window(changes, target):
    """Grow on the right; shrink while the total is over the target. Right only when no change is below zero."""
    total = left = 0
    for right, change in enumerate(changes):
        total += change
        while total > target and left <= right:
            total -= changes[left]
            left += 1
        if total == target and left <= right:
            return left, right
    return None


def stretch_brute(changes, target):
    """Every stretch, from every first hour."""
    for first in range(len(changes)):
        total = 0
        for last in range(first, len(changes)):
            total += changes[last]
            if total == target:
                return first, last
    return None


def stretch_prefix(changes, target):
    """Prefix sums and a dict, for changes of any sign: the hours first..last add up to prefix[last + 1] - prefix[first],
    so look for an earlier prefix total equal to the current one minus the target."""
    first_seen = {0: 0}  # prefix total -> how many hours it covers (the earliest such position)
    prefix = 0
    for last, change in enumerate(changes):
        prefix += change
        if prefix - target in first_seen:
            return first_seen[prefix - target], last
        first_seen.setdefault(prefix, last + 1)
    return None


if __name__ == "__main__":
    for changes, target in [([3, 1, 0, 2, 5], 3), ([5, -3, 4], 2)]:
        print(f"{changes}, target {target}:")
        print("  window     ", stretch_window(changes, target))
        print("  brute force", stretch_brute(changes, target))
        print("  prefix sums", stretch_prefix(changes, target))

[3, 1, 0, 2, 5], target 3:
  window      (0, 0)
  brute force (0, 0)
  prefix sums (0, 0)
[5, -3, 4], target 2:
  window      None
  brute force (0, 1)
  prefix sums (0, 1)

At hour 0 the total, 5, is above the target, so the window drops hour 0 for good. But hours 0 and 1 together make 5 − 3 = 2. Dropping was safe only because a stretch that was too large could never become right by growing; once a later value can be negative, growing can make the total smaller again. The rule has lost its monotone validity, and nothing tells the window when shrinking is safe.

The fix is prefix sums. Let prefix[j] be the total of the first j hours, with prefix[0] = 0. The hours first to last add up to prefix[last + 1] - prefix[first], so a stretch ending at last hits the target exactly when an earlier prefix total equals prefix[last + 1] - target. A dict of the prefix totals seen so far answers that in O(1) time on average, according to Python’s time-complexity table, so stretch_prefix makes one scan of the data and works whatever the signs. A random test shows where the boundary lies:

"""Random tests: each version against the brute force, first with no change below zero, then with negative changes.
The lists come shortest first, so the first disagreement found is a small one."""
import random

from net_change import stretch_brute, stretch_prefix, stretch_window


def random_cases(lowest):
    rng = random.Random(3)  # a fixed seed: both versions get the same 2,000 lists on every run of one Python version
    for length in range(1, 9):
        for _ in range(250):
            yield [rng.randint(lowest, 5) for _ in range(length)], rng.randint(0, 8)


for lowest in (0, -5):
    print(f"changes from {lowest} to 5:")
    for name, version in [("window", stretch_window), ("prefix sums", stretch_prefix)]:
        checked = 0
        for changes, target in random_cases(lowest):
            # Several stretches may add up to the target, so compare whether one was found at all.
            if (version(changes, target) is None) != (stretch_brute(changes, target) is None):
                print(f"  {name}: wrong on {changes}, target {target}")
                print(f"    {version(changes, target)}, brute force {stretch_brute(changes, target)}")
                break
            checked += 1
        else:
            print(f"  {name}: right on all {checked:,} lists")

changes from 0 to 5:
  window: right on all 2,000 lists
  prefix sums: right on all 2,000 lists
changes from -5 to 5:
  window: wrong on [3, -1], target 2
    None, brute force (0, 1)
  prefix sums: right on all 2,000 lists

With changes from 0 to 5 the window agrees with the brute force on all 2,000 lists. Once changes can go down to −5 it fails almost at once, on the two-hour list [3, -1] with target 2: 3 alone is above 2, so it is dropped before −1 arrives. The prefix-sum version agrees on both sets. The fixed seed makes every run test the same lists; Python’s documentation guarantees the same sequence across versions only for random(), and randint may change in a later version, so replay a failure on the same Python. Rules with “at most” or “at least” and values below zero also start from prefix sums, but they look for a range of earlier totals rather than one exact value, so a dict is not enough there: they need the prefix totals kept in order.

Telling the variants apart

Most window questions take one of a few shapes, and the shape tells you what the window has to keep:

Interview questions

What is the difference between a fixed and a variable sliding window, and how do you tell which one a problem needs? Both keep a summary of a stretch of consecutive items between two indices that only move forward. A fixed window always holds k items: each step adds the item that enters and removes the one that leaves, so it fits questions that name the length, such as the highest total of any 7 days. A variable window grows on the right at every step and shrinks on the left while it breaks a rule; it fits questions where the length is the unknown, such as the longest stretch with at most k distinct values or the shortest stretch whose total reaches a target. The variable form is correct only when validity is monotone: shrinking a valid window keeps it valid, or, for shortest-window questions, growing it does. Rules about totals lose that property as soon as values can be negative.

A variable window has a while loop inside a for loop. Why does it still run in O(n) time? Count pointer moves instead of loop iterations. The for loop moves right forward n times. Each pass of the while loop moves left forward one place, left never moves back and never passes right + 1, so across the whole scan the while loop runs at most n times in total, however unevenly those passes are spread. Each move does O(1) work on the summary, so the whole scan is at most 2n moves: O(n). This is an amortised bound: one step can shrink the window by many items, but only items that entered earlier can leave. The argument fails if the code ever moves left backwards or rebuilds the summary from scratch inside the loop.

Key takeaways

• A sliding window keeps a summary of consecutive items between two indices that only move forward, so each item is added once and removed at most once: O(n) instead of O(n·k) or O(n²).
• Fixed size k: add the item that enters, subtract the item k places back, and record once the first window is full.
• Variable size: extend right every step, shrink from left while the window breaks the rule, and record where the window is valid (after the shrinking for longest, inside it for shortest).
• The variable window needs monotone validity. Totals lose it when values can be below zero; switch to prefix sums, with a dict for an exact target.
• State the invariant, trace a small case, and test the window against a brute force on many small random inputs.