Basis Lab

Making it fast enough

Look at a problem and name the structure in its input that a fast method could exploit, then derive the handful of patterns that exploit each one, well enough to write the method correctly from the invariant rather than recall it from memory

The Patterns Behind Most Coding Problems

Most problems are one of about seven shapes. This derives each shape from the structure it exploits, and gives the invariant that makes it correct.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

  1. 01What a Pattern Is Actually Exploiting, and Why It Is Never ClevernessA 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.
  2. 02Two Ends Moving Inward, and the Proof That Nothing Is Lostopening onlyTwo 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.
  3. 03A Window That Slides, and Why Its Work Stays Linearopening onlyThe shortest adjacent stretch reaching a target, found in one pass, with the invariant that makes it correct, the move count that makes it linear, and the condition that breaks it.
  4. 04Remembering What You Have Seen, and What the Memory Costsopening onlyA 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.
  5. 05Totals You Compute Once, Then Read by Subtractionopening onlyBuild the running totals once and every question about the total of a stretch becomes one subtraction, including counts, rectangles and the stretch a window cannot find.
  6. 06Keeping Only the Best Few Without Sorting the Restopening onlyHolding 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.
  7. 07Searching the Answer Instead of the Inputopening onlyNothing 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.
  8. 08Choosing the Pattern From the Words of the Problemopening onlyA decision procedure that reads the pattern off what a statement says about its input, plus the two cases where every pattern here is the wrong answer.