Techniques Keep a running answer as a range moves

Sliding window

Add on the right, drop on the left.

A gzip-compressed page was squeezed by finding repeats within the previous 32K bytes, a window that slides along as the compressor reads. Search a static site built with Pagefind, and each result’s excerpt is the densest run of matching words, found by sliding a fixed window across the page. You meet windows every day without seeing them. Let’s watch one find the part of a product review that mentions what a shopper cares about, and see why it never has to read the same word twice.

TypeScriptGoOne review excerpter, two implementations.

01 / The idea

Show the part that mentions it.

A shopper looking at camping lanterns taps the filters “battery” and “bright.” Every review in the list should show the passage where it talks about both, not its first two lines. For a 34-word review, the passage could start at any word and end at that word or any later one: 595 possible excerpts. Checking each one reads the same words again and again.

A sliding window reads them once. It keeps a run of consecutive words between a left edge and a right edge, and a summary of what is inside: how many search terms, or how many of each. Moving the right edge adds one word to the summary. Moving the left edge takes one out. Neither edge ever moves backwards.

That is the trick inside DEFLATE, the compression behind gzip, which looks for repeats “within the previous 32K input bytes.” It is how TCP describes the data a receiver will accept, a window with a left and a right edge. And it is what Pagefind does to choose search result excerpts: a window of words slides across the page, adding the score of the word entering and subtracting the word leaving.

02 / Name the rule

Move one edge at a time, and never move back.

A fixed window keeps its width. To find the busiest six words, add the next word on the right and drop the oldest on the left, so each step adds one to the count of search terms if the entering word is one, and subtracts one if the leaving word is, instead of recounting all six.

A variable window changes width to satisfy a condition. For the shortest excerpt that mentions every term, grow the right edge until the window covers all the terms. Then shrink the left edge for as long as it still covers them, recording each shorter excerpt. When a drop uncovers a term, grow the right edge again.

The rule that makes this work: if a window covers every term, so does any larger window around it. So once the left edge has moved past a word, no excerpt starting there can end sooner than one already seen, and the left edge never needs to go back.

Why can’t shrinking skip the best excerpt?Every shortest excerpt gets its turn

Take the shortest excerpt, from word a to word b. The right edge reaches b at some point. If the left edge is still at or before a, the window covers every term, so it shrinks until it passes a, recording the excerpt from a to b on the way. Could the left edge already be past a when the right edge reaches b? Only if an earlier window ending before b covered every term while starting at a, which would be shorter than the shortest. So it cannot.

The same argument fails for sums that can go down. A window that sums to at least 100 can grow into one that sums to less if the next value is negative, so “shrink while it still qualifies” stops being safe. Windows that shrink on a sum need values that are never negative; a window of fixed width does not care.

03 / Follow one operation

A lantern review, searched for “battery” and “bright.”

The review has 34 words: “The lantern is bright enough for the whole tent. The battery lasted three nights, and the hook holds it upside down. Bright mode drains the battery fast, but the low mode is still bright.”

Before you watch, predict which excerpt wins and how many edge moves it takes to be sure. The animation replays every recorded move. Try it lets you paste another review and pick your own terms.

Playback controls

Sliding window

Grow the right edge, shrink the left.

window: words 0 to 0 · 1 word · covers 0 of 2 terms

0 the
1 lantern
2 is
3 bright
4 enough
5 for
6 the
7 whole
8 tent
9 the
10 battery
11 lasted
12 three
13 nights
14 and
15 the
16 hook
17 holds
18 it
19 upside
20 down
21 bright
22 mode
23 drains
24 the
25 battery
26 fast
27 but
28 the
29 low
30 mode
31 is
32 still
33 bright

in the window · best so far · bold search term

01/ 05

Shortest excerpt: battery + bright

Move one edge at a time.

Add “the” at the right edge. Still 0 of 2 terms.

Reduced motion: choose a scene to see its completed state.

Read this scene

Add “the” at the right edge. Still 0 of 2 terms.

Window: words 0 to 0.

Try the example by reading

A 34-word review of a camping lantern is searched for the shortest excerpt mentioning both battery and bright. The right edge adds words until the window holds both, at words 0 to 10. The left edge then drops the, lantern, and is, recording shorter excerpts, and dropping bright leaves it uncovered. The right edge adds words again until another bright and another battery come in, and shrinking finds words 21 to 25, “Bright mode drains the battery,” five words. In all, the edges moved 60 times over 34 words. A fixed window of six words then slides across the review, adding one word and dropping one each step, and finds that “hook holds it upside down. Bright” has the most mentions of battery, bright, or hook: two.

Excerpt a review

Find the shortest excerpt that mentions every term, or the busiest run of a fixed number of words. Then open the steps to see each edge move.

Search the lantern review, or paste your own. Try battery, bright, hook, then switch to the busiest six words.

Words: 34
Excerpt: —
Edge moves: 0
Possible excerpts: 595

Inspect the last search move by move

The answer above is already complete. Stepping replays the moves the search recorded; it does not search again.

Before the search. 34 words. Choose search terms and a question.

Choose terms to start sliding a window.

0 the
1 lantern
2 is
3 bright
4 enough
5 for
6 the
7 whole
8 tent
9 the
10 battery
11 lasted
12 three
13 nights
14 and
15 the
16 hook
17 holds
18 it
19 upside
20 down
21 bright
22 mode
23 drains
24 the
25 battery
26 fast
27 but
28 the
29 low
30 mode
31 is
32 still
33 bright

in the window · best so far · bold search term

Words are runs of ASCII letters and digits, with apostrophes inside them, so accented letters split words. Terms must be single words. Counts are edge moves, not time.

Watch restarts when you return. Step through keeps your selected step. Try it keeps your review and terms while you stay on it.

04 / Read the shape

Two windows, one pass each.

Basic form is the two windows with nothing about reviews in them: bestFixedWindow over numbers and shortestCovering over strings. In the wild wraps them in ReviewExcerpts, which splits the review into words once, normalizes search terms, and turns window positions back into the exact text of the review, punctuation and all.

The busiest excerpt is the fixed window run over a list of ones and zeros: one where a word is a search term. The shortest excerpt is the variable window run over the words themselves.

Read in

Compare with

Two windows. A fixed one keeps a running sum as it slides, adding one value and dropping one. A variable one grows its right edge until it covers every required item, then shrinks its left edge while it still does, using counts. Pass an array to record every move.

TypeScriptReading

excerpts.ts

export type Move = {
	kind: 'add' | 'drop' | 'best';
	/** The window after the move: positions left up to, not including, right. */
	left: number;
	right: number;
	/** The window's running sum, or how many required items it covers. */
	score: number;
};

// The window of exactly `width` values with the largest sum; the earliest one on a tie.
// Each value enters the window once and leaves it once, so the sum is never recounted.
export function bestFixedWindow(
	values: readonly number[],
	width: number,
	moves?: Move[]
): { start: number; sum: number } | null {
	if (!Number.isSafeInteger(width) || width < 1)
		throw new RangeError('width must be a whole number of at least 1');
	if (width > values.length) return null;
	let left = 0;
	let sum = 0;
	let best: { start: number; sum: number } | null = null;
	for (let right = 0; right < values.length; right++) {
		sum += values[right];
		moves?.push({ kind: 'add', left, right: right + 1, score: sum });
		if (right + 1 - left > width) {
			sum -= values[left];
			left++;
			moves?.push({ kind: 'drop', left, right: right + 1, score: sum });
		}
		if (right + 1 - left === width && (best === null || sum > best.sum)) {
			best = { start: left, sum };
			moves?.push({ kind: 'best', left, right: right + 1, score: sum });
		}
	}
	return best;
}

// The shortest run of items that contains every required item at least once; the earliest
// on a tie. Grow the right edge until the window covers everything, then shrink the left
// edge while it still does. Counts, not a set, track what is inside, because an item can
// appear in the window more than once.
export function shortestCovering(
	items: readonly string[],
	required: readonly string[],
	moves?: Move[]
): { start: number; end: number } | null {
	const need = new Set(required);
	if (need.size === 0) return { start: 0, end: 0 };
	const counts = new Map<string, number>();
	let covered = 0;
	let left = 0;
	let best: { start: number; end: number } | null = null;
	for (let right = 0; right < items.length; right++) {
		const entering = items[right];
		if (need.has(entering)) {
			const count = (counts.get(entering) ?? 0) + 1;
			counts.set(entering, count);
			if (count === 1) covered++;
		}
		moves?.push({ kind: 'add', left, right: right + 1, score: covered });
		while (covered === need.size) {
			if (best === null || right + 1 - left < best.end - best.start) {
				best = { start: left, end: right + 1 };
				moves?.push({ kind: 'best', left, right: right + 1, score: covered });
			}
			const leaving = items[left];
			if (need.has(leaving)) {
				const count = counts.get(leaving)! - 1;
				counts.set(leaving, count);
				if (count === 0) covered--;
			}
			left++;
			moves?.push({ kind: 'drop', left, right: right + 1, score: covered });
		}
	}
	return best;
}

GoAlongside

excerpts.go

// Move records one change to the window: positions Left up to, not including,
// Right. Score is the running sum, or how many required items the window covers.
type Move struct {
	Kind  string `json:"kind"`
	Left  int    `json:"left"`
	Right int    `json:"right"`
	Score int    `json:"score"`
}

// BestFixedWindow finds the window of exactly width values with the largest sum;
// the earliest one on a tie. Each value enters the window once and leaves it once,
// so the sum is never recounted. ok is false when width is longer than values.
func BestFixedWindow(values []int, width int, moves *[]Move) (start, sum int, ok bool, err error) {
	if width < 1 {
		return 0, 0, false, errors.New("width must be a whole number of at least 1")
	}
	if width > len(values) {
		return 0, 0, false, nil
	}
	left, running := 0, 0
	for right, value := range values {
		running += value
		record(moves, "add", left, right+1, running)
		if right+1-left > width {
			running -= values[left]
			left++
			record(moves, "drop", left, right+1, running)
		}
		if right+1-left == width && (!ok || running > sum) {
			start, sum, ok = left, running, true
			record(moves, "best", left, right+1, running)
		}
	}
	return start, sum, ok, nil
}

// ShortestCovering finds the shortest run of items that contains every required
// item at least once; the earliest on a tie. Grow the right edge until the window
// covers everything, then shrink the left edge while it still does. Counts, not a
// set, track what is inside, because an item can appear in the window more than once.
func ShortestCovering(items, required []string, moves *[]Move) (start, end int, ok bool) {
	need := map[string]bool{}
	for _, item := range required {
		need[item] = true
	}
	if len(need) == 0 {
		return 0, 0, true
	}
	counts := map[string]int{}
	covered, left := 0, 0
	for right, entering := range items {
		if need[entering] {
			counts[entering]++
			if counts[entering] == 1 {
				covered++
			}
		}
		record(moves, "add", left, right+1, covered)
		for covered == len(need) {
			if !ok || right+1-left < end-start {
				start, end, ok = left, right+1, true
				record(moves, "best", left, right+1, covered)
			}
			if leaving := items[left]; need[leaving] {
				counts[leaving]--
				if counts[leaving] == 0 {
					covered--
				}
			}
			left++
			record(moves, "drop", left, right+1, covered)
		}
	}
	return start, end, ok
}

func record(moves *[]Move, kind string, left, right, score int) {
	if moves != nil {
		*moves = append(*moves, Move{kind, left, right, score})
	}
}

Reading the TypeScriptA Map of counts

counts is a Map from term to how many copies are inside the window, and covered counts terms whose count is above zero, so checking coverage is one comparison instead of a scan of the map.

Positions are half-open: a window from left up to, not including, right. An empty window is left === right, and its width is right - left with no off-by-one.

Reading the GoZero values do the counting

counts[entering]++ works on a missing key because a map returns the zero value, so there is no “first time” branch. ShortestCovering returns the window with an ok flag instead of null.

Tokenize works on bytes, so non-ASCII letters separate words exactly as they do in TypeScript, and slicing the review by byte offsets gives the same excerpt text.

What would I normally use in application code?Usually a few lines, sometimes a query

Neither language ships a sliding window helper; a loop with two indexes is the idiom. For search excerpts on a static site, Pagefind already picks the densest region for you.

For numbers over time, let the system that stores them do it. Prometheus range selectors such as [5m] hand functions like avg_over_time the samples in a trailing window, so a dashboard never downloads the raw series to average it.

05 / Try a decision

A set or a count?

Tracking which terms are inside the window sounds like a job for a set. Decide what happens when a term appears twice before the feedback tells you.

06 / Follow the cost

Sixty moves, not 595 excerpts.

Here is every operation at a glance, with n words, L characters, and t distinct terms. The rest of this section is about why the first two rows are linear.

Review excerpts: time and extra space per operation
Operation	Time	Extra space	What it assumes
Busiest fixed-width excerpt	`O(n)`	`O(n)`	Each word enters the window once and leaves once. The running count changes by one entering and one leaving value per step. The window keeps one count; the excerpter first builds an n-entry list of ones and zeros for it to slide over.
Shortest excerpt with every term	`O(n) average`	`O(n + t)`	The right edge moves n times and the left edge at most n times. Each move is one map lookup and one count change; t is the number of distinct terms. The window keeps t counts; the excerpter first copies the n words into a plain list.
Split a review into words	`O(L)`	`O(n)`	One pass over L characters, done once per review and reused for every search.
Check every excerpt instead	`O(n²) excerpts`	`O(t)`	n(n + 1) / 2 possible excerpts: 595 for a 34-word review. Stopping early at the first covering end still revisits words over and over.
Answer many different ranges	`O(n) once, O(1) each`	`O(n)`	For sums over arbitrary ranges, prefix sums beat sliding: store running totals once, then subtract two of them.

In the animation, the shortest excerpt took 34 moves of the right edge and 26 of the left: 60 moves for 34 words. The right edge moves exactly once per word. The left edge never passes the right, so it moves at most once per word too. That bound, at most 2n moves, holds for any review and any terms. Checking every excerpt instead means n(n + 1) / 2 of them, 595 here.

On a longer text, the gap is the whole point. In this lesson’s model, 1,000 random words drawn from a 15-word vocabulary needed 1,956 edge moves to find the shortest excerpt with three terms. A search that restarts from each word and stops at the first excerpt covering all three still looked at 33,832 words, and 5,000 such words pushed that to 131,839 against 9,981 moves. The restart search stops early because the terms are common; with rarer terms it approaches n² / 2.

These are counts, not timings. A 34-word review is fast either way. The sliding window matters when there are many long reviews and the shopper changes filters often.

07 / Give it a real job

Decide what counts as a word before you slide over them.

In a real store, each review is tokenized once when it loads, and every filter change runs one window per review over words already split. The window finds positions; the component turns them into text and highlights the terms.

What the excerpter leaves out is a decision too. It matches exact words, so “batteries” does not count as “battery.” It treats accented letters as separators, which is wrong for a review in French. It returns the shortest excerpt even when the terms are far apart and that excerpt is most of the review. Real search tools stem words, segment text per language, and cap excerpt length.

Build UIs?See the window behind the search excerpts you already ship, and the day you write one.

Where it already is in your components

If your docs or blog use Pagefind for search, every result excerpt came from a sliding window. Its calculate_excerpt_region scores each word, slides a window of the excerpt length across the page by adding the word that enters and subtracting the word that leaves, and keeps the densest start. When several neighboring starts tie, it picks the middle one.

Compressed responses are the other everyday case. The browser inflates every gzip response by copying earlier bytes from within the last 32K, the window DEFLATE compressed against.

When you have to own it

Now picture the connection badge in the corner of a video call. Your app pings the server, times each round trip, and the badge shows the average over the last 30 seconds with a label: Good, Fair, or Poor. Pongs land whenever the network lets them, several a second on a good line and none during a stall, so the last 30 seconds is not a fixed number of samples. Your framework will not keep that average for you.

This is the fixed-width window with time as the width. Keep the samples in arrival order with a running sum. Each pong goes on the right and adds its round trip. Each read drops from the left every sample older than 30 seconds and subtracts it. Every sample comes in once and goes out once, so a read is O(1) amortized, and you never add up the whole history again.

Then it gets real. Say your app stops pinging while the tab is hidden. Come back a minute later and every sample is older than the window, so the next read has to empty it and show “No recent data”, not the average from before you left. A window that only moves when a pong arrives never lets those samples go, so the badge reads on a one-second timer and again when the tab becomes visible. A pong updates the window, not the screen, and the badge renders once a second, not once per pong.

The average of the last ten pings. Each pong adds on the right, the eleventh drops the oldest from the left, and one running sum means nothing is added up twice.

ReactAlready in your code

PingAverage.tsx

import { useEffect, useState } from 'react';

type Connection = { onPong(listener: (rttMs: number) => void): () => void };

const COUNT = 10;

export function PingAverage({ connection }: { connection: Connection }) {
	const [average, setAverage] = useState<number | null>(null);

	useEffect(() => {
		// The window: the last ten round trips, oldest first, and their sum.
		const recent: number[] = [];
		let sum = 0;
		return connection.onPong((rttMs) => {
			// Add on the right.
			recent.push(rttMs);
			sum += rttMs;
			// Drop on the left once there are eleven. For ten numbers, shift is fine.
			if (recent.length > COUNT) sum -= recent.shift()!;
			// One addition and one subtraction per pong. Nothing is re-added.
			setAverage(sum / recent.length);
		});
	}, [connection]);

	return (
		<p>
			{average === null
				? 'Waiting for the first ping'
				: `${Math.round(average)} ms, last ${COUNT} pings`}
		</p>
	);
}

08 / Make the call

Ask whether the answer is a contiguous run.

Reach for a sliding window when the answer is a contiguous run of a sequence, the summary can be updated by adding one item and removing one, and growing a window can only help the condition. Excerpts, the busiest stretch, the longest run within a budget, and counts over the last n items all fit.

Look elsewhere when the question changes. Items that need not be next to each other: count them with a hash map. Many different ranges asked at once: prefix sums answer each in O(1), and with non-negative values a binary search over them finds where a budget runs out. Sums that can go negative: shrinking is no longer safe, so use prefix sums with an ordered structure. A stream you cannot read twice: keep the window’s items in a ring buffer so the left edge knows what to subtract.

09 / Take the idea with you

Explain it without saying “sliding window.”

“I keep a stretch of the sequence between two markers and a tally of what is inside. I move the right marker to take in the next item, and the left marker to let go of the oldest, updating the tally each time. Neither marker goes back, so every item comes in once and goes out once.” That describes the mechanism. The name is what you call it in a review.

Before moving on, explain three things without the name: why the left edge never moves back, why the window counts copies of a term instead of remembering it in a set, and why a sum with negative values breaks shrinking. Then find a loop in your own code that recomputes a total for every position, and decide whether one running total would do.

Connections to follow nextRelated lessons

Hash map holds the counts that tell the window what it covers.
Ring buffer keeps a window’s items when the sequence cannot be read again.
LZ77 compression, in Applied algorithms, matches text against a window of what came before.