Card 01/ 07
Choosing a Pattern by the Properties of the Problem
What the input is, what the question asks for, and what the values allow: three properties that point to one pattern, in a fixed order.
A pattern is chosen by testing the problem for the properties that pattern needs, in a fixed order: first the structure of the input, then the shape of the question, then what the values allow. A cue is one of those properties, something the problem has, such as items with a start and an end or values that are never negative; a keyword is a word the statement happens to use, such as "largest" or "sorted", and it can point at the wrong pattern. Structure comes first because it rules out the most: a problem about a linked list or a tree has only a few patterns left to consider, whatever its question says. The decision below reads top to bottom, and the first condition the problem meets names its pattern.
When The input is a linked list, and the question asks about a loop, the middle, or a position counted from the end
, chooseWhen The input is a linked list that must be reordered, reversed whole, in a stretch or in groups, without a copy
, chooseWhen The input is a tree, and the answer at a node comes from the path above it, the subtree below it, or its level
, chooseWhen The input is a map of cells, and movement goes between cells that touch
, chooseWhen Things are linked in pairs but no graph, tree or map is given, and the question asks for the fewest steps, an order that respects prerequisites, or groups joined through shared details
, chooseWhen Each item has a start and an end, and the question asks about overlaps, gaps, or how many are open at once
, chooseWhen The question asks for the k largest, smallest or closest items taken from anywhere in the input, not from one contiguous run; the next item across several sorted sources; or the middle of values that keep arriving
, chooseWhen The answer is the point where a yes-or-no test changes, false up to it and true after it, over positions or over possible answers
, chooseWhen The question asks, for each item, for the nearest item on one side that is larger or smaller
, chooseWhen The question asks for the best contiguous run of a fixed length, or the longest or shortest contiguous run when growing a run can only move its condition one way, as sums of values that are never negative do
, chooseWhen The question asks about sums of contiguous runs of any length when values can be negative, or asks many range-sum questions of data that does not change
, chooseWhen The input is sorted and the question asks for pairs or a split of it, or it asks for three or more items that together meet a target, after sorting
, chooseWhen Each item is a small fixed set of yes-or-no flags, or every value appears twice except one and the extra memory must stay constant
, chooseWhen The question is about single items in an unsorted input, such as whether one was seen before, which one completes a pair, how often each occurs, or which are equal under some key, and memory in proportion to the input is allowed
, choose
Otherwise None of these: write the brute force and follow the six steps of Solving an Unseen Problem; the step that dominates its cost usually names the pattern.
Several branches sit close together, and each pair is kept apart by a word in its condition. Fast and slow pointers find something in a list, and reversal reorders it. A grid is a map you are given, and graph modelling starts from links nobody drew. A heap takes the best items from anywhere, and a sliding window from one contiguous run. Binary search finds a single point where a test changes, and two pointers find pairs. A sliding window needs a fixed length or a condition that moves one way, and prefix sums handle any length with negative values, or many questions of the same data. Bit manipulation keeps the memory constant, and a hash map spends memory in proportion to the input.
The properties are tested, not read off: "closest" in a problem about campsites says nothing until the problem shows whether the closest come from anywhere, which picks a heap, or from one sorted run, which picks a binary search and a window. When no branch fits, the brute force is still a correct answer, and costing it, as the Solving an Unseen Problem topic does, usually shows a step whose waste one of these patterns removes. The decision is a guide to the first pattern to try, not a proof: a problem can meet two conditions, and then the higher one is tried first.
← → move through sections and cards