Appendix C - Algorithm Pattern Cards

Use a card to eliminate, not to identify

A familiar noun can suggest several algorithms. “Contiguous” might lead to a sliding window, two pointers, prefix sums, or dynamic programming. The result and constraints decide which candidates survive. A useful card therefore has two doors: a trigger that admits the pattern and a rejection test that can send you elsewhere.

Start with a brute-force solution. Name the repeated or impossible work. Then choose a pattern only if its invariant permits that work to be discarded. This keeps recall in its proper role: narrowing the search without replacing the reasoning.

Each card below carries six things worth retrieving: when to consider the pattern, when to reject it, the state it keeps, the invariant that makes progress safe, the cost to account for, and representative problems on which to rehearse it.

Exact lookup and prefix counting

Consider it when the repeated operation is membership, frequency, an exact complement, or the number of earlier prefixes with a particular value. A hash set answers “have I seen this?”; a count map answers “how many times?”

Reject it when the query needs order, predecessor, nearest value, or a bounded range rather than exact lookup. An unordered map does not preserve those relationships.

State and invariant. The map describes exactly the processed portion of the input. In a prefix-count scan, insert the current prefix only after using earlier prefixes, so the map cannot count the current boundary as its own start. Multiplicity belongs in the state when distinct positions produce distinct answers.

Cost and trap. A single scan with hash lookup is expected O(n) time and may use O(n) space. Watch update order, duplicate values, mutable keys, and any claim that hashing is worst-case constant time.

Rehearse with: Two Sum, Group Anagrams, Subarray Sum Equals K, and Longest Consecutive Sequence.

Two pointers

Consider it when ordering lets one move discard a whole region of candidates: a pair in a sorted array, an in-place partition, or a comparison from both ends.

Reject it when the input cannot be ordered without losing required identity, or when moving a pointer does not rule out any remaining answer.

State and invariant. Keep the live boundaries and the best result found. After each move, every position outside the boundaries is either settled or proved irrelevant. The proof must explain why the chosen comparison permits that discard.

Cost and trap. The scan is usually O(n) after any sorting cost. Watch duplicate handling, reuse of the same index, skipped answers when both pointers move, and accidental mutation of input the caller expected to keep.

Rehearse with: Two Sum II, Three Sum, Container With Most Water, and Remove Duplicates from Sorted Array.

Sliding window

Consider it when the result concerns one contiguous range and validity can be restored by advancing the left boundary as the right boundary advances. Fixed-size windows are a special case; variable windows need a monotone rule for becoming valid or invalid.

Reject it when adding or removing an item can change validity in both directions. Negative values, for example, break the usual sum-window argument. A single active window also cannot automatically count every overlapping range.

State and invariant. Keep left, right, the information needed to test the current range, and the answer. Before recording a valid result, the window must have the promised form: valid, minimally valid, or maximally extended, depending on the problem.

Cost and trap. If each boundary only advances, total work is O(n), even with a loop that shrinks the window. Watch whether the answer is recorded before or after restoration and whether duplicate counts are removed at zero.

Rehearse with: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum with positive values, and Minimum Window Substring.

Binary search

Consider it when the input is ordered or the question can be written as a monotone predicate: once a candidate becomes feasible, every larger candidate is feasible too, or the reverse.

Reject it when the predicate can switch back and forth. “Can we do it?” is not enough; feasibility must divide the search space into two ordered regions.

State and invariant. The boundaries enclose every remaining answer. Each comparison proves that one side cannot contain the requested boundary or optimum. Decide whether the interval is closed or half-open before coding and keep that convention throughout.

Cost and trap. Ordinary search takes O(log n) comparisons. Search on an answer costs O(log R) predicate evaluations over range R, multiplied by the predicate cost. Watch equality, termination, overflow in midpoint arithmetic, and confusion between finding any match and finding a boundary.

Rehearse with: First and Last Position, Search in Rotated Sorted Array, Koko Eating Bananas, and Capacity to Ship Packages Within D Days.

Intervals and sweep lines

Consider it when ranges overlap, resources become active and inactive over time, or the answer changes only at ordered endpoints.

Reject it when order is irrelevant or a direct count answers the question without sorting. Do not build a sweep merely because the input contains times.

State and invariant. After sorting, the merged prefix is final, or the active structure represents exactly the intervals crossing the current coordinate. Endpoint semantics belong in the model: touching closed intervals and adjacent half-open intervals are different cases.

Cost and trap. Sorting usually sets the cost at O(n log n); the sweep is often linear afterward. Watch start/end tie order, open versus closed bounds, and returning a count when the prompt requires the actual assignment.

Rehearse with: Merge Intervals, Insert Interval, Meeting Rooms II, and a maximum-concurrent-sessions sweep.

Monotonic stacks and deques

Consider it when the result asks for the next greater or smaller item, a nearest boundary, or the best candidate in a moving window. A new item can discard older candidates it dominates for every future query.

Reject it when a discarded candidate could become useful again. The dominance argument, not the desire for a linear solution, is the entry ticket.

State and invariant. The stack or deque stores unresolved candidates in monotonic order. Everything removed from the back is dominated; everything removed from the front has left the permitted range.

Cost and trap. Each item enters and leaves at most once, giving O(n) total work. Watch strict versus non-strict comparison, value versus index, equal heights, and expiring an index at the wrong boundary.

Rehearse with: Daily Temperatures, Largest Rectangle in Histogram, Next Greater Element, and Sliding Window Maximum.

Heaps and bounded best sets

Consider it when the next item is chosen by priority, several ordered sources must be merged, or only the best k items seen so far must survive.

Reject it when the problem needs arbitrary ordered lookup or the entire result sorted. A heap exposes one extreme; it is not a sorted collection.

State and invariant. For a merge, the root is the smallest unseen item across all represented sources. For streaming top k, the root is the worst member of the best set retained so far.

Cost and trap. A heap of size k gives O(log k) update cost. Merging N items from k sources costs O(N log k). Watch min-heap versus max-heap direction, deterministic ties, stale entries, and a heap that quietly grows beyond the bound used in the complexity claim.

Rehearse with: Merge K Sorted Lists, Kth Largest Element in a Stream, Top K Frequent Elements, and task scheduling with release times.

Breadth-first and depth-first search

Consider them when the input defines reachable states and transitions. BFS is especially useful for fewest transitions in an unweighted graph; DFS is natural for exhaustive reachability, component work, and postorder relationships.

Reject ordinary BFS for weighted shortest paths. Reject node-only visited state when arriving at the same node with a different resource, mask, or phase changes the legal future.

State and invariant. The frontier contains discovered but unprocessed states. In BFS, the queue is ordered by nondecreasing distance when every edge has equal cost. In DFS, the active path and completed states must remain distinct when cycle detection depends on that difference.

Cost and trap. With adjacency lists, a complete traversal is O(V + E). Implicit graphs may generate far more neighbors than the visible input size suggests. Watch marking visited too late, losing necessary state in the key, recursion depth, and confusing a graph with a tree.

Rehearse with: Number of Islands, Clone Graph, Word Ladder, and shortest path through a grid with an additional state constraint.

Topological order

Consider it when directed prerequisites constrain a schedule or when a dynamic-programming state depends on an acyclic graph of earlier states.

Reject it when dependencies are undirected, when every valid order must be enumerated, or when cycles are permitted and need a different representation.

State and invariant. Maintain adjacency and either indegrees plus a queue, or DFS colors plus a postorder. With Kahn’s algorithm, a node enters the output only after every remaining prerequisite has been removed.

Cost and trap. Building and traversing the graph costs O(V + E). If the output contains fewer than V nodes, a directed cycle remains. Watch missing isolated nodes, reversed edge direction, duplicate edges, and claims of a unique order when several zero-indegree choices exist.

Rehearse with: Course Schedule I and II, Alien Dictionary, and Build Order.

Union-find

Consider it when the questions concern equivalence or connectivity as edges are added, particularly when they can be answered offline. The structure is good at merging components and asking whether two items share a component.

Reject it when you need the path between nodes, directed reachability, connectivity under arbitrary deletions, or the exact history of how a component formed.

State and invariant. Every item follows parent links to one representative root, and two items are connected exactly when their roots match. Union by size or rank controls tree growth; path compression shortens later searches without changing component identity.

Cost and trap. A sequence of operations is effectively near-linear with both optimizations. Watch uninitialized singleton nodes, comparing immediate parents instead of roots, losing component counts, and applying the structure to a time direction it cannot represent.

Rehearse with: Number of Connected Components, Redundant Connection, Accounts Merge, and offline connectivity as edges arrive.

Backtracking

Consider it when the output enumerates constructions and each step chooses among alternatives that can be rejected from a partial candidate.

Reject it when the prompt asks only for a count or optimum and equivalent partial histories can be merged into a smaller dynamic-programming state.

State and invariant. The current path is a valid partial construction. Every legal continuation is explored once, and any mutation made before a recursive call is undone before the next sibling branch.

Cost and trap. Cost usually follows branching factor, depth, and output size; pruning reduces explored work but does not make an exponential search polynomial by declaration. Watch state restoration, duplicate choices, aliasing a mutable result, and pruning without proving that no solution lies below the cut branch.

Rehearse with: Generate Parentheses, Combination Sum, Permutations with duplicates, and Word Search.

Greedy choice

Consider it when a locally best choice can be exchanged into an optimal solution, or the partial solution can be shown to stay ahead of every rival on the measure that determines the result.

Reject it when the justification is only that the choice “looks best now.” One small counterexample is enough to invalidate a proposed greedy rule.

State and invariant. Keep the chosen prefix and the resource or boundary that governs the next choice. The proof must show that committing now never removes all optimal completions.

Cost and trap. Sorting often dominates at O(n log n); the selection pass may be linear. Watch a comparator that does not express the proof, hidden dependence on future choices, and confusing a heuristic that performs well with an algorithm guaranteed to be optimal.

Rehearse with: Non-overlapping Intervals, Jump Game, Gas Station, and a counterexample to greedy coin change using denominations [1, 3, 4].

Dynamic programming

Consider it when recursive choices revisit equivalent states and the future depends only on a compact description of the past. The state definition must answer a complete sentence such as “the best result for this prefix and remaining capacity.”

Reject it when the chosen key merges histories with different legal futures, or when the problem has enough structure for a direct greedy or linear invariant.

State and invariant. Each stored state has one precise meaning, and every transition reads states already known to be correct. Base cases represent the smallest valid worlds, not merely values that make the recurrence run.

Cost and trap. Time is the number of reachable states multiplied by the transition work; space is the retained state. Watch an incomplete key, iteration in an order that reads current-layer values too early, impossible states represented as real answers, and space optimization before the dependency direction is understood.

Rehearse with: Coin Change, Partition Equal Subset Sum, Longest Common Subsequence, and Edit Distance.

Rehearse the decision, not the label

Choose a mixed problem and write the brute force first. Circle its bottleneck, then put two candidate cards beside it. For each candidate, name the constraint that would disqualify it. Only then write the chosen invariant and trace one boundary case by hand.

After the implementation works, change one promise: introduce negative values, weights, duplicate output, streaming input, updates, or a much larger n. Locate the first sentence of the invariant that becomes false. That sentence tells you whether to change a data structure, enlarge the state, or discard the pattern altogether.

The entire retrieval loop fits on one line:

result -> constraints -> brute force -> bottleneck -> candidate -> rejection test -> invariant -> cost -> boundary tests

If you stall, return to the brute force and improve one dimension. Recovery is easier when you still know which work the optimized algorithm was meant to remove.

Related links

• Arrays and Strings
• Hash Maps and Sets
• Graphs
• Dynamic Programming
• Pattern Selection and Proof