Review
Every pattern on one page Each card starts with the signals in a problem statement that point to the pattern, then gives its walk, notebook, promise and cost. Use it to review before a mock or an interview, and turn on quiz mode to practice saying the four answers before you look.
In quiz mode, read the signals, name the pattern, say its walk, notebook, promise and cost out loud, then reveal. Loops and basics One pass over a list or string answers it Running total, count, best so far
Walk Left to right, each item once.
Notebook One or two values: a total, a count, a best so far.
Promise After each item, the notebook answers the question for the items seen so far.
Cost O(n) time, O(1) space. Hash maps and sets Pairs that add to a target, complements Seen before, duplicates, first unique Count or group by a key
Walk Left to right, once.
Notebook A dict or set of what has been passed (value to index, or counts).
Promise The dict holds exactly the items to the left of the current one.
Cost O(n) time, O(n) space. Prefix sums Sum of a range, many range queries Subarray sum equals k (negatives allowed) Product of everything except one item
Walk Left to right, keeping a running total.
Notebook The total so far, and how many times each total has appeared.
Promise Any range sum is a difference of two prefix totals.
Cost O(n) time, O(n) space. Two pointers Sorted input and a pair or triple Palindromes, reversing in place Compare the two ends and move one
Walk From both ends inward.
Notebook left and right.
Promise Nothing outside left..right can be part of a better answer.
Cost O(n) time after sorting, O(1) space. Sliding window Contiguous subarray or substring Longest or shortest stretch that obeys a rule Exactly k consecutive items
Walk The right edge moves every step; the left edge catches up.
Notebook What is inside the window: a sum, a set, counts.
Promise After the inner loop, the window obeys the rule.
Cost O(n) time: each pointer moves at most n times. Stack Matching brackets, nesting Undo the most recent thing Evaluate an expression
Walk Left to right, once.
Notebook A stack of items still open or waiting.
Promise The top of the stack is the most recent unfinished item.
Cost O(n) time, O(n) space. Monotonic stack Next greater or smaller item How many days until warmer, spans Largest rectangle
Walk Left to right, once.
Notebook A stack of indexes still waiting for an answer.
Promise The values at the stacked indexes stay in order (decreasing for next greater).
Cost O(n) time: each index is pushed and popped at most once. Queues and deques Process in arrival order Recent events in a time window Maximum of every window (monotonic deque)
Walk Items in the order they arrive.
Notebook A deque: add at one end, remove at the other in O(1).
Promise The deque holds exactly the items still relevant, in order.
Cost O(n) time, O(n) space. Sorting Sorting puts duplicates next to each other Merge two sorted things
Walk Sort first, then one pass.
Notebook The sorted list, plus whatever the pass needs.
Promise After sorting, related items sit next to each other.
Cost O(n log n) time for the sort. Binary search Sorted input and a target Minimum or maximum value that still works n up to 10⁹ for the answer
Walk Halve the range each step.
Notebook lo and hi.
Promise If the answer exists, it is between lo and hi.
Cost O(log n) steps. Sort by start and sweep Meetings, bookings, ranges that overlap How many at the same time Merge or insert ranges
Walk Sort by start, then sweep left to right.
Notebook The last merged interval, or the end times still running.
Promise Everything before the current interval is already merged or counted.
Cost O(n log n) time for the sort. Linked lists Nodes with next pointers Reverse, merge, find the middle Cycle detection with O(1) space
Walk Node by node (or two pointers at different speeds).
Notebook A few node names: prev, cur, next, slow, fast.
Promise prev heads the finished part; cur heads the rest.
Cost O(n) time, O(1) space. Recursion A problem that contains smaller copies of itself Fast power, halving
Walk Call yourself on a smaller input until a base case.
Notebook The call stack.
Promise Each call returns the right answer for its own input.
Cost Number of calls times work per call; O(depth) stack space. Trees, depth-first Depth, diameter, paths in a tree What a node needs from its children
Walk A node, then its children, recursively.
Notebook The call stack, plus one best-so-far when needed.
Promise Each call returns the answer for its subtree.
Cost O(n) time, O(h) space for height h. Tree level by level (breadth-first) Level by level, right side view Minimum depth, nearest leaf
Walk Level by level with a queue.
Notebook A deque of the nodes on the current level.
Promise At the start of each round, the queue holds exactly one level.
Cost O(n) time, O(w) space for the widest level. Binary search tree Binary search tree, kth smallest Validate ordering of a tree
Walk One path down, left or right by comparison (or inorder for sorted order).
Notebook Bounds passed down, or a counter.
Promise Left subtree smaller, right subtree larger, at every node.
Cost O(h) for one path, O(n) for a full walk. Heaps k largest, k closest, kth smallest Merge k sorted lists Median of a stream
Walk Each item once, pushing into a heap.
Notebook A heap of size k (min-heap; negate for max).
Promise heap[0] is the smallest item kept.
Cost O(n log k) time, O(k) space. Trie (prefix tree) Prefixes, autocomplete, starts-with Many words searched at once
Walk One character at a time down the tree.
Notebook Nested dicts of children, with an end-of-word mark.
Promise A path from the root spells a prefix of an inserted word.
Cost O(L) per word of length L. Depth-first search Islands, regions, connected parts Can you reach it at all
Walk As deep as possible, then back up.
Notebook A visited set (or mark the grid).
Promise Every cell reachable from the start is visited exactly once.
Cost O(V + E) time. Breadth-first search Fewest steps, shortest path with no weights Spreading from many sources (rotting, fire)
Walk Ring by ring from the start, with a queue.
Notebook The queue and a visited set or distances.
Promise The first time a node is reached is by a shortest path.
Cost O(V + E) time. Topological sort Prerequisites, dependencies, build order Detect a cycle in a directed graph
Walk Tasks in the order they become ready.
Notebook In-degrees and a queue of ready tasks.
Promise A task is output only after all its prerequisites.
Cost O(V + E) time. Union-find Groups that merge as edges arrive Count components, find the edge that makes a cycle
Walk Edge by edge.
Notebook A parent list; roots name the groups.
Promise Two items share a root exactly when they are connected.
Cost Nearly O(1) per operation. Dijkstra's shortest paths Weighted edges, cheapest or fastest route Non-negative costs
Walk Always settle the closest unsettled node next.
Notebook Best distances and a heap of (distance, node).
Promise A node's distance is final when first popped.
Cost O((V + E) log V) time. Backtracking All subsets, permutations, combinations Place items under constraints (queens, words on a grid)
Walk Every choice, one at a time.
Notebook path, the choices so far (undone on the way back).
Promise path is always a valid partial answer.
Cost Exponential: 2ⁿ subsets, n! permutations. Dynamic programming, 1D Number of ways, min or max cost, can you reach Each answer reuses answers for smaller inputs
Walk Smallest subproblem to largest.
Notebook A table dp[i] (often only the last two values).
Promise dp[i] is the answer for the first i items.
Cost O(n × choices) time. Dynamic programming, 2D Two strings or a grid Edit distance, common subsequence, paths
Walk Cells row by row.
Notebook A table dp[i][j].
Promise Each cell reads only cells already filled.
Cost O(m × n) time. Greedy choice Best single move each step is safe Maximum subarray, jump reach, stock prices
Walk Left to right, deciding once per item.
Notebook The best so far and one running value.
Promise No better answer was thrown away (an exchange argument).
Cost O(n) time, O(1) space. Bits and math Every number appears twice except one Count set bits, powers of two
Walk Each number once.
Notebook A running XOR or count.
Promise x ^ x = 0, so pairs cancel.
Cost O(n) time, O(1) space. Design as coding Build a class with O(1) operations Cache with eviction, key-value store with time
Walk Each method call.
Notebook Two structures that cover each other's weakness (for an LRU cache, a dict plus a doubly linked list).
Promise Both structures always describe the same contents.
Cost Stated per operation, usually O(1) or O(log n). 