The Patterns Behind Most Coding Problems

Searching the Answer Instead of the Input

Nothing in the input is sorted, so halve the range of possible answers instead, and prove the check is monotone before trusting a word of it.

Every pattern so far has leaned on something the input already was. Sorted, so

two ends could move inward. Adjacent, so a window could slide. Streaming, so

only the best few needed holding. Take all of that away and one move is left,

and it is the one that feels like cheating the first time it is seen.

The move has a tell in the wording of a problem. It is the questions that ask

for a smallest largest, or a largest smallest, or the least capacity, or the

earliest time by which something is possible. Those are not asking for an item

in the input at all. They are asking for a number, and the number has a range

it must lie in, and that range is a stretch of ordinary numbers whatever state

the input is in.

Here is the question this lesson works, on the list the whole course uses.

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

Cut $A$ into three contiguous parts and make the largest part total as small as

you can. The parts have to be runs of neighbours, so the order of $A$ is fixed

and sorting is not available. The totals are 64 altogether, since

$2 + 7 + 11 + 15 + 1 + 8 + 4 + 4 + 9 + 3 = 64$ , and the largest single value is

15, both of which matter shortly.

At ten items the direct approach is fine. Three contiguous parts are fixed by

two cut points chosen from the nine gaps between neighbours, which is

$\binom{9}{2} = 36$ arrangements, each priced in constant time from running

totals. Thirty-six is nothing. But the count is $\binom{n-1}{2}$ , which is

about $n^2/2$ , and at the large size this course uses, $n = 100{,}000{,}000$ ,

that is $99{,}999{,}999 \times 99{,}999{,}998 / 2$ , almost exactly

$5 \times 10^{15}$ arrangements. So the direct approach is not a method, it is

a bound.

Turn the smallest into a yes or no

Write $t$ for a candidate answer, a proposed cap on how large any one part is

allowed to total, and $k$ for the number of parts, here $k = 3$ . Define a

check.

$\text{fits}(t)$ is true when $A$ can be cut into at most $k$ contiguous parts

with every part totalling at most $t$ .

The answer we actually want is the smallest $t$ for which $\text{fits}(t)$ is

true. That restatement is the whole move. Finding a minimum has been traded for

asking a yes-or-no question about a named number, and named numbers come in

order whether or not anything in $A$ does.

Why the trade is worth making is worth one sentence of its own, because it is

the same reason this pattern exists at all. In the original question the cap

and the cut points were both unknown and had to be chosen together, which is

what made the search space the $\binom{n-1}{k-1}$ arrangements. Naming $t$

fixes one of the two unknowns, and once the cap is fixed the cut points stop

being a choice: there is a best place to cut, and finding it is a single sweep.

Checking is easier than finding because checking is given the hard half of the

answer for free.

FIG 1Every candidate cap, and what the check says about it

This picture is the thing being halved, and it is in order because it is a stretch of whole numbers. The two ends are chosen so the picture is true before any work is done: a cap of 14 cannot hold the element 15 in a part of its own, so no split exists at any number of parts, and a cap of 64 is the whole total, which one part satisfies and three certainly do. Everything the search does is move the boundary between the two spans, and the answer is the leftmost value in the right-hand span, 24, which is reached by the parts [2, 7, 11] totalling 20, [15, 1, 8] totalling 24, and [4, 4, 9, 3] totalling 20.

Checking one candidate in a single pass

The check has to be cheap or none of this is worth anything. Walk left to

right, adding the next value to the current part while it still fits under $t$ ,

and starting a fresh part the moment it does not. Count the parts. If the count

is at most $k$ , the candidate passes.

The step everybody skips is why that greedy filling is allowed. It is not

obvious: refusing to overfill a part is a local decision, and the question is

global. The argument is an exchange. Let $g_1$ be the position of the greedy

method's first cut and $c_1$ the first cut of any valid split into parts all

within $t$ . The greedy part ran as far right as it could without exceeding $t$ ,

so $g_1 \ge c_1$ . Now the greedy method faces the suffix beginning after

$g_1$ , which is a suffix of the one the other split faces after $c_1$ , and a

shorter suffix never needs more parts than a longer one under the same cap.

Repeat the argument at every cut and the greedy count is never larger than the

other split's count. So the greedy count is the minimum, and comparing it with

$k$ is exactly the right test.

The lesson stops here

5 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

Searching the Answer Instead of the Input

Turn the smallest into a yes or no

Checking one candidate in a single pass

5 more paragraphs to go

This is the reading half

Read alongside