The Patterns Behind Most Coding Problems

What a Pattern Is Actually Exploiting, and Why It Is Never Cleverness

A fast method is one piece of structure in the input being used to rule out candidates unexamined. Six structures are worth naming, and an invariant is what licenses not looking.

Every fast method looks like a trick the first time it is read and like an

inevitability the second. What changes between the two readings is not the

code. It is knowing what the method was allowed to assume.

So here is a list, and it is the same list throughout.

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

Ten values, summing to 64, the largest of them 15. And one question about it.

How many pairs of its values sum to 18?

The baseline, which is a number and not an insult

Try every pair. Each of the ten values could be the first member of a pair and

each of the nine others the second, which is $10 \times 9 = 90$ ordered pairs,

and every unordered pair has been counted twice, once in each order, so there

are $90 / 2 = 45$ pairs. Forty five is the whole of the work, and it is worth

writing down before anything else, because every method below is measured

against it.

Two of the 45 sum to 18. They are $7 + 11$ and $15 + 3$ .

FIG 1Every pair of the ten value list, examined in order

step	pair	its total	pairs tested	pairs summing to 18	what happened
1	2 and 7	9	1	0	the first value against the second
2	2 and 15	17	3	0	one short of the target, which tells us nothing at all
3	2 and 3	5	9	0	the first value is finished and nine pairs are gone
4	7 and 11	18	10	1	the first hit, at pair ten of forty five
5	15 and 3	18	30	2	the second hit, twenty pairs later
6	9 and 3	12	45	2	the last pair, and only now is the count safe to report

6 steps

Two things in this trace are worth more than the method. The existence question, is there any pair summing to 18, was answered at pair ten, which was luck: 7 sits at index one and 11 at index two, so the tenth pair tried happens to be a hit. The counting question got no such luck and could not stop early, because any unexamined pair might be another hit, which is why the answer 2 appears only on the last row. Existence and counting here have the same 45 candidates and different stopping conditions, and that difference belongs to the question rather than to the method.

FIG 2How many candidates the pair question has

: the number of values in the list
: the number of unordered pairs, which is how many candidates the pair question has

Forty five is small, and the only reason to write it down is that the same expression is sometimes not. At a hundred million values the pair count is 4,999,999,950,000,000, and at one nanosecond a pair, which is optimistic for anything that fetches from memory, that is 4,999,999.95 seconds. Divided by the 86,400 seconds in a day it comes to 57.87 days. The question did not change and the method did not change. The candidate space did, and it is the only thing that did.

The candidate space is what gets searched, not the input

The list has ten values. The pair question has 45 candidates. Those are

different numbers, and the second one is the one that decides the cost.

Change the question and the count moves a long way without the input moving at

all. A question about contiguous stretches of $A$ has $10 \times 11 / 2 = 55$

candidates, counting each single value as a stretch of one. A question about

which values to keep and which to drop has $2^{10} - 1 = 1{,}023$ non-empty

subsets. A question about the order to process them in has $10! = 3{,}628{,}800$

orderings. One list of ten numbers, and the search in front of you is 45 or 55

or 1,023 or 3,628,800 depending on nothing but the sentence that was asked.

So the first move on an unfamiliar problem is not to recall a method. It is to

say what a candidate is, count them, price one check, and multiply. That

product is the baseline, and it answers a question that growth shapes cannot:

whether a faster method is needed at all. A baseline of a million steps is

finished before anyone has read the second paragraph of the statement, and

replacing it with something clever is a way of introducing a bug. A baseline of

57.87 days is not going to be rescued by tuning.

The six structures

When the baseline is too slow, something in the input has to be used. There are

about six things worth naming, and they are the reason the handful of patterns

that follow exist at all.

FIG 3

Structure	What it says about the input	What one comparison can then rule out	The giveaway in the statement
Sorted order	the values are in order, or may be put in order	everything on one side of the value compared	sorted, ordered, ranked, non-decreasing
Adjacency	the answer is a run of neighbours rather than any subset	every stretch that is not an extension of the current one	contiguous, consecutive, substring, window
A small answer set	only a few items out of many are wanted	everything worse than the worst item currently kept	top k, k largest, best few, median
A cheap check	testing a proposed answer is easier than finding one	half of the remaining candidate answers	minimise the maximum, smallest capacity such that
Repeated subproblems	the same smaller question is asked many times over	every repeat of a subproblem after the first	in how many ways, optimal, overlapping choices
A bounded alphabet	values come from a small fixed set	the distinction between items that share a value	lowercase letters, digits, bytes, 0 to 255

Two of these are worth testing against the list above straight away, because

they cut the same 45 in different ways and by different amounts.

Sorted order. Put $A$ in order to get

$S = [1, 2, 3, 4, 4, 7, 8, 9, 11, 15]$ and compare the two ends. $1 + 15 = 16$ ,

which is below 18. The low end 1 cannot reach 18 with any partner at or below

15, which is every partner it has, so 1 is finished and nine pairs are gone in

one comparison. Then $2 + 15 = 17$ , still below, and eight more pairs go. Then

$3 + 15 = 18$ , which is a hit. Three comparisons, of which the first two ruled

out $9 + 8 = 17$ of the 45 pairs without looking at any of them, while the

third landed on the answer itself.

A bounded alphabet. The list says nothing about its alphabet, so this one is

not available here. Had the statement said the values were bytes, the most

common value question would stop being about pairs or order at all: 256

counters, one pass, and the sortedness nobody has would be irrelevant.

What an invariant actually is

The sorted sweep above reported an answer after examining three of 45 pairs.

That is a claim about 42 pairs it never touched, and the claim has to live

somewhere. The place it lives is the invariant.

An invariant is not a comment and not a true remark about a loop. It is a

statement that passes three separate checks.

It holds before the first step. It is preserved by every step, so that if it

held going in it holds coming out. And at the stopping condition it is strong

enough to force the answer.

Take the exhaustive search first, because the invariant is easiest to see where

it is least needed. Say that before pair number $t$ is examined, the running

count holds the number of pairs among the first $t - 1$ that sum to 18. Before

the loop, $t = 1$ and no pairs have been examined and the count is 0, so it

holds. Examining pair $t$ adds one to the count exactly when that pair sums to

18, so the statement holds again with $t$ one larger. The loop stops when

$t = 46$ , at which point the statement says the count holds the number of hits

among all 45 pairs, which is the answer. Three checks, three sentences.

Now the part that gets skipped. The third check is a real check and it fails

for statements that pass the first two. The count of hits is at most 45 before

the loop, is still at most 45 after every single step, and is at most 45 at the

end. It is an invariant in the sense that it never varies, and at the stopping

condition it says nothing whatever about the answer. An invariant that survives

the loop without pinning the answer is a true sentence, not a proof, and the

only way to notice the difference is to do the third check explicitly.

FIG 4The same question twice, each counting its own comparisons

python

def count_pairs_summing_to(xs, target):
    hits = comparisons = 0
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            comparisons += 1
            if xs[i] + xs[j] == target:
                hits += 1
    return hits, comparisons          # (2, 45) on A with target 18

def any_pair_summing_to(ordered, target):
    i, j, comparisons = 0, len(ordered) - 1, 0
    while i < j:
        comparisons += 1
        total = ordered[i] + ordered[j]
        if total == target:
            return (ordered[i], ordered[j]), comparisons
        if total < target:
            i += 1                    # no partner at or below ordered[j] lifts this low end
        else:
            j -= 1                    # no partner at or above ordered[i] lowers this high end
    return None, comparisons          # ((3, 15), 3) on S with target 18

The two return values to read are the comparison counts, 45 and 3. The two comments in the sweep are the whole of its correctness, and they are what the exhaustive version has no need of: it never claims anything about a pair it has not examined, which is why it is slow. Note what the sweep returns on this list. Both 7 plus 11 and 3 plus 15 sum to 18, and the sweep gives back whichever it meets first, so it answers whether a pair exists and not which pair it is. A statement asking for all pairs summing to 18 has a different candidate space and is a different problem.

The structure is not free, and on ten values it loses

Here is the step that gets left out of every short version of this subject. The

sweep needs a sorted list, and $A$ is not sorted. Sorting ten values by

comparisons costs about $10 \times \log_2 10 = 10 \times 3.32 = 33$

comparisons. Add the three the sweep uses and the sorted route costs

$33 + 3 = 36$ comparisons against 45 for trying every pair, and against the ten

it actually took to stumble on $7 + 11$ . For one existence question on ten

unsorted values, the pattern is slower than the thing it replaces.

That is not an argument against the pattern. It is the statement of when the

pattern applies. Structure is free when it arrives with the data, and cheap

when it is paid for once and then asked many questions, and expensive when it

is built to answer one. The arithmetic flips entirely with scale. At

$n = 100{,}000{,}000$ the sort costs about

$100{,}000{,}000 \times 26.6 = 2{,}660{,}000{,}000$ comparisons and the sweep

costs at most $99{,}999{,}999$ more, against 4,999,999,950,000,000 for every

pair. The sort is now roughly two million times cheaper than the thing it

enables you to skip.

FIG 5Step counts for four shapes of method, as powers of ten

	n = 10	n = 1000	n = 100,000,000
every pair	1.65	5.70	15.70
sort, then one sweep	1.52	4.00	9.42
one pass	1.00	3.00	8.00
halving what is left	0.52	1.00	1.42

Every cell is the base ten logarithm of the step count, because the raw numbers span fifteen orders of magnitude and no shared axis holds them. So 1.65 is the 45 pairs of a ten value list, 5.70 is the 499,500 pairs of a thousand, and 15.70 is the 4,999,999,950,000,000 pairs of a hundred million. The second row is n times log base two of n, which is 33 at ten and 2,660,000,000 at a hundred million. The two marked cells are the whole argument of this subject: 15.70 against 1.42 is a difference of 14.28, so more than fourteen orders of magnitude, and it is bought entirely by what the method is entitled to assume. Read the left column too. At ten values the four shapes run from 45 steps down to about 3, a little over one order of magnitude between the dearest and the cheapest, which is why structure buys nothing on small inputs and why the first question is always how large n really gets.

FIG 6How many of the 45 pairs each route looks at

The shaded stretch on the right is what a pattern is. Not a faster comparison, not a tighter loop, but 42 candidates that were never examined and a reason on paper for why they did not need to be. The mark at 10 is a warning about measurement: trying every pair found a hit at the tenth comparison on this list and in this order, and on a list where the only hit sits in the last pair it would need all 45, so a single timing of the exhaustive method measures the input it was given rather than the method.

Reading the structure off the statement

The procedure, in the order the steps actually help.

Say what a candidate is and count them. Price one check. Multiply, and look at

the number in seconds, because sometimes it ends there. If it does not,

underline what the statement promises about the input and match it against the

six structures above. Then ask the only question that produces a method, which

is what a single comparison would be entitled to rule out given that promise.

If the answer is one candidate, there is no pattern to be had and the baseline

stands. If the answer is a block of candidates whose size grows with $n$ , the

method writes itself from the invariant that justifies the discard.

That last clause is the one worth distrusting until it has been done in full.

The sorted sweep was asserted above, not proved, and the proof is a single

inequality applied exactly once. It is worth doing properly, because every

pattern that follows is the same manoeuvre with a different structure under it.

Recap

A fast method is never cleverness, it is one piece of structure in the input being used to rule out candidates without examining them, and naming that structure is the whole of the work.
The cost of the exhaustive method is the size of the candidate space multiplied by the cost of one check, so a ten value list already carries 45 pairs, 1,023 non-empty subsets and 3,628,800 orderings, and counting the candidates comes before choosing a method.
A statement earns the name invariant only when it is true before the first step, preserved by every step, and strong enough at the stopping condition to force the answer, and the third part is the one that gets skipped.

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

NextTwo Ends Moving Inward →