Problem-Solving Pattern Library

Create a dedicated pattern library.

Create a dedicated pattern library. Each pattern page must include recognition signals, a template, proof/invariant, complexity, failure cases, and a curated problem ladder.

Each row below is one pattern: how to recognise it, the core idea or invariant, its usual cost, when it fails, where this course teaches it, and an easy → medium → hard ladder (problem types described in our own words).

Template / invariant Frequency counting / hash map “how many”, duplicates, pairs summing to a target count or index values in a map in one pass O(n) expected adversarial hashing; order needed first unique character → two-sum → subarrays with sum k Sorting + scanning grouping, closest pairs, overlaps sort once, then a linear pass relies on order order must be preserved contains duplicate → merge intervals → minimum arrows to burst balloons sorted input, pairs/triples, in-place filtering discard one candidate per step; invariant proves it safe unsorted input without sorting two-sum II → three-sum → trapping rain water longest/shortest contiguous segment with a property expand right, shrink left while invalid validity not monotonic (negatives) max average subarray → longest unique substring → minimum window substring Prefix sums / prefix XOR many range-sum queries; subarray sums P[r] − P[l]; hash of prefixes O(n) build, O(1) query updates between queries range sum query → subarray sum k → 2-D submatrix sums many range increments, then read all +v at l, −v at r, prefix pass car pooling → corporate flight bookings → range add on a grid Binary search on sorted data sorted array, “first/last position” half-open interval invariant search insert position → first and last position → rotated array search Binary search on answer

“minimise the maximum”, “smallest capacity” monotone feasibility predicate O(check · log range) predicate not monotone integer square root → ship within D days → split array largest sum Fast/slow pointers linked list cycles, middle element two speeds meet inside a cycle O(n), O(1) space random access needed middle of list → cycle detection → cycle entry / duplicate number overlapping time ranges sort by start; merge while overlapping intervals in a circle merge intervals → insert interval → employee free time Cyclic sort / index placement values in 1..n, find missing/duplicate swap each value to index value − 1 values out of range missing number → all duplicates → first missing positive reverse a list or part of an array save next, rewire, advance reverse list → reverse between positions → reverse in k-groups merge, partition, reorder lists dummy head + tail pointer merge two lists → partition list → reorder list next greater/smaller, spans, histograms pop dominated elements; each pushed/popped once next greater element → daily temperatures → largest rectangle sliding-window max/min, DP over a window front = best in window window maximum → constrained subsequence sum → shortest subarray ≥ K Top-k with heaps k largest/smallest, k closest min-heap of size k kth largest → k closest points → top k frequent words merge sorted streams heap of current heads merge k lists → smallest range covering k lists → kth smallest in sorted matrix BFS shortest path unweighted shortest moves queue by distance shortest path in a grid → word ladder → open the lock distance to the nearest of many sources start with all sources at 0 rotting oranges → distance to nearest 0 → walls and gates DFS / connected components regions, islands, reachability visited marking; iterate all starts number of islands → surrounded regions → number of distinct islands dependencies, ordering with prerequisites Kahn's indegrees / DFS finishing order cycles (detect them) course schedule → alien dictionary → parallel courses (minimum semesters) dynamic connectivity, merging groups find with compression, union by size number of provinces → redundant connection → accounts merge Backtracking and pruning “all combinations / arrangements” choose → explore → undo; prune invalid large n without pruning subsets → combination sum → N-Queens / Sudoku Memoization / DP state design overlapping subproblems, “number of ways”, optimum state, transition, base case, order states × transitions state too large climbing stairs → coin change → edit distance Greedy + exchange proof local choice seems optimal prove by exchange or staying ahead usually O(n log n) no matroid structure assign cookies → non-overlapping intervals → task scheduler Divide and conquer problem splits into independent halves solve halves, combine merge sort → count inversions → closest pair events on a line, overlaps, skylines sort events, process in order with a structure meeting rooms → the skyline → rectangle union area huge value range, few distinct values map values to ranks values must stay comparable only rank transform → count smaller after self → range module all queries known in advance reorder queries (Mo's, sorting by key) queries sorted by threshold → distinct values in ranges → dominance counting DSU on tree / small-to-large merge child data up a tree always merge smaller into larger distinct colours in subtrees → most frequent colour per subtree → path queries offline k-th ancestor, LCA, jump pointers up[k][v] = 2ᵏ-th ancestor O(log n) query k-th ancestor → LCA → path maximum with jumps Euler tour / subtree flattening subtree queries and updates tin/tout make subtrees contiguous O(log n) with a Fenwick tree path queries need HLD subtree sum → subtree add, point query → ancestor checks n ≤ 20, subsets of items dp[mask] over subsets subsets via bits → minimum cost to visit all → assignment / TSP Meet in the middle n ≈ 40, subset sums split in halves, combine sorted lists O(2^(n/2) · n) subset sum with n = 40 → closest subsequence sum → 4-sum counts Trie / prefix search prefixes, autocomplete, XOR maximisation walk characters or bits implement trie → word search II → maximum XOR pair KMP / prefix function pattern matching, periodicity, borders reuse borders on mismatch find needle → repeated substring pattern → shortest palindrome substring equality, repeated substrings prefix hashes, random base O(1) per comparison collisions (verify) repeated DNA sequences → longest duplicate substring → distinct echo substrings Quickselect / order statistics k-th element without full sort partition around a random pivot adversarial pivots (use random) kth largest → median of array → wiggle sort uniform sample from a stream keep item i with probability k/i O(n), O(k) memory random node of a list → random pick index → weighted sampling puzzles, keys and doors, extra resources vertex = full state states × moves open the lock → shortest path with obstacles removal → shortest path to get all keys games, process simulation find a quantity that never changes or always decreases can you reach the end → robot bounded in circle → gas station Prefix/suffix precomputation

“everything except i”, best to the left and right arrays of best-from-left and best-from-right product except self → trapping rain water → best time to buy and sell (two transactions) constraints x_j − x_i ≤ c shortest paths in a constraint graph Bellman–Ford O(VE) negative cycle = infeasible schedule with gaps → seating constraints → system feasibility costs on moves between states build the graph, pick BFS/0–1 BFS/Dijkstra negative weights with Dijkstra network delay time → cheapest flights with k stops → path with minimum effort Flow / matching modelling assignments, disjoint paths, capacities source → … → sink with capacities Dinic O(V²E) maximum bipartite matching → assign tasks to workers → minimum cut in a grid

Quiz

? “Minimise the largest sum when splitting an array into k parts” suggests which pattern?
+ Binary search on the answer :: Feasibility (“can every part stay ≤ X?”) is monotone in X.
- Two pointers :: Not directly.
- Trie :: No.
- Topological sort :: No.

? “Distance from every cell to the nearest hospital” suggests…
+ Multi-source BFS :: All hospitals start at distance 0.
- One BFS per hospital :: Correct but much slower.
- Dijkstra from every cell :: Far slower.
- Union-Find :: Connectivity, not distances.

? Which signals point to bitmask DP? (select all that apply)
+ n ≤ 20 :: 2ⁿ states are affordable.
+ “visit every item exactly once” :: TSP-like.
- n up to 10⁶ :: Far too many states.
+ Assignments between two small sets :: Assignment DP.