The Patterns Behind Most Coding Problems

Two Ends Moving Inward, and the Proof That Nothing Is Lost

Last timeWhat a Pattern Is Actually Exploiting

Two ends moving inward answers a pair question on a sorted list in at most n minus one comparisons. Here is the discard argument that proves nothing was lost.

The list is the same one throughout, now in order.

$ $S = [1, 2, 3, 4, 4, 7, 8, 9, 11, 15]$ $

Ten values, summing to 64, with the duplicate 4 left in because it is going to

matter. And the standing question. Is there a pair of these values summing to

18?

Trying every pair costs $10 \times 9 / 2 = 45$ comparisons. Sorted order should

buy something, and the thing it buys is not a faster comparison. It is the

right to stop looking at whole blocks of pairs at once.

The sweep, on the standing question

Compare the two ends. $1 + 15 = 16$ , which is below 18, so move the low end

inward. $2 + 15 = 17$ , still below, so move it again. $3 + 15 = 18$ , which is

the answer. Three comparisons.

Two notes before the proof, because both are easy to pass over. The first is

that $7 + 11 = 18$ as well, so this list has two pairs summing to 18 and the

sweep returned the one it met first. A sweep answers whether a pair exists, not

which pair, and a statement asking for all of them is a different question with

a different candidate space. The second is the arithmetic of what those three

comparisons achieved. The first ruled out every pair containing the value 1,

which is nine pairs. The second ruled out every remaining pair containing 2,

which is eight. The third found the answer, so it ruled nothing

out. So $9 + 8 = 17$ pairs of the 45 were settled by the first two

comparisons, neither of which looked at any of them, and the third comparison

looked at exactly one pair and that pair was the answer.

Why abandoning an end is safe

That last claim is the method. Everything else is bookkeeping, so it is worth

writing out in full rather than trusting.

Index the sorted list so that $S_1 \le S_2 \le \ldots \le S_n$ , let $T$ be the

target, and let the two ends sit at $i$ and $j$ with $i < j$ . Suppose

$S_i + S_j < T$ .

Take any partner for the low end, at some index $m$ with $i < m \le j$ . Because

the list is sorted and $m \le j$ , that partner satisfies $S_m \le S_j$ . Add

$S_i$ to both sides of that, which preserves the inequality, and

$S_i + S_m \le S_i + S_j$ . The right hand side is already below $T$ by

assumption, so $S_i + S_m < T$ too. Every pair whose lower member is $S_i$ and

whose partner lies anywhere in the untouched stretch fails, so $S_i$ can be

abandoned.

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

Two Ends Moving Inward, and the Proof That Nothing Is Lost

The sweep, on the standing question

Why abandoning an end is safe

6 more paragraphs to go

This is the reading half

Read alongside