The map: from a prompt to a pattern

How do I know which algorithm to use?

Read the prompt for two things, in order. First the shape of the input: a row of numbers, a string, a sorted row, a list of ranges, a linked list, a tree, a grid, a graph given as edges, a stream, a set of words. That alone cuts the twenty patterns down to about five, because most patterns live on exactly one shape. Then the shape of the question: one contiguous run, a pair, the k-th or top k, every arrangement, a count or a best value over choices, fewest steps, cheapest path, an order that respects dependencies, are these connected, or design a structure with fast operations. The pair usually names one pattern. Where it leaves two, one further question separates them, and this page lists those questions shape by shape.

How do I recognise a dynamic programming problem?

Three things show up together. The question asks for a count of ways or a best value rather than for the items themselves. A candidate answer is built out of a sequence of small decisions, so you can say what one decision is. And a plain recursion over those decisions visibly asks the same question twice, which is what a table removes. The input size confirms it: a few hundred to a few thousand is room for a table over one or two indices, while a bound of twenty says the answer is exhaustive search instead. If you can prove one choice is always safe to take, you do not need the table at all, and that is greedy.

What if two patterns both seem to fit?

Sometimes both really do work, and then the only mistake is silence. Static connectivity can be answered by a depth-first walk or by union-find, top k by a heap or by a sort, reachability by BFS or by DFS, and a decision tree by a table or by a memoised recursion. Say both out loud with their costs, say which you are taking and why, and start typing. The other case is a pair where the two look alike and only one is correct, such as a sliding window against prefix sums when the numbers can be negative. Those are on the look-alikes page, each with the question that separates them.

What do the input constraints tell me about the intended solution?

They tell you what your answer is allowed to cost, which rules out most of the catalogue before you have thought about the problem. A bound of about twenty is an instruction to enumerate, because two to the twentieth is around a million. A bound in the low hundreds leaves room for a cubic loop, which is where interval DP lives. A few thousand says quadratic. A hundred thousand and above says everything has to be a sort, a heap, a binary search, a hash pass or a single scan. And a bound near a billion is almost never a length: it is a value you binary search over.

How long should recognition take in an interview?

The first three minutes of a forty-five minute round, running in parallel with reading the prompt aloud. You are not trying to have the solution by minute three. You are trying to have said the shape of the input, the shape of the question, and what the constraint line allows, because those three sentences are what the pattern falls out of, and they are gradeable even when the pattern does not arrive. If you are still unsure at minute five, say the brute force and name the repeated work in it. Every pattern on this site is the answer to some repetition.