Skip to content
algo150Open the app
Patterns

42 problem-solving patterns for coding interviews

Most interview problems are one of a few dozen methods in disguise. These are the 42 that the 150 problems use, in 6 groups, in the order they are taught.

Practice spotting them

Foundations

Remember what you have seen, in a shape that makes the next question take one step.

  • Hash set membershipUse it when all you need to know about a value is whether you have it, not where it was or how many times it came.
  • Hash map lookupUse it when yes or no is not enough: you need something kept beside each item, such as its position or its partner.
  • Frequency countingUse it when the answer depends on how many times each value appears, and where the values stand does not matter.
  • Prefix and suffix passesUse it when the answer at each position needs a total or a best of everything before it and of everything after it.
  • Length-prefixed encodingUse it when several strings must become one string and come back exactly, and any character may appear in them, so no dividing mark is safe.
  • Last-in, first-out stackUse it when the newest item still waiting is the only one that matters now, and older items must wait until it is finished or removed.
  • Monotonic stackUse it when every item needs the nearest item before or after it that is larger, or smaller, than itself.
  • Linked list pointer rewiringUse it when the answer is the same nodes in a different order or grouping, built by changing links as you walk the list.
  • Fast and slow pointersUse it when the question is about a place in a chain of unknown length: its middle, a spot counted from the end, or whether it loops.
  • Purpose-built data structureUse it when the task lists operations to support and wants each one fast, and no single ready-made structure answers all of them.

Search & scan

Move one or two positions across the input so that nothing is looked at more than a few times.

  • Opposing two pointersUse it when the answer is about a pair of positions, and looking at both ends tells you which end to leave behind: they start apart and move toward each other.
  • Fixed-size sliding windowUse it when the stretch has a given length, such as any k days in a row, and you track a total or a count, not the largest value.
  • Variable sliding windowUse it when you want the longest or shortest stretch of neighbors that keeps a rule, and the length is not given: the rule decides when the window grows and shrinks.
  • Monotonic queueUse it when a window, a stretch of neighbors, moves along a list and you need its largest or smallest value at every position, which a running total cannot give.
  • Expand around a centerUse it when the pieces you want read the same from both ends and may sit anywhere in the input, so their two ends are not known in advance.
  • Binary search on a sorted rangeUse it when the list you search is given to you already in order, and one look at a position tells you on which side the answer lies.
  • Binary search on the answerUse it when there is no sorted list to look in: the answer is a number, a guess can be checked, and the guesses that pass all lie on one side.

Trees

Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

  • Postorder tree recursionUse it when a node's answer is built from the answers of its children, so the children must finish first: that order is what postorder means.
  • Preorder tree recursionUse it when a node needs something from the nodes above it, such as its level or a total so far, or must be handled before its children.
  • Level-order tree traversalUse it when the answer is grouped by level, or is about each level, or is the node nearest to the root, the top node.
  • Binary search tree orderingUse it when the tree is a binary search tree and you must find a value, its neighbour in sorted order, or its position in that order.
  • TrieUse it when the questions are about how words begin: whether any stored word starts with some letters, or which stored word a text starts with.
  • Heap of the best kUse it when only the k largest or k smallest of many values matter, and every other value can be thrown away as soon as k others are better.
  • Heap as a priority queueUse it when you must take the most urgent item next, again and again, while new items keep arriving and every item waits for its turn.
  • Two heapsUse it when you need the middle value again and again while numbers keep arriving: keep a smaller half and a larger half, and read their tops.

Graphs

Visit every place you can reach, once each, in the order that suits the question.

  • BacktrackingUse it when you must return every way to choose, order or place a few items, or find one way that keeps a rule, by trying the choices in turn.
  • Grid connected componentsUse it when a grid holds separate regions of joined cells and you must count them, measure them or mark them, and how far apart two cells are does not matter.
  • Breadth-first search by distanceUse it when the question is the fewest steps from a start, or from several starts at once, and every step costs the same: places are reached nearest first.
  • Graph traversal with a visited setUse it when things are joined by links that may form a loop, and you must reach, check or copy everything connected to a start, in any order.
  • Topological orderingUse it when pairs say one thing must come before another, and you need an order that keeps every pair, or need to know that no such order exists.
  • Union-findUse it when links are added one at a time and, between them, you must know whether two items are already in the same group.
  • Weighted shortest pathUse it when every link has its own cost and you need the cheapest route from one start to another place, or to every place.
  • Minimum spanning treeUse it when you choose which links to build so that everything is joined at the lowest total cost, and no single route has to be short.

Optimization

Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

  • One-dimensional dynamic programmingUse it when the answer at position i of one list depends only on the answers at a few earlier positions, so one row of cells is enough.
  • Knapsack dynamic programmingUse it when each item is taken or left against a budget or an exact total, so the cells are numbered by the amount used, not by position.
  • Two-dimensional dynamic programmingUse it when a smaller version of the task needs two numbers to describe it: a place in each of two strings, or a row and a column of a grid.
  • Interval dynamic programmingUse it when items stand in one row, an order of joins or removals must be chosen, and a smaller task is a stretch of the row, known by its two ends.
  • Greedy choiceUse it when you can say why the best-looking choice now can never spoil a better answer later, so nothing has to be kept open or tried again.
  • Sorted interval sweepUse it when the input is a list of start and end pairs and the question is how they overlap, touch or leave gaps, with nothing to choose.

Math & bits

Work on the cells, the digits or the bits themselves, in a fixed order.

  • Matrix traversalUse it when the task states the order to visit the cells of a grid, or the new place of each cell, and neither depends on what the cells hold.
  • Digit-by-digit arithmeticUse it when a number comes as separate digits in a list, a string or linked nodes, or when you must take its digits off one at a time.
  • Bit manipulationUse it when the task is about the 0s and 1s a number is stored as, not its decimal digits, or when each bit can stand for one yes or no.