The Patterns Behind Most Coding Problems

A Window That Slides, and Why Its Work Stays Linear

The shortest adjacent stretch reaching a target, found in one pass, with the invariant that makes it correct, the move count that makes it linear, and the condition that breaks it.

Take the ten values $A = [2, 7, 11, 15, 1, 8, 4, 4, 9, 3]$ and ask for the

shortest stretch of adjacent values whose total is at least 15. The obvious

method tries every stretch. A stretch is fixed by where it starts and where it

ends, so a list of $n$ values holds $n(n+1)/2$ of them, which at $n = 10$ is

$10 \times 11 / 2 = 55$ , and each has to be totalled before it can be judged.

The method below reads the list once, moves an index 17 times in total, and is

correct for a reason that fits in a sentence.

The structure being exploited is adjacency. The candidates are not arbitrary

subsets of the list but stretches of neighbours, so a candidate is fixed by two

indices rather than by one decision per element, and once the right index is

fixed the only freedom left is where the stretch starts. That is a small enough

space to walk through directly.

FIG 1The shortest valid stretch, and the smaller question it is built from

: the value at index t of the list, indexed from one in this figure and from zero in the code below
: the target a stretch has to reach, 15 for the whole of this lesson
: the total of the stretch that starts at i and ends at j
: the length of the shortest valid stretch that ends at j, and undefined when none does
: the answer being asked for, the shortest valid length anywhere in the list

The middle quantity is the one that makes the lesson work, and it is not in the question as asked. Fixing the right end turns a search over 55 stretches into ten searches with one free index each, and the last equality says that is not a loss, because every stretch ends somewhere, so the smallest of the ten answers is the answer. A method that produces each L_j cheaply, in the order the list arrives, has answered the whole question without ever holding two candidates at once.

What the window keeps true

The window is a pair of indices $i$ and $j$ and the running total

$S(i,j)$ of the values between them. One step takes in the value at the next

index $j$ , and then advances $i$ for as long as the stretch would still reach

the target without the value at $i$ . The invariant afterwards is that the window

is the shortest valid stretch ending at $j$ among the stretches that start at

$i$ or later. It holds because the advance stopped, which says the stretch from

$i + 1$ to $j$ does not reach the target, and with non-negative values a later

start can only have a smaller total.

That half is usually all that gets written down, and on its own it does not

justify anything, because stretches starting before $i$ were never examined at

this right edge. The missing half is the discard argument. The left edge only

left index $i$ because the stretch from $i + 1$ to some earlier right edge $j'$

already reached the target, so at that moment a valid stretch of length at most

$j' - i$ was recorded. Every stretch starting at $i$ and ending at $j \ge j'$

has length $j - i + 1$ , which is at least $j' - i + 1$ , which is larger than

the length already recorded. So nothing that could win was discarded. The two

halves together are what makes the minimum of the recorded lengths the minimum

over all 55 stretches.

The previous pattern in this course moved two indices as well, inward from the

two ends of a sorted list. The difference is worth naming, because the two get

confused. There, the order of the values was the structure, the ends moved

towards each other, and a comparison killed a whole block of pairs at once.

Here the list is in whatever order it arrived in, both indices move the same

way, and what is being exploited is that a candidate is a stretch of

neighbours. The only property the two share is that neither index ever reverses,

and that alone is what both cost arguments are made of.

FIG 2One pass over the ten values with a target of 15

step	right edge	value entering	window	window total	shortest valid so far	what happened
1	0	2	0 to 0	2	none	below the target, and there is nothing to drop
2	1	7	0 to 1	9	none	9 minus the 2 is 7, which is below 15, so the left edge stays
3	2	11	1 to 2	18	2	20 minus the 2 is 18, still valid, so the left edge moves once
4	3	15	3 to 3	15	1	the left edge moves twice, dropping the 7 and the 11; this is the answer
5	4	1	3 to 4	16	1
6	5	8	3 to 5	24	1	24 minus the 15 is 9, below the target, so nothing can be dropped
7	6	4	3 to 6	28	1
8	7	4	5 to 7	16	1	the left edge moves twice again, dropping the 15 and the 1
9	8	9	6 to 8	17	1
10	9	3	7 to 9	16	1

10 steps

The window total is the total of the window shown beside it, so row four reads 15 because the stretch is the single value 15. The answer is a stretch of length one, and the reason is worth noting rather than hiding: the largest single value in the list is 15 and the target is 15, so one value suffices. Nothing in the method special-cases that. At the third right edge it was holding the length-two stretch 7 and 11, total 18, and the fourth step replaced it. Five of the ten steps move the left edge not at all, two of them move it twice, and the remaining three move it once, which is the seven moves the next figure prices.

Why the work is linear

The shrink step is written as a loop inside a loop, which is the shape that

normally means $n^2$ . Here it does not, and the argument is not about any one

step. Each index is taken in by the right edge exactly once, which is $n$

moves. Each index is passed by the left edge at most once, because the left

edge never decreases, which is at most $n$ more. Nothing else in the loop

depends on the size of the window.

The lesson stops here

6 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

A Window That Slides, and Why Its Work Stays Linear

What the window keeps true

Why the work is linear

6 more paragraphs to go

This is the reading half

Read alongside