Master Cheat Sheet
One line per need. Click a row to open the topic.
Lookup
O(1) lookup by key->Hash mapMembership test / dedupe->Hash setLookup in sorted data->Binary searchOrdered keys with predecessor / successor queries->Balanced BST (tree map)Prefix matching / autocomplete->TrieProbabilistic "definitely not seen" check in tiny memory->Bloom filterkth smallest without full sort->Quickselect
Arrays
Pair with a given sum in a sorted array->Opposite-direction two pointersPair with a given sum in an unsorted array->Hash map of complementsBest contiguous range (longest / shortest / at most k)->Variable sliding windowAggregate over every window of size k->Fixed sliding windowMaximum of each sliding window->Monotonic dequeNext greater / previous smaller element->Monotonic stackMaximum subarray sum->Kadane's algorithmIn-place compaction / remove duplicates->Same-direction two pointersPartition around a pivot / sort 3 colors->Partitioning (Dutch national flag)Top K elements->Heap of size kStable sort of general data->Merge sortSort small integers / fixed-width keys in O(n)->Counting / radix sortSubsets of a set with n <= 20->Bitmask enumerationElement that appears an odd number of times->XOR fold
Ranges
Repeated range sums on a static array->Prefix sumRange sums on a 2D grid->2D prefix sumMany range updates, then point queries->Difference arrayRange min / max / gcd on a static array->Sparse tableRange query with point updates (sum)->Fenwick treeRange query with updates (min / max / custom)->Segment treeCount of subarrays with sum k->Prefix sum + hash mapOverlapping intervals / merge them->Sort by start and sweepMaximum non-overlapping intervals->Sort by end time (greedy)Which stored intervals overlap a point->Interval tree
Graphs
Shortest path, unweighted->BFSShortest path, weights 0 and 1 only->0-1 BFS with a dequeShortest path, non-negative weights->DijkstraShortest path with negative weights or at most k edges->Bellman-FordAll-pairs shortest paths (n <= ~400)->Floyd-WarshallShortest path with a good heuristic->A*Dependencies / prerequisites ordering->Topological sortConnectivity as edges arrive->Union-FindConnected components of a static graph->DFS / BFS flood fillMinimum spanning tree (sparse)->Kruskal's algorithmMinimum spanning tree (dense)->Prim's algorithmCycle in a directed graph->DFS with colors / Kahn'sStrongly connected components->Tarjan / KosarajuBridges / critical connections->Tarjan low-linkArticulation points->DFS low-linkTwo-colorable / bipartite check->BFS 2-coloringPath using every edge once->Euler path (Hierholzer)Visit all nodes with n <= 16->Bitmask DP / BFS on (node, mask)
Trees
Strings
Substring search in O(n + m)->KMPMultiple pattern hashes / plagiarism-style match->Rabin-KarpAll palindromic substrings in O(n)->Manacher's algorithmIs it a palindrome->Opposite-direction two pointersLongest prefix that is also a suffix->Z-algorithm / KMP failure tableCompare many substrings quickly->Rolling hashMatch many patterns in one pass->Aho-CorasickBracket matching / nesting->StackAnagram grouping->Hash map keyed by sorted string / countsEdit distance / LCS between two strings->2D DP
Optimization
All possibilities / arrangements->BacktrackingRepeated subproblems->MemoizationBottom-up table, O(1) per state->TabulationChoose items under a capacity->0/1 knapsack DPLongest increasing subsequence->DP or patience sorting with binary searchScheduling with deadlines and profits->Greedy + Union-Find on slotsLocal choice provably optimal->GreedyMinimum "answer" satisfying a monotonic check->Binary search on the answerOptimal prefix-free encoding->Huffman codingSplit, solve halves, combine->Divide and conquer
Math
Count primes up to n->Sieve of Eratosthenesx^n fast / modular power->Fast exponentiationgcd / lcm->Euclid's algorithmnCr mod p->Factorials + modular inverseDivision under a modulus->Modular inverse (Fermat)Prime factors of n->Trial division to sqrt(n)Is n a power of two->n & (n - 1) == 0Count set bits->Kernighan's trick / popcount
Design
LRU eviction->Hash map + doubly linked listLFU eviction->Hash maps of frequency bucketsMedian of a stream->Two heapsK-way merge of sorted streams->Min-heap of headsCycle in a linked list->Fast & slow pointersFIFO buffer with fixed capacity->Circular queuePush / pop / min in O(1)->Stack with auxiliary min stackInsert / delete / getRandom in O(1)->Array + hash map of indicesOrdered set without rebalancing code->Skip listCustom priority scheduling->Priority queue