Patterns

Pattern clue sheet

Every clue from every lesson. Read a problem, find the words that match, and see which pattern they point to. One clue is a hint; two that agree are an answer.

Search the clues in the app All 42 patterns

What you are given

Values in no useful order, and all you ask is whether one is there: Hash set membership. A set does not need order. It finds a value by the value itself, and yes or no is all it answers.
A rule gives the exact partner of each item: Hash map lookup. When you know exactly which value you need, you do not search for it. You look it up as a key.
Only lowercase letters, so at most 26 different values: Frequency counting. The table of counts stays small however long the input is. A list of 26 numbers can be the whole table.
The strings may contain any character at all: Length-prefixed encoding. Any mark you put between strings can also appear inside one. A length cannot be confused with the contents.
An empty string, and an empty list, must also come back exactly: Length-prefixed encoding. A length of 0 is written like any other length. So an empty string is still written as something, and an empty list as nothing.
Things open and close, one inside another: Last-in, first-out stack. What opened last must close first. Keep the open ones on a stack, and each close only looks at the top.
A linked list, and you may relink its nodes: Linked list pointer rewiring. A node is reached only by following links. Putting nodes in a new order means changing those links, not shifting values as in an array.
A list of operations to carry out, each with its arguments: Purpose-built data structure. There is no single input to scan. You decide what to store so that each operation finds what it needs.
A list sorted from smallest to largest, and a pair to find: Opposing two pointers. In sorted order the two ends are the smallest and the largest. Their sum tells you which one is too small or too large to keep.
A text and a shorter word; every candidate is as long as the word: Fixed-size sliding window. The word fixes the window's length, even though no number k is given. Slide a window of that length along the text.
A substring or subarray, and its length is not given: Variable sliding window. Neighbors in order are what lies between two edges, and a rule must set the length. A subsequence, which may skip items, is not a window.
The palindrome is a substring: its characters sit next to each other: Expand around a center. With no gaps allowed, the two ends move away from one middle together. If characters may be skipped, there is no single middle to grow from.
A list sorted from smallest to largest, and one value to find: Binary search on a sorted range. Order lets one comparison rule out a whole side. Without order, every value has to be looked at.
A sorted list was rotated: its first values moved to the end: Binary search on a sorted range. It is still two sorted pieces. Comparing the middle with an end value tells which piece it is in, so half still goes.
A budget to keep: finish within a given number of hours or days: Binary search on the answer. The budget turns a guess into a yes or no question: does this guess stay within it? That question is the test.
A path may join any two nodes, not only go down from the top: Postorder tree recursion. Such a path climbs to one highest node and goes down again. That node needs the best way down on each side, and its children hand those up.
The path to a node: the nodes from the root down to it: Preorder tree recursion. The root is the top node. A problem that defines this path usually has a rule about it, and each parent hands down a summary of the path so far.
The root is on level 0, its children on level 1: Level-order tree traversal. A problem that numbers the levels usually wants an answer for each level, which is what this walk produces.
The input is a binary search tree: Binary search tree ordering. Its ordering lets one comparison rule out a whole side of a node, so most of the tree is never visited.
Many words to look for at once, while letters come one at a time: Trie. Words that begin the same share one path. One walk down the tree follows every word that still fits the letters so far.
Values arrive one at a time, and the best k are wanted after each: Heap of the best k. Updating a heap of k takes about log k steps. Sorting everything again after each new value is far slower.
New items arrive, or change, between one take and the next: Heap as a priority queue. A sorted list would have to be sorted again after each change. A heap puts one new item in its place in about log n steps.
A growing collection of numbers, and the middle is asked for many times: Two heaps. Sorting again for each question is too slow. Two heaps keep the middle on top while numbers are added.
A path may not use the same cell twice: Backtracking. A cell is marked while the path stands on it. The mark is removed on the way back, so that another path may use the cell.
A grid whose cells are of two kinds, such as land and water: Grid connected components. Cells of one kind that touch form regions. A problem that draws its grid this way usually asks something about those regions.
Cells are joined side by side, and not at a corner: Grid connected components. This sentence defines a region. It also names the neighbors to look at from each cell: up, down, left and right.
Something spreads to every neighbor once per minute or per day: Breadth-first search by distance. After t rounds it has reached everything t steps from where it began. The time a place is reached is its distance.
One move changes a single letter, digit or position: Breadth-first search by distance. Each value is a place and each allowed change is a step to a neighbor. No list of links is given: you make the neighbors when you need them.
Each item has a list of the items it is joined to: Graph traversal with a visited set. That is a graph. From any item you can step to its neighbors, then to theirs, and so reach everything connected to it.
The links may lead round in a circle: Graph traversal with a visited set. A walk with no memory would go round for ever. The visited set ends it: a node already in the set is not entered again.
Each pair says one item must come before another: Topological ordering. These are one-way requirements. Count for each item how many others must come first, and take the items whose count is 0.
Links are added one at a time and never removed: Union-find. Groups only merge and never split. One changed pointer merges two groups, so the structure is right after every new link.
Each road has its own length, time or price: Weighted shortest path. Counting links is wrong when costs differ: three cheap links can beat one costly link. The costs must be added along each route.
A list of possible links, each with a cost: Minimum spanning tree. You decide which links to build. Grow one tree, and always add the cheapest link that reaches a point outside it.
Taking one item changes which later items you may take: One-dimensional dynamic programming. No choice is safe on the spot, so both sides of every choice are compared. The cells keep that from repeating work.
Each item has a size, and the total may not pass a limit: Knapsack dynamic programming. Many different choices use the same amount, and only the best of them matters. So one cell for each amount is enough.
Two strings to compare, match or turn into each other: Two-dimensional dynamic programming. A smaller task is a start of one string with a start of the other. Every pair of lengths gets one cell of the table.
A grid where each move goes only right or down: Two-dimensional dynamic programming. A cell can be entered only from above or from the left. Its answer comes from those two cells, which are filled first.
Only neighbors in the row can be joined or combined: Interval dynamic programming. Whatever is joined last is made from a left part and a right part, and each part is a shorter stretch of the same row.
Each operation changes which items are next to each other: Interval dynamic programming. Then the first operation is hard to reason about. Ask which operation of a stretch comes last: its two sides never meet, so they are solved apart.
A running total that must never drop below zero: Greedy choice. The moment it drops below zero, everything before that point is ruled out together. One pass settles each point as it is met.
A list of intervals, each a start and an end, in no order: Sorted interval sweep. Sorted by start, the intervals that can touch each other become neighbors, so one walk compares each with what came before it.
A number given as a list of digits, or one digit to a node: Digit-by-digit arithmetic. The number is already cut into places. Do the arithmetic one place at a time, and pass a carry on to the next place.
Every item has some of at most 30 yes or no properties: Bit manipulation. One bit holds one yes or no, so a whole set fits in one number. AND and OR then combine two sets in one step.

What you are asked for

Has this value been seen before?: Hash set membership. The set holds everything met so far, so the question is one lookup for each value.
Which values are in one list but not in the other?: Hash set membership. Put one list in a set, then test each value of the other list against it.
Return the positions of the two items that match: Hash map lookup. A position must be remembered beside each item. A map from item to position gives it back in one step.
Put the items that share a label into one group: Hash map lookup. The label is the key, and the list of its items is kept beside it. Each item finds its group in one step.
Which values appear most often, or at least k times?: Frequency counting. How often is a question about counts. Count every value first, then choose from the counts.
Do two lists hold the same items, in any order?: Frequency counting. When order does not matter, two lists hold the same items exactly when every value has the same count in both.
Compare what is left of a position with what is right of it: Prefix and suffix passes. Each side is a running result. One pass from the left and one from the right give both sides to every position.
For each position, a result from all the items except that one: Prefix and suffix passes. All except one is everything before it together with everything after it. Each side is carried along in its own pass.
Turn a list of strings into one string and back: Length-prefixed encoding. The reader must know where each string ends. A length written in front says so, with no searching.
Undo, cancel or go back to the most recent step: Last-in, first-out stack. The step to take away is the newest one still kept, and that is the top of a stack.
An item combines with, or cancels, the one right before it: Last-in, first-out stack. After a cancel, the item before that becomes the neighbor. A stack keeps that earlier item ready on top.
For each item, the next later item that is larger: Monotonic stack. Items wait on the stack. A larger arrival takes off every smaller one, and it is the answer for each of them.
The nearest earlier item that is smaller than this one: Monotonic stack. Take off the earlier items that are not smaller. The top that is left is the nearest smaller one.
How far an item reaches before a lower one stops it: Monotonic stack. The reach ends at the nearest lower item on each side. One ordered stack finds both ends for every item.
Return the same nodes in a new order: Linked list pointer rewiring. No new node is needed. Each node keeps its value, and only its link is pointed somewhere else.
Join two lists into one, or cut one list into parts: Linked list pointer rewiring. A join or a cut is one link changed: the end of one part points at the start of another, or at nothing.
Find the middle of a linked list in one pass: Fast and slow pointers. When the fast pointer has covered the whole list, the slow one, at half the speed, has covered half of it.
Does following the links ever come back to an earlier node?: Fast and slow pointers. In a loop the fast pointer cannot leave. It gains one node on the slow one each round until it lands on it.
The node that is k places before the end: Fast and slow pointers. Start one pointer k nodes ahead and move both together. When the leader reaches the end, the other is k behind.
Design a structure that supports these operations: Purpose-built data structure. The work is choosing the parts. For each operation, ask which simple structure would answer it in one step.
The same data must be found in two different ways: Purpose-built data structure. One structure is fast for one way of asking. Keep a second one for the other way, and update both together.
Does the whole string read the same forward and backward?: Opposing two pointers. The first item must match the last, the second must match the one before last. Two positions moving inward check exactly those pairs.
Choose two positions; the score grows with the distance between them: Opposing two pointers. Start with the widest pair. Every move gives up distance, so leave the end that cannot score higher with any other partner.
The largest total of any k items in a row: Fixed-size sliding window. The length is given, so only the place of the window changes. Each move adds one item to the total and subtracts one.
The longest run of neighboring items in which a rule holds: Variable sliding window. Take items in on the right while the rule holds. When it breaks, dropping items on the left repairs it, so you never start over.
The shortest run of neighboring items that reaches a goal: Variable sliding window. Grow on the right until the goal is reached, then drop items on the left while it still is. Each drop gives a shorter candidate.
The smallest value of every k items in a row: Monotonic queue. A total can be corrected when an item leaves the window. A smallest value cannot, so you keep the values that could be smallest next.
After each new reading, the highest of the last k readings: Monotonic queue. A new reading that is higher makes every older, lower reading useless: the new one stays in the window longer. Drop them, and the highest is at the front.
The longest palindrome inside a string: Expand around a center. Every palindrome has a middle. Growing outward from each middle finds the longest one around it, and the longest of those is the answer.
How many substrings are palindromes?: Expand around a center. Each step outward that still matches is one more palindrome. Count the steps over all middles and none is missed or counted twice.
The position of a value, or where it would go: Binary search on a sorted range. In sorted data the smaller values come first. Halving finds where they stop, and that is the place of the value.
The smallest speed, size or limit that is still enough: Binary search on the answer. Smallest that is enough means a line between no and yes. When larger values stay enough, halving the range finds that line.
The earliest time at which something becomes possible: Binary search on the answer. When what is possible stays possible later, the times are a run of no and then a run of yes. Halving finds the first yes.
Return the height, the size or the total of a tree: Postorder tree recursion. For a node, each of these is made from its own part and the same number from each child. So the children must answer first.
A rule at every node about the height or total of its two sides: Postorder tree recursion. Each side's number is ready only after that side has finished. So the children report first, and the node tests the rule on the way back up.
Each node needs its level, counted from the root: Preorder tree recursion. A node cannot see above itself. Its parent knows its own level and passes that number plus one to each child.
Write the tree out, each node before its children: Preorder tree recursion. The node is handled first and its two sides after it, each side in the same way. That order is preorder.
Return the values level by level, from the top down: Level-order tree traversal. The queue hands the nodes over in exactly that order: all of one level before any node of the next.
The largest, the total or the average value of each level: Level-order tree traversal. Each of these needs all the nodes of one level together. The size of the queue when a level starts says where that level ends.
The fewest steps down from the root to reach something: Level-order tree traversal. Levels are read in order of distance from the root, so the first match met is the nearest and the walk can stop.
In a binary search tree, the smallest value not below a given number: Binary search tree ordering. At each node the comparison says whether a better value can only be on the left or only on the right.
Return a binary search tree's values in sorted order, or its kth smallest: Binary search tree ordering. Reading a node's left side, then the node, then its right side meets the values from smallest to largest.
Does any stored word start with these letters?: Trie. Walk the letters down from the root. If every step is there, at least one stored word begins that way.
Match words letter by letter, where some letters are unknown: Trie. A known letter has one step down to take. An unknown letter tries every step, and a path that spells no word is dropped early.
Return the k largest values, or the kth largest: Heap of the best k. Only k values can matter. A min-heap, a heap with its smallest on top, keeps them: the top is the weakest of the k.
The k closest, cheapest or smallest of many items: Heap of the best k. Keep k items in a max-heap, a heap with its largest on top. The top is the worst of the k kept, so a better item pushes it out.
Take the largest (or smallest) item that is left, again and again: Heap as a priority queue. The top of the heap is always that item. After it leaves, the next one comes to the top in about log n steps.
Report the median after each new number: Two heaps. The median, the middle value in sorted order, is where the smaller half meets the larger half. Both tops stand at that border.
Split the values into a lower half and an upper half: Two heaps. A max-heap, largest on top, holds the lower half. A min-heap, smallest on top, holds the upper half. Moving one top across keeps the sizes the same, or one apart.
Return every possible way, or all the ways that keep a rule: Backtracking. Every way must be built, so each one is made choice by choice. Undoing a choice lets the next way reuse the part before it.
Place the pieces so that no rule is broken: Backtracking. A rule can be tested after each piece. A piece that breaks it is taken back at once, with everything that would have followed.
How many separate regions are there, or how large is the largest?: Grid connected components. Each region is walked once, from the first of its cells that the scan meets. Count the walks, or count the cells in each walk.
Which regions touch the edge of the grid?: Grid connected components. Start the walks from the cells on the edge. Everything they reach touches the edge, and every region left unmarked does not.
The fewest steps, moves or changes to get from A to B: Breadth-first search by distance. Places leave the queue in order of distance. The first time the target appears, no shorter way to it can exist.
The distance from each cell to the nearest of several sources: Breadth-first search by distance. Put all the sources in the queue first, at distance 0. They spread together, and each cell is first reached from its nearest source.
Can every node be reached from the first one?: Graph traversal with a visited set. Walk from the first node and mark what you meet. Then compare the number of marked nodes with the number of nodes.
Make a copy of every node, with the same links: Graph traversal with a visited set. Keep a map from each node to its copy. It is the visited record, and it also gives the copy that a link must point to.
Return an order in which everything can be done: Topological ordering. Taking an item only when nothing it needs is missing builds such an order, from the front to the back.
Can all of it be done, true or false?: Topological ordering. It can, unless some requirements form a loop. Items in a loop never reach a count of 0, so they are never taken.
Are these two already connected?: Union-find. Two items are connected exactly when find gives the same leader for both. No walk along the links is needed.
How many separate groups are there after each new link?: Union-find. Start the count at the number of items. Each union of two different leaders leaves one group fewer.
The cheapest, shortest or fastest way from a start: Weighted shortest path. The answer is the smallest sum of costs along a route from the start. Keep the best sum known for each place and lower it link by link.
The cheapest route that uses at most k links: Weighted shortest path. Let each round read only the costs from before it, kept in a copy. Then a round lets every route grow by one link, so run k rounds.
Connect all the points at the lowest total cost: Minimum spanning tree. The cheapest way to join everything has no closed loop, so it is a tree that reaches every point: n points, n - 1 links.
Count the ways to reach the end, or say if there is any way: One-dimensional dynamic programming. You are asked how many or whether, not which. The answer for a position comes from the answers for the positions one move before it.
The largest or smallest total you can get along a row: One-dimensional dynamic programming. The best total up to a position is built from the best totals a few positions earlier. Each is worked out once and read later.
Can some of the numbers add up to exactly this total?: Knapsack dynamic programming. Which numbers made a sum does not matter, only that it can be reached. Mark each reachable sum in its cell, number by number.
The fewest items, or the number of ways, to make an exact amount: Knapsack dynamic programming. Take one item off the amount and a smaller amount is left. Its cell is already filled, so the answer is read, not worked out again.
The longest part two strings share, or the fewest edits between them: Two-dimensional dynamic programming. Look at the last item of each. Whatever is done with them leaves the same question for shorter strings, already answered in the table.
The best total over every order of doing the operations: Interval dynamic programming. The orders are far too many to try one by one. Many orders share the same stretches, so each stretch is solved once and reused.
The largest number of items you can take, each counting as one: Greedy choice. When every item counts the same, a choice is judged only by what it blocks. Often one choice blocks the least, and taking it first is safe.
Can the last position be reached, when shorter moves are always allowed?: Greedy choice. Then reaching far also means reaching everything nearer. One number, the farthest point so far, stands for all the routes.
The largest sum of a run of neighbors, with negative numbers allowed: Greedy choice. A run whose sum has dropped below zero only hurts what follows. Drop it and start again at the next number: one carried sum is enough.
Do any two of the bookings overlap?: Sorted interval sweep. After sorting by start, an overlap always shows between neighbors: a booking starts before the latest end so far. No other pair needs a look.
The largest number of visits going on at the same moment: Sorted interval sweep. Sort every start and every end as moments in time. Walking them in order, a count goes up at a start and down at an end.
Return the values of the grid in a stated order: Matrix traversal. The order is known before you start. Loops over the row and column numbers produce it, so nothing is searched and nothing is marked.
Flip, turn or shift the whole grid: Matrix traversal. The new cell of a value depends only on its old row and column. One rule with those two numbers moves every value.
The result may need one more digit than the input has: Digit-by-digit arithmetic. That extra digit is the carry left over after the first digit. A carry means the arithmetic is done place by place.
A question about the digits of a whole number, such as their sum: Digit-by-digit arithmetic. The remainder after dividing by 10 is the last digit. Dividing by 10 and rounding down removes it. Repeat, and the number comes apart digit by digit.
The task asks about the 0s and 1s a number is stored as: Bit manipulation. Bit operators reach single bits directly. AND with 1 reads the last bit, and a shift right moves the next bit into its place.

What the limits say

Up to 100,000 values, so checking every pair for a repeat is too slow: Hash set membership. Every pair is about 5 billion comparisons. One set check for each value is 100,000.
Up to 100,000 items, and each needs its exact partner among the earlier ones: Hash map lookup. Searching back from every item is about 5 billion steps. One lookup by key for each item is 100,000.
You may not use division: Prefix and suffix passes. Dividing the product of all the items by one item would take that item out. Without division, the two sides have to be built separately.
Up to 100,000 items, so adding up each side again is too slow: Prefix and suffix passes. Building both sides again for every position is about 10 billion steps. Two passes are 200,000.
The reader gets only the one string, nothing else: Length-prefixed encoding. Everything needed to split the text must be inside the text. The lengths are written in the text, in front of the strings.
Up to 100,000 items, so looking back for a larger one is too slow: Monotonic stack. Looking back from every item can take about 5 billion steps. On the stack each item goes on once and comes off at most once.
Reorder the list in place, with only a few variables: Linked list pointer rewiring. Changing links in place needs a few variables that each remember one node, and nothing more.
Walk a chain using only a constant amount of extra memory: Fast and slow pointers. Two variables are all it takes. Remembering every node you passed would need memory for the whole chain.
Every operation must take constant time: Purpose-built data structure. Constant time means a few steps however much is stored. A search through everything is ruled out, so something extra must be kept ready.
Trying every pair is too slow, and extra space must stay constant: Opposing two pointers. A table of values seen would cost memory. Two positions are two numbers, however long the list is, and together they move at most n places.
k can be large, so adding up each stretch again is too slow: Fixed-size sliding window. Adding up every window again costs about n times k steps. Updating the total costs two steps for each move, whatever k is.
Up to 100,000 items, so trying every stretch is too slow: Variable sliding window. There are about 5 billion stretches. Two edges that only move forward make at most 200,000 moves between them.
Aim for O(n) time; searching each window again is too slow: Monotonic queue. Searching every window costs about n times k steps. In the queue each value joins once and leaves once, about 2n steps.
Palindromes in a string of at most 1,000 characters: Expand around a center. About 2,000 middles, each grown at most 500 steps, is at most a million comparisons. Testing every substring on its own can take about 83 million.
Aim for O(log n) time: Binary search on a sorted range. Only halving is that fast. A list of 1,000,000 values is down to one position after about 20 looks.
The answer can be as large as 1,000,000,000: Binary search on the answer. Trying every value is a billion tests. Halving needs about 30, so each test can afford a full pass over the input.
Up to 100,000 nodes, so no height or total can be worked out twice: Postorder tree recursion. On a tree that is one long chain, working out the height again at every node costs about 5 billion steps. Handing it up costs one visit per node.
The tree is balanced and holds a million values: Binary search tree ordering. Balanced means no side is much deeper than the other. A path from the top to the bottom is then about 20 nodes, so a search takes about 20 steps.
Many stored words, and a question about a beginning must not read them all: Trie. A walk takes one step for each letter of the question. How many words are stored does not change that.
n is very large and k is small: Heap of the best k. Sorting costs about n log n steps and keeps all n values. A heap of k costs about n log k steps and keeps only k.
Up to 100,000 items, so scanning them all for each take is too slow: Heap as a priority queue. Scanning for the largest before every take is about 5 billion comparisons in total. A heap needs about 17 steps for one take.
Up to 100,000 numbers, and the middle is asked for after each: Two heaps. Sorting before every question is far too slow. A push or a pop takes about 17 steps, and the middle is read in one.
The input has at most about 20 items: Backtracking. Trying every way grows very fast: 20 yes-or-no choices give 1,048,576 ways. A limit this small says that trying them all is expected.
Thousands of items and pairs, so trying every order is far too slow: Topological ordering. Ten items already have 3,628,800 possible orders. This method reads each item once and each pair twice.
Up to 100,000 items, and 100,000 questions mixed in with the links: Union-find. A new walk for every question can be about 10 billion steps in all. A find climbs only a few pointers.
Up to 1,000 points, and any two of them may be linked: Minimum spanning tree. That is about 500,000 possible links, far too many to try in sets. Growing the tree takes about 2 million steps.
Up to 100 items, and each one is a yes or no choice: One-dimensional dynamic programming. Trying every mix of choices is 2 to the power 100, far too many. One cell for each position is about 100 cells.
The limit or the target total is at most a few thousand: Knapsack dynamic programming. The row has one cell for each amount from 0 to the limit, so the limit must be small enough to walk through.
Both strings have up to 1,000 letters: Two-dimensional dynamic programming. That is about a million pairs of lengths, one cell each, which is fast. Trying every way to line the letters up is not.
The row has at most a few hundred items: Interval dynamic programming. Every stretch with every split is about 4.5 million steps for 300 items. A limit this small leaves room for such a table.
Up to 100,000 intervals, so comparing every pair is too slow: Sorted interval sweep. Every pair is about 5 billion comparisons. Sorting takes about 1.7 million steps, and the walk after it 100,000.
Move the values inside the grid itself; a second grid is not allowed: Matrix traversal. Values must trade places directly. The walk is planned so that every value moves once and none is written over before it has moved.
You may not turn the whole string into a number: Digit-by-digit arithmetic. The built-in arithmetic is ruled out, and in many languages a long number would not fit. The paper method needs only one digit and a carry.
The + and - operators are not allowed: Bit manipulation. When ordinary arithmetic is ruled out, only the bits are left to work with. The bit operators can rebuild it from them.
Every value comes twice except one, and extra memory must stay constant: Bit manipulation. XOR, written ^, gives 0 for two equal numbers. So pairs cancel each other, and one number does the work of a set.