The Patterns Behind Most Coding Problems
Remembering What You Have Seen, and What the Memory Costs
Last timeA Window That Slides
A pair reaching a target found in one pass over an unsorted list by storing what each value needs, priced honestly against sorting first and against the bytes the table takes.
The working list is and the question is
whether two of its values reach 18. They do, since . Nothing about
the list is in order, and the brute force examines every unordered pair, which
for ten values is of them.
The previous patterns both needed something. Two ends moving inward needed
sorted order, and the window needed the candidates to be stretches of
neighbours. Here the input has neither property, and sorting it first is an
option that costs more than the search itself does afterwards. So the structure
being exploited is not in the input at all. It is in the question.
- the value at position j, read in the order the list arrives
- the target the two values have to reach, 18 for the worked question
- what the value at position j needs from somewhere earlier, and the only value that will do
- the values at every position before j, held in a table that answers membership in constant time on average
The rewrite that makes one pass possible
The same move works on any condition that can be solved for one of its two
unknowns. A difference of asks whether or has been
seen, a ratio asks about when the values are non-zero, and two
stretches with equal totals ask whether a total has been seen before, which is
the next lesson. The requirement is just that fixing one member leaves exactly
one value, or a short fixed list of values, that would complete it.
An invariant about the past
The window in the previous lesson kept a statement true about a stretch of the
input. The invariant here is of a different kind, and the difference is why one
pass is enough. Before the value at position is read, every pair whose two
members both lie before has already been tested.
That is maintained by one step. Reading and looking up in the
table tests every pair that has as its later member, all of them,
in one operation, because the lookup answers all of those questions at once.
Inserting afterwards extends the invariant to position . The
consequence is the part worth holding on to. If a pair exists anywhere in the
list, the pass reports it at its later member, so nothing ever has to be looked
up ahead of the current position, and the pass can finish there.
It is worth being precise about which pair that is, because the invariant
promises less than people assume. The pass stops at the pair whose later member
comes earliest, which is not the same as the pair whose earlier member comes
first. Ask the working list for a pair reaching 5 and three pairs qualify, the
2 at position 0 with the 3 at position 9, and the 1 at position 4 with each of
the two 4s at positions 6 and 7. The pass returns positions 4 and 6, because
that is the first position at which any pair becomes complete. If a question
asks for the earliest starting pair, or for all pairs, or for the pair whose
members are closest together, the single pass as written answers a different
question and has to be changed rather than reinterpreted.
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 planThe contentsThis 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