Pattern cheat sheet

This is the page to reread before a contest or an interview. It compresses the whole book into signals, tools, and typical costs. When a problem lands in front of you, run down this list and something will click.

Signal to pattern

The problem says or implies	Try this pattern	Typical time
Seen this value before, count, or pair up	Hash map or set	O(n)
Sorted array, pair summing to a target, palindrome	Two pointers	O(n)
Longest or shortest contiguous run	Sliding window	O(n)
Matching brackets, next greater, undo	Stack	O(n)
Sorted data, or "smallest value that works"	Binary search	O(log n)
Reverse, middle, cycle in a chain	Linked list pointers	O(n)
Depth, height, path sum in a tree	DFS recursion	O(n)
Level by level, shortest unweighted path	BFS with a queue	O(n)
Kth largest, top K, running median	Heap	O(n log k)
All subsets, permutations, combinations	Backtracking	exponential
Islands, connected groups, reachability	DFS or BFS on a graph	O(nodes + edges)
Prerequisites, build order	Topological sort	O(nodes + edges)
Min or max cost, number of ways, overlapping subproblems	Dynamic programming	O(states)
Locally best choice provably safe	Greedy	O(n log n) with a sort
Overlapping ranges, meeting rooms	Intervals, sort first	O(n log n)
Appears once among pairs, flags, toggles	Bit manipulation	O(n)

The decision flow, in words

Start by reading the constraints. If n is tiny (up to about 20), an exponential backtracking solution is probably fine and maybe expected. If n is large (100,000 or more), you need roughly O(n) or O(n log n), which rules out nested loops.

Next, look at the shape of the data. Is it sorted, or would sorting help? That points to binary search, two pointers, or a greedy sweep. Is it a tree or a grid or a network? That points to DFS and BFS. Is it a string or array asking for a contiguous best? That is a sliding window.

Finally, look at what is being asked. "How many ways" or "min / max with subproblems" is dynamic programming. "All of something" is backtracking. "The Kth best" is a heap. "Have I seen this" is a hash map.

W H E N Y O U A R E T O T A L L Y S T U C K

Write the brute force anyway. Getting a slow but correct solution on the board does three things: it proves you understood the problem, it often reveals the repeated work you can cut, and it gives you partial credit. Then ask the one question that unlocks most optimizations: "what am I recomputing, and can I remember it instead?"

Complexity reference for common operations

Operation	Cost
Hash map or set lookup, insert, delete	O(1) average
Array index access	O(1)
Append to a dynamic array or list	O(1) amortized
Insert or delete in the middle of an array	O(n)
Sorting	O(n log n)
Binary search on a sorted array	O(log n)
Heap push or pop	O(log n)
BFS or DFS over a graph	O(nodes + edges)