Coding Interview Patterns Module 33 – Pattern recognition and mixed practice
Which pattern? A decision guide
Map a problem's input shape, question words and limits to the coding patterns that fit, rule the rest out, and choose top-down or bottom-up DP.
What you will learn
- Map input shapes and question words to candidate patterns
- Eliminate the patterns that the constraints rule out
- Recognise when DP is needed and choose top-down or bottom-up
- Check a pattern choice on small cases before writing the full solution
Before you start
What you’ll learn · Before you start
What you will learn
- Map input shapes and question words to candidate patterns
- Eliminate the patterns that the constraints rule out
- Recognise when DP is needed and choose top-down or bottom-up
- Check a pattern choice on small cases before writing the full solution
Before you start
On this page
Choosing a pattern for a coding problem comes down to three readings of the statement: the shape of the input, the words of the question and the size of the limits. Each reading points to a few candidates. A sorted array suggests binary search or two pointers, “count the ways” suggests dynamic programming, and n up to 20 allows an exponential search over subsets. The limits then rule out whatever is too slow, and a check on a small case, by hand or against a brute force, rules out an idea that gives wrong answers. This lesson collects those signals in one table, classifies twelve original problem sketches with the reasoning written out, runs two problems that read alike but need different patterns, and shows when a dynamic program should be written top-down or bottom-up.
Three readings of every statement
Read the statement three times, each time for one kind of clue, and note what you find before you think about code.
- The shape of the input. A sorted array, an unsorted array, a string, a grid, a tree, a list of edges, a set of intervals, or a stream that arrives one item at a time. The shape narrows the field at once: intervals invite sorting by an end point, a list of edges invites a graph search, and a stream rules out anything that needs the whole input first.
- The words of the question. “Longest contiguous”, “number of ways”, “minimum cost”, “every combination”, “k-th largest”, “next greater”, “before”, “connected” and “the smallest value such that” each belong to a small family of patterns. The verb matters too: list every answer, count the answers or find the best one are three different problems, even on the same input.
- The limits. The largest n and the time limit give a target complexity, which the constraints lesson works out step by step. The limits on the values, the number of queries and whether numbers can be negative matter as much as n.
Say what each reading found in one sentence, for example: “a list of up to 2 × 10⁵ integers, some negative; the number of stretches with a given total”. That sentence is usually enough to pick the first candidate.
The decision table
Each row pairs a clue with the pattern to try first and the property that must hold before the pattern is correct. The property matters most: a clue suggests a pattern, and the property decides it.
| The statement shows | Try first, and what to check before you commit |
|---|---|
| Sorted input, or “the smallest value such that” | Binary search, on the array or on the answer. Check that the yes-or-no test is monotone: once it is true, it stays true for every larger value. |
| A contiguous run whose validity only breaks as it grows | A sliding window. Check that shrinking a valid run keeps it valid, which usually means no negative values. |
| Totals or counts over contiguous runs, with negative values | Prefix sums with a hash map. Check that the question becomes “two prefixes that differ by k”. |
| Pairs or triples in sorted data | Two pointers. Check that each move rules a value out for good. |
| “Seen before?”, grouping or counting | A hash map or a set. Check that equal items can be given equal keys, such as sorted letters or a tuple. |
| “List every combination or arrangement” | Backtracking. Check that the output, or the search after pruning, is small enough to list. |
| “Count the ways” or “the best total”, with choices that repeat subproblems | Dynamic programming. Check that you can state the subproblem in words, and that greedy has a counterexample. |
| A choice that never needs undoing | Greedy. Check that an exchange argument holds, or at least that a brute force finds no counterexample. |
| Fewest steps when every step costs the same | Breadth-first search. Check that edges are unweighted; weights of 0 and 1 need a 0-1 BFS. |
| Cheapest path with non-negative weights | Dijkstra’s algorithm. Check that no weight is negative; otherwise use Bellman–Ford. |
| “Must come before”, “depends on” | Topological sort. Check that the graph has no cycle, which the sort itself detects. |
| “Same group?” while connections are added | Union-find. Check that connections are only added, never removed. |
| “The k largest”, “the k closest”, a repeated minimum | A heap. Check that k is much smaller than n; otherwise sort. |
| “Next greater”, “previous smaller” | A monotonic stack. Check that each item waits for the first item that beats it. |
| Overlapping time slots or ranges | Sort by start or end, then sweep. Check that the ends are agreed: half-open or closed. |
| Many lookups by prefix | A trie. Check that many words share prefixes. |
From a shortlist to one choice
How a shortlist of patterns becomes one choice
Text description of the diagram
The flow chart runs from top to bottom in one column.
- Read three things in the statement: the shape of the input, the words of the question, and the limits.
- Shortlist one to three patterns from the decision table.
- Ask whether a candidate fits the time budget that the limits allow. If not, drop it and go back to the shortlist.
- If it fits, check it on a small case, by hand or against a brute force.
- Ask whether the answers are the same. If not, go back to the shortlist and take the next candidate.
- If they are, say the pattern and its cost aloud, then write the code.
The table gives a shortlist of one to three patterns; the flow above turns it into one choice. First compare each candidate’s cost with the budget that the limits allow. A pattern that is too slow is dropped, or kept only if you can name the property that would make a faster version correct. Then check the survivor on a small case. For a greedy rule or a sliding window, a brute force over every small input is the fastest way to find a counterexample, and the run later in this lesson finds one in a fraction of a second. Only then say the choice aloud, with its cost, and start writing.
In a 45-minute round this takes about two minutes, and it is time well spent: an interviewer can redirect a plan that you state, but not one that you keep to yourself while typing.
Ruling patterns out with the limits
The limits rarely tell you which pattern to use, but they often tell you which ones you cannot use. Read the largest size first and cross out what it forbids:
- n up to about 10: trying every order is affordable, since 10! is about 3.6 × 10⁶, so a plain permutation search can be the whole answer.
- n up to about 20: every subset, about 10⁶ of them, can be visited, so bitmask DP and backtracking stay on the list.
- n in the hundreds: three nested loops fit, which keeps interval DP and all-pairs shortest paths possible.
- n in the thousands: quadratic work fits, which allows a table over two prefixes.
- n around 10⁵ to 10⁶: only O(n log n) or O(n) remain: sorting, heaps, binary search, one pass with a hash map, windows, stacks and two pointers.
The other limits cross out more. Values up to 10⁹ rule out an array indexed by value, so use a hash map or sort and compress the values. Negative values rule out a sliding window over sums and Dijkstra’s algorithm on weights. Many queries on a fixed input rule out answering each query from scratch, so prepare once. A small second parameter, such as k ≤ 20 colours, suggests subsets over k even when n is large.
Twelve sketches, classified
Each sketch below is an original problem in one or two sentences, followed by the clues, the pattern and why the look-alike pattern fails.
- Most overlapping bookings. Given n room bookings as time slots, report the largest number in progress at once. Clues: intervals, “at once”. Pattern: sort the start and end events and sweep, counting. A sliding window does not apply because the slots are not one contiguous run of an array.
- The longest playlist for a commute. Song lengths are positive; find the longest run of consecutive songs that fits in 60 minutes. Clues: contiguous, a total that only grows as the run grows. Pattern: a sliding window. Prefix sums with binary search also work, but cost a log factor for nothing.
- Balanced trading days. Daily profit can be negative; count the stretches of days with a total of exactly zero. Clues: contiguous, negative values, “count”. Pattern: prefix sums with a hash map of how often each running total has occurred. The window fails, because with negative days neither growing nor shrinking a stretch moves its total in one direction.
- The quickest metro route. Stations and the travel time between neighbours; the quickest route from A to B. Clues: a graph with non-negative weights, “quickest”. Pattern: Dijkstra’s algorithm. Breadth-first search finds the fewest stops, which is a different question.
- A study order. Courses with prerequisites; an order that takes every course after its prerequisites, or “no order”. Clues: “after”, dependencies. Pattern: topological sort. Sorting by the number of prerequisites fails as soon as a chain is longer than two.
- Friend groups as requests arrive. After each accepted friend request, are users x and y in one group? Clues: connectivity, edges only added, many queries. Pattern: union-find. A fresh search for every query is too slow.
- The smallest truck. Parcels must leave in order within d days; find the smallest daily capacity that ships them all. Clues: “the smallest value such that”, and a capacity that works keeps working when it grows. Pattern: binary search on the capacity with a greedy check. Trying every capacity in turn costs one check per possible capacity.
- Seating rivals. Seat nine guests in a row so that no two rivals sit side by side, and list every seating. Clues: “list every”, n = 9. Pattern: backtracking with pruning, because 9! is only 362,880 orders to begin with and pruning cuts most of them.
- The ten busiest pages. A day of 10⁷ page views; the ten most viewed pages. Clues: counting, “top ten”. Pattern: a hash map of counts, then a heap of size ten. Sorting every view is wasteful when only the ten largest counts matter.
- Nearest taller tower. For each tower in a row, the distance to the nearest taller tower on its right. Clues: “nearest greater”. Pattern: a monotonic stack, O(n). Two nested loops cost O(n²).
- Change with odd coins. Coins of 1, 4 and 6 units; the fewest coins for an amount. Clues: “fewest”, choices that overlap. Pattern: dynamic programming over the amounts. The largest coin first pays 8 as 6 + 1 + 1, three coins, where 4 + 4 needs two.
- The longest rising trend. Daily prices; the longest sequence of days, not necessarily consecutive, on which the price keeps rising. Clues: “not necessarily consecutive” makes it a subsequence. Pattern: dynamic programming, or patience sorting in O(n log n). A single pass that tracks the current rising run answers the contiguous version of the question, not this one.
Three of the sketches turn on a single word. “Positive” in sketch 2 keeps the window; with negative values the problem would need sketch 3’s prefix sums. “Quickest” in sketch 4 asks for Dijkstra; “fewest stops” would ask for breadth-first search. “Not necessarily consecutive” in sketch 12 asks for a subsequence; consecutive days would need one pass.
Two problems that read alike
A technician staffs conference talks, one at a time; each talk is a time slot from its start to its end, and a talk may start when another ends. Problem 1: staff as many talks as possible. Problem 2: each talk pays a fee; earn as much as possible. Both read as “choose non-overlapping slots”, and a well-known greedy rule, taking the talk that ends first among those that fit, solves the first. The program below tests that rule, a second greedy rule and a dynamic program against a brute force that tries every set of talks. Each talk is written as (start, end, fee).
"""Two problems that read alike: a technician staffs one talk at a time, each talk a half-open slot [start, end).
Problem 1 asks for the most talks staffed; problem 2 pays a fee per talk and asks for the most money. One greedy
rule solves the first. The second needs dynamic programming, and a brute force over every set of talks shows why:
first on every small case, shortest first, then on random ones.
"""
import random
from bisect import bisect_right
from itertools import combinations, product
def fits(chosen):
"""No two chosen talks overlap (a talk may start when another ends)."""
ordered = sorted(chosen, key=lambda t: t[0])
return all(a[1] <= b[0] for a, b in zip(ordered, ordered[1:]))
def brute_force(talks, value):
"""The best total of value(talk) over every set of talks that fit: 2^n sets."""
best = 0
for r in range(1, len(talks) + 1):
for chosen in combinations(talks, r):
if fits(chosen):
best = max(best, sum(value(t) for t in chosen))
return best
def greedy(talks, value, key):
"""Takes talks in the order of `key`, keeping each one that fits with those kept."""
kept = []
for t in sorted(talks, key=key):
if fits(kept + [t]):
kept.append(t)
return sum(value(t) for t in kept)
def dynamic_program(talks, value):
"""best[i] = the most from the first i talks by end time: skip talk i, or take it after the talks that end in time.
O(n log n): one sort, then one binary search per talk.
"""
by_end = sorted(talks, key=lambda t: t[1])
ends = [t[1] for t in by_end]
best = [0] * (len(by_end) + 1)
for i, (start, end, fee) in enumerate(by_end, 1):
before = bisect_right(ends, start, 0, i - 1) # talks that end by this one's start
best[i] = max(best[i - 1], value((start, end, fee)) + best[before])
return best[-1]
COUNT = lambda t: 1 # problem 1: every talk counts once
FEE = lambda t: t[2] # problem 2: a talk is worth its fee
EARLIEST_END = lambda t: (t[1], t[0])
HIGHEST_FEE = lambda t: (-t[2], t[1])
SLOTS = [(s, e) for s in range(4) for e in range(s + 1, 5)]
def small_cases(max_talks, fees):
"""Every set of up to max_talks talks with slots inside [0, 4) and the given fees, fewest talks first."""
for n in range(1, max_talks + 1):
for slots in combinations(SLOTS, n):
for paid in product(fees, repeat=n):
yield [(s, e, f) for (s, e), f in zip(slots, paid)]
def first_disagreement(method, value, fees):
for talks in small_cases(3, fees):
if method(talks, value) != brute_force(talks, value):
return talks
return None
def random_agreement(method, value, rng, trials=2000):
right = 0
for _ in range(trials):
talks = []
for _ in range(rng.randint(1, 9)):
start = rng.randint(0, 20)
talks.append((start, start + rng.randint(1, 6), rng.randint(1, 9)))
right += method(talks, value) == brute_force(talks, value)
return right
rng = random.Random(7)
by_end = lambda talks, value: greedy(talks, value, EARLIEST_END)
by_fee = lambda talks, value: greedy(talks, value, HIGHEST_FEE)
print("Problem 1: the most talks staffed")
print(f" earliest end first: first disagreement with the brute force: {first_disagreement(by_end, COUNT, [1])}")
print(f" earliest end first: right on {random_agreement(by_end, COUNT, rng):,} of 2,000 random sets")
print()
print("Problem 2: the most fees earned")
for name, method in (("earliest end first", by_end), ("highest fee first", by_fee)):
talks = first_disagreement(method, FEE, [1, 2, 3])
print(f" {name}: first disagreement: {talks}")
print(f" brute force {brute_force(talks, FEE)}, {name} {method(talks, FEE)}, dynamic program {dynamic_program(talks, FEE)}")
print(f" {name}: right on {random_agreement(method, FEE, rng):,} of 2,000 random sets")
print(f" dynamic program: first disagreement: {first_disagreement(dynamic_program, FEE, [1, 2, 3])}")
print(f" dynamic program: right on {random_agreement(dynamic_program, FEE, rng):,} of 2,000 random sets")Output
Problem 1: the most talks staffed
earliest end first: first disagreement with the brute force: None
earliest end first: right on 2,000 of 2,000 random sets
Problem 2: the most fees earned
earliest end first: first disagreement: [(0, 1, 1), (0, 2, 2)]
brute force 2, earliest end first 1, dynamic program 2
earliest end first: right on 1,130 of 2,000 random sets
highest fee first: first disagreement: [(0, 1, 1), (0, 2, 2), (1, 2, 2)]
brute force 3, highest fee first 2, dynamic program 3
highest fee first: right on 1,856 of 2,000 random sets
dynamic program: first disagreement: None
dynamic program: right on 2,000 of 2,000 random sets
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 look_alike.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
For problem 1, the earliest-ending rule agrees with the brute force on every set of up to three talks in a small grid of slots and on 2,000 random sets. For problem 2 it fails on two talks: (0, 1) paying 1 and (0, 2) paying 2. It takes the first because it ends sooner and earns 1, where the brute force earns 2. Taking the highest fee first fails too, on three talks. The dynamic program sorts the talks by end and, for each talk, takes the better of skipping it or taking it after the talks that end in time, which a binary search finds; it agrees with the brute force everywhere.
Notice how often the broken rules look right on random data: the highest-fee rule is right on 1,856 of 2,000 random sets, 93 %. A few random tests prove little; an exhaustive search over small cases, sorted shortest first, finds the smallest counterexample. The word that moved the problem was “fee”: once choices carry different values, a choice that looks best now can cost more later, and that is the signal for dynamic programming.
Is it DP, and which way to write it?
Dynamic programming fits when three things hold. The problem is made of choices (take or skip, which coin, which split). The best or the count for the whole is built from the best or the count of smaller instances of the same problem. And those smaller instances repeat, so that remembering them saves work. Richard Bellman, who developed the method, called the second property the principle of optimality. If you can say the subproblem in one sentence (“the most money from the first i talks”), you have a state; if a greedy rule has a counterexample, you need the state.
There are two ways to write the same recurrence. Top-down is the recursion with a cache: it is quick to write from the recurrence and computes only the states it reaches. Bottom-up fills a table in an order that has every smaller state ready: it needs no recursion and can often keep only the last row or two. The program below writes two recurrences both ways in Python:
"""Top-down or bottom-up: the same two recurrences written both ways.
1. Bit strings of length n with no two 1s side by side, counted modulo 10**9 + 7. Every state from n down to 0 is
needed, and the top-down version recurses n levels deep.
2. g(0) = 1 and g(n) = g(n // 2) + g(n // 3). From one large n, only a few values of n are ever reached.
"""
import sys
from functools import cache
MOD = 10**9 + 7
def ways_top_down(n, memo):
"""The recursion with a cache: one dictionary entry per length already counted."""
if n <= 1:
return n + 1 # "" for n = 0; "0" and "1" for n = 1
if n not in memo:
memo[n] = (ways_top_down(n - 1, memo) + ways_top_down(n - 2, memo)) % MOD
return memo[n]
def ways_bottom_up(n):
a, b = 1, 2 # ways for lengths 0 and 1; two variables are the whole table this recurrence needs
for _ in range(n):
a, b = b, (a + b) % MOD
return a
print("1. Bit strings with no two 1s side by side")
print(f" recursion limit: {sys.getrecursionlimit()}")
for n in (10, 500, 5000):
try:
top = ways_top_down(n, {})
except RecursionError as e:
top = type(e).__name__
print(f" n = {n:>5,}: top-down {top}, bottom-up {ways_bottom_up(n)}")
@cache
def g(n):
return 1 if n == 0 else g(n // 2) + g(n // 3) # functools.cache keeps one entry per n it has computed
print()
print("2. g(n) = g(n // 2) + g(n // 3), from one large n")
for n in (10**6, 10**12, 10**18):
g.cache_clear()
value = g(n)
print(f" n = 10^{len(str(n)) - 1}: g(n) = {value:,}; top-down computed {g.cache_info().currsize:,} values,"
f" a bottom-up table would hold {n + 1:,}")Output
1. Bit strings with no two 1s side by side recursion limit: 1000 n = 10: top-down 144, bottom-up 144 n = 500: top-down 73724597, bottom-up 73724597 n = 5,000: top-down RecursionError, bottom-up 396105780 2. g(n) = g(n // 2) + g(n // 3), from one large n n = 10^6: g(n) = 80,406; top-down computed 108 values, a bottom-up table would hold 1,000,001 n = 10^12: g(n) = 4,266,563,557; top-down computed 438 values, a bottom-up table would hold 1,000,000,000,001 n = 10^18: g(n) = 224,412,958,156,019; top-down computed 1,012 values, a bottom-up table would hold 1,000,000,000,000,000,001
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 dp_styles.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The first recurrence counts bit strings of length n with no two 1s side by side. Its top-down version recurses
n levels deep, so at n = 5,000 it passes CPython’s recursion limit of 1,000 and stops with a RecursionError. The
bottom-up loop keeps two variables, the whole table that this recurrence needs. The second recurrence, g(n) =
g(n // 2) + g(n // 3), reaches only a few values from one large n: 438 of them for n = 10¹², where a bottom-up
table would need more than 10¹² cells.
| Criterion | Top-down: recursion with a cache | Bottom-up: a table in order |
|---|---|---|
| Coding | Almost a copy of the recurrence | Needs an order in which smaller states come first |
| States | Only those reached from the start | Every state in the table |
| Depth | Up to the longest chain of states; Python stops at about 1,000 by default | None |
| Memory | The cache holds every state reached | Often one or two rows, kept as rolling arrays |
| When to choose | Sparse or irregular states, and a first working version | Long chains of states, tight memory, and Python or JavaScript on deep inputs |
In an interview, a top-down version is often the fastest way to a correct answer. Say how deep it recurses; if the
depth can reach the limits, convert it to bottom-up. Raising the limit with sys.setrecursionlimit is the other way
out, but only with care: the sys documentation cautions that too high a limit can make Python crash.
Practise: twenty sketches
The quiz below has twenty more original sketches, unlabeled and in no particular order. Choose the pattern you would try first; each explanation says why and links to the lesson that teaches the pattern.
Check yourself
20 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
What tells you that a problem needs dynamic programming rather than a greedy rule? (warm-up)
Three signs together. The problem is a sequence of choices; the answer for the whole is built from answers to smaller versions of the same problem; and those smaller versions repeat. A greedy rule commits to one choice and never looks back, so it is only right when some argument, such as an exchange argument, shows that the choice it makes is never worse than any other. The quickest test is a counterexample hunt: write a brute force for small inputs and compare. If greedy fails, for example the largest coin first with coins 1, 4 and 6 on an amount of 8, give each subproblem a name in words and write the recurrence. “Count the ways” almost always means dynamic programming, since a greedy rule produces one answer, not a count.
Key takeaways
- Read every statement three times: the shape of the input, the words of the question and the limits.
- A clue suggests a pattern; the property to check, in the table’s second column, decides whether it is correct.
- The limits cross out patterns before you start: n ≤ 20 keeps subsets on the list, n ≥ 10⁵ leaves only O(n log n) or better, and negative values rule out windows over sums and Dijkstra’s algorithm.
- Check a greedy rule or a window against a brute force on every small input: in the run, a rule that was right on 93 % of random sets failed on three talks.
- Write a dynamic program top-down for sparse states and a quick first version, bottom-up for deep chains and tight memory.
References
- TimeComplexity (Python Wiki) (Python Software Foundation)
- sys.getrecursionlimit() and sys.setrecursionlimit() (The Python Standard Library) (Python Software Foundation)
- functools.cache and functools.lru_cache (The Python Standard Library) (Python Software Foundation)
- bisect: array bisection algorithm (The Python Standard Library) (Python Software Foundation)
- itertools.combinations and itertools.product (The Python Standard Library) (Python Software Foundation)
- The theory of dynamic programming (R. Bellman, Bulletin of the American Mathematical Society 60(6)) (American Mathematical Society)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress