The Patterns Behind Most Coding Problems
Keeping Only the Best Few Without Sorting the Rest
Last timeTotals You Compute Once
Holding the best k of a stream needs one comparison per arrival against the weakest you have kept, which costs n log k instead of n log n and k memory instead of n.
The question is the three largest values of ,
ten values totalling 64. The obvious answer is to sort the list and read the
last three off the end, and the obvious answer is correct, which is what makes
this pattern worth deriving rather than asserting. Sorting arranges all ten
values with respect to one another. The question asked for three of them and
did not ask for them in order, so nearly all of that arrangement is bought and
then thrown away.
The structure being exploited is that the answer set is small. If only three
values can ever be in the answer, then every arrival has exactly one question
to answer, which is whether it is better than the worst of the three being
held.
The weakest of the few you have kept
Hold the best three seen so far. The value that has to be available instantly
is not the best of them but the worst, because that is the one an arrival has to
beat and the one that leaves when it does. So the container is a heap whose root
is its smallest element, which reads backwards the first time and is the whole
idea. Write for how many are kept, here 3, and for how many arrive,
here 10.
| step | the arrival | the three kept | the threshold, smallest of the kept | what the arrival cost |
|---|---|---|---|---|
| 1 | 2 | 2 | none yet | an insertion, the container is not full |
| 2 | 7 | 2, 7 | none yet | an insertion |
| 3 | 11 | 2, 7, 11 | 2 | an insertion, and from here a threshold exists |
| 4 | 15 | 7, 11, 15 | 7 | beats 2, so 2 leaves and the threshold rises to 7 |
| 5 | 1 | 7, 11, 15 | 7 | one comparison and it is gone |
| 6 | 8 | 8, 11, 15 | 8 | beats 7, so 7 leaves and the threshold rises to 8 |
| 7 | 4 | 8, 11, 15 | 8 | one comparison and it is gone |
| 8 | 4 | 8, 11, 15 | 8 | the duplicate is dismissed the same way |
| 9 | 9 | 9, 11, 15 | 9 | beats 8, so 8 leaves and the threshold rises to 9 |
| 10 | 3 | 9, 11, 15 | 9 | one comparison and it is gone |
Three arrivals filled the container, three replaced the root, and four were
dismissed for one comparison each. Nothing was ever sorted.
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 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