Sliding window and prefix sums

The problem: the best week of the year

A small chain of supermarkets records its revenue for every day, in kobo. The owner is planning next year's promotions and asks: "What were our best 7 days in a row, and how much did we make in them?" Not the best calendar week, Monday to Sunday: any 7 consecutive days.

A run of consecutive items in a list is called a subarray (for strings, a substring). "Consecutive" is the important word. The frequency counter from the frequency lesson forgets positions, so it cannot help here; the answer lives in which values sit next to each other.

A naive solution: add up every period

For each possible start day, add up the 7 days from there, and keep the best:

function bestPeriodNaive(daily, k) {
  if (k <= 0 || daily.length < k) return null;
  let best = null;
  for (let start = 0; start + k <= daily.length; start++) {
    let total = 0;
    for (let d = start; d < start + k; d++) total += daily[d];
    if (best === null || total > best.total) best = { start, total };
  }
  return best;
}

const revenue = [42000, 51000, 38000, 60000, 75000, 90000, 88000, 40000, 35000, 99000, 101000, 97000, 30000, 45000];
const naira = (kobo) => `₦${(kobo / 100).toLocaleString("en-NG")}`;
const best = bestPeriodNaive(revenue.map((n) => n * 100), 7);
console.log(`best 7 days start on day ${best.start + 1}: ${naira(best.total)}`);
console.log(bestPeriodNaive([100, 200], 7));

best 7 days start on day 6: ₦550,000
null

Days are counted from 1 in the report and from 0 in the array, which is why the output adds 1. The toLocaleString("en-NG") call only formats the number with thousands separators; the maths stays in whole kobo.

What is wrong with it: count the operations

For one shop and one year, 359 periods of 7 additions is nothing. But the same report is soon wanted for the whole chain, hourly, over five years, with a window of 30 days (720 hours), and then for every product. Count the additions:

function bestPeriodNaive(values, k, counter) {
  let best = -Infinity;
  for (let start = 0; start + k <= values.length; start++) {
    let total = 0;
    for (let d = start; d < start + k; d++) {
      counter.adds++;
      total += values[d];
    }
    best = Math.max(best, total);
  }
  return best;
}

for (const [label, n, k] of [["1 year, daily, 7 days", 365, 7], ["5 years, hourly, 7 days", 43800, 168], ["5 years, hourly, 30 days", 43800, 720]]) {
  const values = Array.from({ length: n }, (_, i) => (i * 7919) % 1000);
  const counter = { adds: 0 };
  bestPeriodNaive(values, k, counter);
  console.log(`${label.padEnd(25)} n=${String(n).padEnd(6)} k=${String(k).padEnd(4)} adds=${counter.adds}`);
}

1 year, daily, 7 days     n=365    k=7    adds=2513
5 years, hourly, 7 days   n=43800  k=168  adds=7330344
5 years, hourly, 30 days  n=43800  k=720  adds=31018320

The count is (n − k + 1) · k: O(n · k). When the window is small compared with the data, that is close to n · k; a 30-day hourly window over five years already costs over 31 million additions for one product, and there are thousands of products. The waste is exactly what the reason block found: each period re-adds the k − 1 values it shares with its neighbour.

The pattern: slide, don't recompute

A window is a range of consecutive positions, described by its two edges: left (the first position inside) and right (the last). The sliding window pattern keeps a summary of what is inside the window (a total, a count, a Map) and updates it as the edges move, instead of recomputing it. It has two shapes, and a close relative:

1. Fixed size k: both edges move together, one step at a time.
   [ 4  2  7  1  8  3 ]
     [-----]              total = 13
        [-----]           total = 13 - 4 + 1 = 10

2. Variable size: right moves every step; left moves only when the window breaks a rule.
   right grows the window  ->  check the rule  ->  while broken, left shrinks it

3. Prefix sums: precompute running totals once, then the total of ANY range
   is one subtraction. Useful when the ranges are not neighbours.

Both window shapes are two pointers moving in the same direction, like the reader and writer in the two pointers lesson. Each edge only moves forward, so each moves at most n times in total: O(n), however the window grows and shrinks.

How to recognise it

• The question is about contiguous ranges: "in a row", "consecutive", "any 7 days", "substring", "streak", "period".
• It asks for the best, longest, shortest or number of such ranges.
• The summary of a range can be updated cheaply when one item enters or leaves: a sum, a count, a set of what is inside.
• Many queries ask for totals of arbitrary ranges of data that does not change: that is prefix sums.

The improved solution

Add up the first window once. Then, for each step, add the value that enters on the right and subtract the value that leaves on the left:

function bestPeriod(daily, k, counter = { ops: 0 }) {
  if (k <= 0 || daily.length < k) return null;
  let total = 0;
  for (let d = 0; d < k; d++) {
    counter.ops++;
    total += daily[d];
  }
  let best = { start: 0, total };
  for (let right = k; right < daily.length; right++) {
    counter.ops++;
    total += daily[right] - daily[right - k]; // one day enters, one day leaves
    if (total > best.total) best = { start: right - k + 1, total };
  }
  return best;
}

const revenue = [42000, 51000, 38000, 60000, 75000, 90000, 88000, 40000, 35000, 99000, 101000, 97000, 30000, 45000];
const naira = (kobo) => `₦${(kobo / 100).toLocaleString("en-NG")}`;
const best = bestPeriod(revenue.map((n) => n * 100), 7);
console.log(`best 7 days start on day ${best.start + 1}: ${naira(best.total)}`);
console.log(bestPeriod([100, 200], 7), bestPeriod([500, 900, 300], 3));

for (const [n, k] of [[365, 7], [43800, 168], [43800, 720]]) {
  const values = Array.from({ length: n }, (_, i) => (i * 7919) % 1000);
  const counter = { ops: 0 };
  bestPeriod(values, k, counter);
  console.log(`n=${String(n).padEnd(6)} k=${String(k).padEnd(4)} ops=${counter.ops}`);
}

best 7 days start on day 6: ₦550,000
null { start: 0, total: 1700 }
n=365    k=7    ops=365
n=43800  k=168  ops=43800
n=43800  k=720  ops=43800

The answer is the same, and the work is exactly n operations whatever the window size: k to fill the first window, then one per slide. Going from a 7-day to a 30-day window costs nothing extra. The start of the window that ends at right is right − k + 1; getting that formula right is where most off-by-one bugs in window code live, so check it on a tiny case (with k = 3 and right = 3, the window is positions 1, 2, 3, so the start is 1).

Its complexity

When the window size k is a small constant, O(n · k) is technically O(n) too. The difference matters when k grows with the data, as it did above (720 hours out of 43,800), or when you run the report thousands of times.

Variable size: the longest on-time streak

A logistics company rewards riders for streaks of on-time deliveries. Each rider's history is a list of true (on time) and false (late). The first question, the longest run of true, needs only a counter that resets on a late delivery. The company then relaxes the rule: a streak may include at most one late delivery (traffic happens). Now a simple reset no longer works, because a late delivery does not end the streak, the second late one does.

function longestStreak(onTime, maxLate) {
  let left = 0;
  let late = 0;
  let best = { length: 0, start: 0 };
  for (let right = 0; right < onTime.length; right++) {
    if (!onTime[right]) late++;              // grow: one delivery enters
    while (late > maxLate) {                 // shrink until valid again
      if (!onTime[left]) late--;
      left++;
    }
    const length = right - left + 1;
    if (length > best.length) best = { length, start: left };
  }
  return best;
}

const T = true, F = false;
const history = [T, T, F, T, T, T, F, T, T, F, T];
console.log("no lates allowed:", longestStreak(history, 0));
console.log("one late allowed:", longestStreak(history, 1));
console.log("two lates allowed:", longestStreak(history, 2));
console.log(longestStreak([], 1), longestStreak([F, F], 0));

no lates allowed: { length: 3, start: 3 }
one late allowed: { length: 6, start: 0 }
two lates allowed: { length: 9, start: 0 }
{ length: 0, start: 0 } { length: 0, start: 0 }

right − left + 1 is the length of a window whose edges are both inside it. The inner while looks like a nested loop, but left only ever moves forward and never passes right, so over the whole run it moves at most n times. The total work is at most 2n pointer moves: O(n) time, O(1) space.

The general recipe for a variable window, which you will reuse in every problem of this kind:

for each right:
    add item[right] to the window summary
    while the window breaks the rule:
        remove item[left] from the summary; left++
    the window [left .. right] is now the longest valid one ending at right: record it

The longest block without a repeated ad

A radio station sells advertising slots. For a sponsor package it wants the longest block of consecutive slots in which no advert plays twice. This is the classic "longest substring without repeating characters", with ad codes instead of characters. The window's summary is now a Map from ad to the last position it played. When the ad entering on the right already played inside the window, left jumps just past that earlier play:

function longestWithoutRepeat(slots) {
  const lastSeen = new Map();
  let left = 0;
  let best = { length: 0, start: 0 };
  for (let right = 0; right < slots.length; right++) {
    const previous = lastSeen.get(slots[right]);
    if (previous !== undefined && previous >= left) left = previous + 1;
    lastSeen.set(slots[right], right);
    if (right - left + 1 > best.length) best = { length: right - left + 1, start: left };
  }
  return { ...best, block: slots.slice(best.start, best.start + best.length) };
}

console.log(longestWithoutRepeat(["MTN", "GLO", "DANGOTE", "MTN", "INDOMIE", "GLO", "PEAK", "MTN"]));
console.log(longestWithoutRepeat([..."abba"]));
console.log(longestWithoutRepeat([]).length);

{
  length: 5,
  start: 2,
  block: [ 'DANGOTE', 'MTN', 'INDOMIE', 'GLO', 'PEAK' ]
}
{ length: 2, start: 0, block: [ 'a', 'b' ] }
0

The check previous >= left is the subtle part, and the "abba" case tests it: when the last a arrives, its earlier position (0) is already outside the window (which starts at 2 after the second b), so left must not jump backwards to 1. Without that check the window would grow a duplicate b back inside. Each position is visited once by right and left only jumps forward: O(n) time, O(k) space for the Map of distinct ads.

Prefix sums: any range in one subtraction

The owner's dashboard lets managers pick any two dates and see the revenue between them. Thousands of managers, each choosing different ranges. The ranges are not neighbours, so there is nothing to slide; a loop per query would cost O(n) each.

A prefix sum array stores, at position i, the total of the first i values. It has one more entry than the data, starting with 0 (the total of nothing):

daily:          5   3   8   2   6
prefix:     0   5   8  16  18  24
index:      0   1   2   3   4   5

total of days 1..3 (0-based positions 1 to 3) = prefix[4] - prefix[1] = 18 - 5 = 13  (3 + 8 + 2)

The total of positions from to to (inclusive) is prefix[to + 1] − prefix[from]: everything up to the end of the range, minus everything before its start. Building the array is one O(n) pass; every query afterwards is O(1).

function buildPrefix(values) {
  const prefix = new Array(values.length + 1);
  prefix[0] = 0;
  for (let i = 0; i < values.length; i++) prefix[i + 1] = prefix[i] + values[i];
  return prefix;
}

function rangeTotal(prefix, from, to) {
  if (from < 0 || to >= prefix.length - 1 || from > to) throw new RangeError(`bad range ${from}..${to}`);
  return prefix[to + 1] - prefix[from];
}

const daily = [5, 3, 8, 2, 6].map((naira) => naira * 100000); // ₦5,000 is 500,000 kobo
const prefix = buildPrefix(daily);
console.log(prefix);
console.log(rangeTotal(prefix, 1, 3), rangeTotal(prefix, 0, 4), rangeTotal(prefix, 2, 2));
try {
  rangeTotal(prefix, 3, 5);
} catch (error) {
  console.log(error.message);
}

const year = Array.from({ length: 365 }, (_, i) => 3000000 + ((i * 7919) % 500000));
const yearPrefix = buildPrefix(year);
let brute = 0;
for (let d = 31; d <= 58; d++) brute += year[d]; // February: a loop of 28 additions
console.log(rangeTotal(yearPrefix, 31, 58) === brute);

[ 0, 500000, 800000, 1600000, 1800000, 2400000 ]
1300000 2400000 800000
bad range 3..5
true

The extra leading 0 is what makes the formula work for ranges that start at position 0 with no special case. Prefix sums only suit data that does not change: if a past day's revenue is corrected, every prefix after it changes too, O(n) per update. For data that changes often and is queried often, structures called Fenwick trees and segment trees do both in O(log n); they are beyond this course, but now you know what problem they solve.

Counting periods with a given total

A business account records each day's net cash flow: sales minus refunds and expenses, so some days are negative. The accountant asks how many periods of consecutive days had a net flow of exactly ₦0 (those periods are candidates for a netting-off check).

A variable window does not work here. Its shrinking rule assumed that adding a value never makes a total smaller and removing one never makes it bigger. With negative values that is false: a window that is "too big" might become exactly right after adding a refund. Prefix sums rescue it, together with the frequency counter. A period from position i to j has total prefix[j + 1] − prefix[i]. That total is the target exactly when prefix[i] = prefix[j + 1] − target. So walk the prefix sums once, and for each one ask: how many earlier prefix sums equal the current one minus the target? That is a count lookup in a Map.

function countPeriods(net, target) {
  const seen = new Map([[0, 1]]); // the empty prefix, before day 0
  let running = 0;
  let periods = 0;
  for (const value of net) {
    running += value;
    periods += seen.get(running - target) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return periods;
}

function countPeriodsBrute(net, target) {
  let periods = 0;
  for (let i = 0; i < net.length; i++) {
    let total = 0;
    for (let j = i; j < net.length; j++) {
      total += net[j];
      if (total === target) periods++;
    }
  }
  return periods;
}

const net = [3000, -3000, 5000, -2000, -3000, 4000, -4000]; // in naira, for readability
console.log(countPeriods(net, 0), countPeriodsBrute(net, 0));
console.log(countPeriods(net, 2000), countPeriodsBrute(net, 2000));
console.log(countPeriods([], 0), countPeriods([0, 0], 0));

7 7
1 1
0 3

Starting the Map with 0 → 1 counts periods that begin on the very first day, exactly as the leading 0 did in the prefix array. The order of the two lines inside the loop matters: look up before adding the current prefix, or an empty period would be counted when the target is 0. O(n) time and O(n) space, where the brute force is O(n²). This is the pattern that answers "subarray sum equals k" in interviews.

The busiest day in every week

One more window, because it shows the limit of a running total. The owner also wants, for each 7-day period, the single best day inside it (to plan staffing). A maximum cannot be "un-added" when a day leaves: if the best day leaves, which is the next best? Recomputing it is O(k) per window.

The fix, promised in Stacks and queues, is a deque of candidate positions whose revenues are in decreasing order. A day that arrives removes every weaker day from the back, because those can never be the maximum again while the newer, better day is in the window. The front of the deque is always the current maximum, and it is dropped once it slides out on the left. To keep both ends O(1) without a separate class, this version uses an array with a head index as the front, like the queue in that lesson:

function maxPerWindow(values, k) {
  const q = [];          // positions; values[q[head..]] is decreasing
  let head = 0;
  const out = [];
  for (let right = 0; right < values.length; right++) {
    while (q.length > head && values[q[q.length - 1]] <= values[right]) q.pop();
    q.push(right);
    if (q[head] <= right - k) head++; // the maximum slid out on the left
    if (right >= k - 1) out.push(values[q[head]]);
  }
  return out;
}

console.log(maxPerWindow([42, 51, 38, 60, 75, 90, 88, 40, 35, 99, 101, 97, 30, 45], 7));
console.log(maxPerWindow([5, 4, 3, 2, 1], 2), maxPerWindow([1, 2], 3));

[
   90,  90,  90,  99,
  101, 101, 101, 101
]
[ 5, 4, 3, 2 ] []

Each position is pushed once and removed at most once, so the whole run is O(n) with O(k) space, instead of O(n · k).

Failure cases

• Rows are not days. If closed days have no row, a 7-row window can span 9 days. Build a complete calendar (one row per day, 0 when closed) before sliding, or slide over timestamps instead of positions.
• Window larger than the data, or not positive. k > n has no window at all; k ≤ 0 is meaningless. Return null or throw, but decide.
• Off-by-one edges. Write down whether right is inside the window (as here) or one past it, and derive length = right − left + 1 and start = right − k + 1 from that choice. Test with k = 1 and k = n.
• Negative values in a shrinking window. "Shrink while the total is too big" assumes totals only grow when the window grows. With refunds or losses, use prefix sums with a Map instead.
• if instead of while when shrinking. One step left may not be enough to make the window valid again (the late delivery may be several positions in).
• A stale entry in the window map. In the no-repeat window, a previous position that is already left of the window must be ignored, or left jumps backwards.
• Floating-point drift. Adding and subtracting decimals thousands of times accumulates rounding errors, so a sliding total of naira values can drift away from the true sum. Integer kobo stays exact (as long as totals stay below Number.MAX_SAFE_INTEGER, about 9 × 10¹⁵).

Testing window code

Every function in this lesson has a slow, obvious twin: recompute each window, or try every pair of start and end. Compare them on many small random inputs, including window sizes from 1 up to more than the length, so the edges come up constantly:

function bestPeriod(values, k) {
  if (k <= 0 || values.length < k) return null;
  let total = 0;
  for (let d = 0; d < k; d++) total += values[d];
  let best = total;
  for (let right = k; right < values.length; right++) {
    total += values[right] - values[right - k];
    best = Math.max(best, total);
  }
  return best;
}

function bestPeriodBrute(values, k) {
  if (k <= 0 || values.length < k) return null;
  let best = -Infinity;
  for (let s = 0; s + k <= values.length; s++) {
    best = Math.max(best, values.slice(s, s + k).reduce((a, b) => a + b, 0));
  }
  return best;
}

function xorshift(seed) {
  return () => {
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) / 4294967296;
  };
}

const random = xorshift(365);
let agree = 0, nulls = 0;
for (let t = 0; t < 4000; t++) {
  const values = Array.from({ length: Math.floor(random() * 10) }, () => Math.floor(random() * 21) - 10);
  const k = Math.floor(random() * 12);
  const fast = bestPeriod(values, k);
  if (fast === bestPeriodBrute(values, k)) agree++;
  if (fast === null) nulls++;
}
console.log(`${agree}/4000 agree (${nulls} had no window)`);

4000/4000 agree (2488 had no window)

The values include negatives (from −10 to 10), window sizes include 0 and sizes larger than the list, and the output reports how many cases had no window, so you know the null path was exercised as well as the normal one.

Windows in production

• SQL window functions. Databases compute rolling totals directly: SUM(revenue) OVER (ORDER BY day ROWS BETWEEN 6 PRECEDING AND CURRENT ROW) is the fixed-size window, computed inside the database. Use RANGE with an interval over dates if rows can be missing.
• Rate limiting. "At most 100 requests per minute per user" is a sliding window over time. Limiters keep either the timestamps inside the window (exact, more memory) or counts per fixed bucket (approximate, tiny). ZudoJS's createRateLimiter in @zudojs/security is one such limiter; the security lesson uses it.
• Precomputed totals. Dashboards store daily totals (a summary table updated each night) so that range queries touch 365 rows, not millions of orders. That is prefix-sum thinking at the storage level.
• Streams. Monitoring systems compute moving averages over live data with exactly the add-entering, subtract-leaving update, because they cannot store the whole stream.

New problems to practise

function shortestRun(daily, target) {
  let left = 0;
  let total = 0;
  let best = Infinity;
  for (let right = 0; right < daily.length; right++) {
    total += daily[right];
    while (total >= target) {           // valid: try to make it shorter
      best = Math.min(best, right - left + 1);
      total -= daily[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

const naira = [200000, 150000, 400000, 50000, 600000, 100000, 350000];
console.log(shortestRun(naira, 1000000), shortestRun(naira, 5000000), shortestRun([1000000], 1000000));

3 0 1

function movingAverage(daily, k) {
  const out = [];
  let total = 0;
  for (let i = 0; i < daily.length; i++) {
    total += daily[i];
    if (i >= k) total -= daily[i - k];
    if (i >= k - 1) out.push(Math.round(total / k));
  }
  return out;
}

console.log(movingAverage([420, 510, 380, 600, 750, 900, 880, 400, 350, 990], 7));
console.log(movingAverage([100, 200], 7));

[ 634, 631, 609, 696 ]
[]

function weeksOver(daily, k, target) {
  const prefix = [0];
  for (const value of daily) prefix.push(prefix[prefix.length - 1] + value);
  let count = 0;
  for (let start = 0; start + k <= daily.length; start++) {
    if (prefix[start + k] - prefix[start] >= target) count++;
  }
  return count;
}

const daily = [42000, 51000, 38000, 60000, 75000, 90000, 88000, 40000, 35000, 99000, 101000, 97000, 30000, 45000];
console.log(weeksOver(daily, 7, 500000), weeksOver(daily, 7, 450000), weeksOver(daily, 30, 1));

2 4 0

Summary

• Sliding windows answer questions about contiguous ranges. Keep a summary of the window and update it as items enter and leave, instead of recomputing it.
• Fixed size: add the entering item, subtract the leaving one. O(n) instead of O(n · k), whatever k is.
• Variable size: right grows the window every step; left shrinks it while it breaks the rule (or, for "shortest", while it satisfies it). Each edge only moves forward: O(n).
• Prefix sums answer any range total with one subtraction after one O(n) pass; with a Map of earlier prefix sums they count ranges with an exact total, even with negative values.
• A running maximum cannot be un-added; a decreasing deque of positions gives the maximum of every window in O(n).
• Watch the edges: right − left + 1, right − k + 1, k > n, missing days, negative values, and while rather than if.

Next: Binary search as a pattern, where you search not for an item but for an answer: the smallest truck capacity, the first failing build.