Store what you have seen so far so future questions are answered in constant time.

a.k.a. hashtable, dictionary, hashmap

Applies to

O(1) membership and pairing problems

1. Decide the key that uniquely describes past state.
2. Build the entry before or after each lookup, depending on the question.
3. Return "the thing I needed earlier" when the map answers it.

Count every item first, then let the counts answer comparison, majority and top-k questions.

a.k.a. counts, letter counts

Applies to

Counting occurrences before deciding about a collection

1. Walk the input once building value → count.
2. Compare counts when the problem asks about equality or balance.
3. Read the counts out in the shape the problem's answer expects.

Precompute running totals so any range is a difference of two prefixes.

a.k.a. prefix, cumulative, precompute

Applies to

Range queries over static arrays

1. Build the cumulative array in one pass.
2. Express the range answer as prefix[r] − prefix[l−1].
3. Watch for off-by-one and integer overflow.

Carry one running candidate while you walk, so the best answer is always available at the end.

a.k.a. rolling min, tracking extrema

Applies to

Best-so-far decisions over time

1. Initialise the running value from the first element.
2. Update it when the new element beats the candidate.
3. Use the running value to answer the follow-up question each step.

Swap each value into its index slot in O(1) space; whatever is out of place is the anomaly.

a.k.a. in-place index sort, 1..n placement

Applies to

Arrays of 1..n with one missing or duplicate

1. While cycling, swap a[i] to position a[i]−1 whenever i isn't already correct.
2. Advance only when the slot holds the right value.
3. After one pass the misplaced element identifies the missing or duplicate.

Keep low, mid and high pointers and partition three buckets in-place in one sweep.

a.k.a. 3 partition, sort colors

Applies to

Sorting three distinct values with one pass

1. Left groups the low value, right groups the high value, mid scans the middle.
2. Swap mid with left or right so each bucket stays contiguous.
3. Stop mid crossing the right pointer; the array is sorted in three zones.

Pair candidates against each other; the majority survives every cancellation.

a.k.a. majority element, vote counting

Applies to

Finding an element present more than n/2 times

1. Keep a candidate and a counter that starts at zero.
2. Increment when the value matches the candidate, else decrement.
3. When the counter hits zero, adopt the current value as the candidate.

A set answers 'seen before?' in O(1); the second sighting is usually the answer.

a.k.a. contains duplicate, seen set

Applies to

Any question that asks 'has this appeared before?'

1. Add each element to the set as you meet it.
2. If Add returns false, a duplicate exists — act immediately.
3. At the end an empty-duplicate scan means every element was unique.

Use the array itself as the visited set by flipping the sign at each value's index.

a.k.a. sign flip, negation marking

Applies to

Detecting duplicates or missing values in bounded arrays in place

1. For each value v, inspect index |v|−1.
2. Flip the sign there; a negative on revisit means the value is a duplicate.
3. Value-range guaranteed ≤ n makes index marking safe.

Record deltas at range boundaries instead of touching every overlapped cell.

a.k.a. range add, diff array

Applies to

Many range-update queries answered at the end

1. For each range [l, r] with delta d, add d at l and subtract d at r+1.
2. After all ranges, compute the prefix sum of the diff array.
3. The running total at index i is the true value there.

Reduce each item to a canonical key, then group identical keys — the whole trick.

a.k.a. normalise then group, signature

Applies to

Grouping items that share a normalised shape

1. Decide the canonical form: sorted string, char counts, or normalised encoding.
2. Map canonical key → list of items.
3. Return the groups; anything in the same bucket is equivalent.

Move a left and right pointer inward (or side-by-side) to avoid nested loops.

a.k.a. 2 pointers, pointer

Applies to

Sorted arrays and linked lists

1. Start pointers at opposite ends (or the same head).
2. Apply one rule that decides which pointer moves.
3. Stop when the pointers meet or one runs off the end.

Start at both ends; every step moves exactly one end based on one comparison rule.

a.k.a. left/right sweep, inward scan

Applies to

Sorted arrays where answers sit at both extremes

1. Compare the pair under both pointers against the target.
2. Move the pointer whose move can only improve the direction you need.
3. Terminate when the pointers cross.

One pointer runs ahead; the other chases to maintain an invariant gap.

a.k.a. two runners, fast behind slow

Applies to

Arrays and lists where a gap between two cursors is the answer

1. Advance one pointer first to create the initial gap.
2. Move both together, checking the invariant at the rear pointer.
3. The gap width encodes the answer you report.

A fast pointer moves twice as fast as a slow one; a cycle forces them to collide.

a.k.a. tortoise, hare, cycle detection

Applies to

Linked lists, cycles, middle nodes

1. Advance slow by 1 and fast by 2 each step.
2. If they meet inside the list, a cycle exists.
3. Fast reaching the end proves the list is acyclic.

Either compare mirrored ends or expand outward from a centre — never compare all pairs.

a.k.a. mirror scan, expand around centre

Applies to

Palindromic substrings and symmetric checks

1. Pick the centre: a single char (odd) or a gap (even).
2. Expand both directions while characters mirror.
3. Record each stretched palindrome; the longest wins.

Three reverses — whole, left part, right part — rotate an array without extra space.

a.k.a. reverse then mutate, rotate by reverse

Applies to

Rotations, in-place transforms, and swap-heavy edits

1. Normalise the rotation amount modulo the length.
2. Reverse the whole array, then each partition separately.
3. The result is the rotation, done in O(1) space.

Grow a window with the right edge, shrink with the left, and track a property of the window.

a.k.a. window, substring

Applies to

Contiguous subarrays / substrings

1. Expand the right edge to include a new element.
2. While the window violates the constraint, advance the left edge.
3. Record the answer at the moment the window is valid.

Slide a window of constant size; update the aggregate by evicting one and adding one.

a.k.a. k-length window, constant window

Applies to

Problems with a window of a known length k

1. Build the first window of size k and aggregate it.
2. Slide right: remove a[left], add a[right].
3. Evaluate the aggregate at each position.

Expand to make progress, shrink to restore validity, and keep the max valid length.

a.k.a. expand contract, valid longest

Applies to

Longest subarray/substring satisfying a constraint

1. Track counts so you know when the window becomes invalid.
2. Shrink from the left until valid again.
3. Update the best length every time the window is valid.

Expand until every target is present, then shrink to minimise while staying valid.

a.k.a. enclosing window, minimum covering

Applies to

Smallest window containing all targets

1. Grow the right edge until all required conditions are met.
2. Try shrinking the left edge while the window stays valid.
3. Track the window with the smallest length seen.

For every valid window ending at r, all sub-windows ending at r are valid — count them in bulk.

a.k.a. subarray count, windows satisfying constraint

Applies to

Counting subarrays by a validity rule

1. Run a standard left-shrinking window.
2. When valid at r, add (r − left + 1) to the answer.
3. That one arithmetic brainhands every sub-window ending at r.

Push toward matching, pop toward closing; a stack enforces reverse order naturally.

a.k.a. paren stack, matching stack

Applies to

Symbols that must close in reverse order

1. Push the expected closer for each opener.
2. On a closer, it must equal the top of the stack — else invalid.
3. The stack must be empty at the end.

Keep the stack sorted; pop dominated entries so the extreme stays answerable in O(1).

a.k.a. next greater, next smaller

Applies to

Next greater/smaller and dominance problems

1. While the candidate dominates the back, pop it.
2. The element you pop now resolves its 'next greater' to the candidate.
3. Push the candidate; indices live in the stack, values in the array.

A deque holding candidates in sorted order gives the window extreme in O(1).

a.k.a. deque, window max deque

Applies to

Sliding window extremes in O(n)

1. Pop the back while it can never beat the new element.
2. Pop the front when it leaves the window.
3. The front is always the extreme of the current window.

Store the current minimum alongside each pushed value so history never lies.

a.k.a. tracking min, paired stack

Applies to

O(1) min query alongside O(1) push/pop

1. Push (value, min-so-far) pairs or a parallel min stack.
2. On pop, discard that level's min too.
3. Peek the min stack for the running minimum.

Two stacks — one for enqueue, one for dequeue — give FIFO with amortised O(1) ops.

a.k.a. stack to queue, amortised queue

Applies to

Building one abstract data type from another

1. Push new items onto the 'in' stack.
2. Move items to the 'out' stack only when it is empty.
3. Pop from 'out' for dequeue; it reverses order exactly once.

The stack height at any point is the nesting depth; scores compound as you descend.

a.k.a. depth tracking, nesting level

Applies to

Parsing nesting levels and weighted nesting values

1. Increase a depth counter when opening, decrease on closing.
2. Record the maximum depth or apply the nesting weight.
3. Read the result once the whole input is consumed.

Halve the search space each step by comparing against the middle.

a.k.a. bs, bisect

Applies to

Sorted (or monotonic) search spaces

1. Low, high, and a loop invariant that the answer stays inside.
2. Compare the middle; decide which half to keep.
3. Watch the boundary so the loop always terminates.

Decide which side to keep even on equality to bias toward the first or the last match.

a.k.a. first occurrence, last occurrence, lower bound

Applies to

Leftmost/rightmost match in a sorted array

1. On equality, keep the left half for first-index searches.
2. Keep the right half for last-index searches.
3. Return the surviving boundary after the loop.

Compare the middle against the ends to decide which side is sorted, then search normally.

a.k.a. pivot search, rotate detect

Applies to

Sorted arrays rotated at an unknown pivot

1. Compute mid; one half is always fully sorted.
2. If the target lies in the sorted half's range, search it.
3. Otherwise drop it and search the other half.

Binary search the value space of the answer; each mid is accepted or rejected by a check.

a.k.a. feasibility search, minimax search

Applies to

Optimisation problems with a monotonic feasibility check

1. Set low/high to the tightest possible answer bounds.
2. Run a feasibility check on mid that is monotone in mid.
3. Narrow toward the best feasible answer.

Binary search a partition point in the smaller array so both sides are balanced.

a.k.a. kth element, partition around cut

Applies to

Median / k-th element of two sorted arrays

1. Binary search the cut in the shorter array.
2. Derive the other cut from total size.
3. Verify cross-order: every Left ≤ every Right, then read the median.

Compare the middle with its neighbour; the bigger side is guaranteed to hold a peak.

a.k.a. peak element, bitonic

Applies to

Finding a local extremum in O(log n)

1. Compare mid with mid+1.
2. If the right neighbour is larger, a peak lies to the right.
3. Otherwise a peak lies left (or at mid).

Start at a corner and walk one direction at a time — each step halves the remaining matrix.

a.k.a. grid binary search, staircase search

Applies to

Row- and column-sorted matrices

1. Start at the top-right (or bottom-left) corner.
2. Compare with the target: move down if larger, left if smaller.
3. Match exactly or fall off the matrix.

When f(i) is monotone, the first true index is a binary search over the index space.

a.k.a. inversion search, value in function

Applies to

Finding an index where a predicate flips

1. Define the predicate that is false then true as the index grows.
2. Binary search for the first index where it turns true.
3. Handle the all-false and all-true edges explicitly.

Rewire each node's next pointer to the previous node in one pass.

a.k.a. list reverse, reverse in place

Applies to

Reversing singly-linked structures

1. Keep prev, curr, next pointers.
2. Point curr to prev, then walk all three forward.
3. When curr is null, prev is the new head.

A dummy head and a tail walker zip two sorted lists into one.

a.k.a. merge lists, zipper merge

Applies to

Merging sorted sequences without extra arrays

1. Create a dummy node to own the result.
2. Link the smaller tail, advance that input.
3. Attach whatever remains; return dummy.next.

A dummy head removes the null/head edge cases of every deletion problem.

a.k.a. dummy head, remove nth

Applies to

Deletions at a computed position

1. Read the position with a runner.
2. Advance a second pointer until the runner reaches the end.
3. Unlink the target; return dummy.next.

Fast/slow and offset pointers locate positions without counting twice.

a.k.a. list pointers, middle of list

Applies to

Interleaving, finding middles and k-th-from-end

1. Run one pointer ahead by k steps.
2. Advance both until the lead pointer nulls out.
3. The laggard is exactly k from the end.

Couple a hash map of keys with a doubly-linked recency list of nodes.

a.k.a. lru, eviction list

Applies to

O(1) access plus O(1) recency moves

1. Hash map gives O(1) lookup of a list node.
2. Move a node to the front on access — O(1) with a doubly-linked list.
3. Evict the tail when the capacity is exceeded.

After detection, move slow to head and step both one at a time; they meet at the cycle entry.

a.k.a. cycle head, tortoise equation

Applies to

Finding where a linked-list cycle begins

1. Detect the cycle with fast/slow to find any meeting point.
2. Reset slow to the head; keep fast at the meeting point.
3. Advance both by one — the meeting node is the cycle's start.

Pre/in/post order decide when the node's own work happens relative to its children.

a.k.a. preorder, inorder, postorder

Applies to

Any order-sensitive tree work

1. Pre: root → left → right.
2. In: left → root → right (a BST becomes sorted).
3. Post: left → right → root (children first is ideal for freeing or summing).

Process nodes a level at a time: drain the queue's current size, enqueue children.

a.k.a. bfs tree, level traversal

Applies to

Row-by-row tree processing

1. Seed the queue with the root.
2. For each level, process exactly the current queue size.
3. Each drained group is one level's nodes.

Post-order recursion returns the best value each subtree can offer upward.

a.k.a. root to leaf sum, max path

Applies to

Summing or maximising values along tree paths

1. At each node, combine the best child contributions.
2. Compare the node's own arc against the running global best.
3. Return only the single best downward branch to the parent.

One post-order pass returns subtree depth/height/size to its caller.

a.k.a. tree height, diameter, size

Applies to

Structural metrics of a tree

1. Base case: empty subtree has height 0.
2. Combine child heights, adding 1 for the current edge.
3. The maximum depth-1 + depth-2 + 2 across nodes is the diameter.

Follow the ordering property to locate or prune subtrees in O(height).

a.k.a. bst range, bst path

Applies to

Ordered queries over a binary search tree

1. Compare the target with the current node's value.
2. Prune the subtree that cannot contain the answer.
3. Aggregate values within the range by skipping out-of-range branches.

A node is the LCA when it is one target, or when one target sits in each subtree.

a.k.a. lca, ancestor node

Applies to

Finding the deepest node that is an ancestor of both targets

1. Search both sides recursively for the two targets.
2. If both children return a hit, the current node is the LCA.
3. Otherwise propagate the non-null hit upward.

For trees where a node splits its remaining set, use type 1 in type 2 analogy: one traversal picks the root, the other splits the range.

a.k.a. construct tree, preorder inorder

Applies to

Rebuilding a tree from its traversals

1. Take the next root from the preorder.
2. Find its index in the inorder to split left/right ranges.
3. Recurse with the shrunk ranges.

A preorder walk with explicit null markers encodes the tree unambiguously.

a.k.a. tree encoding, preorder encode

Applies to

Persisting tree structure to a string and back

1. Serialize with preorder, emitting a marker for null.
2. Deserialize by consuming tokens and rebuilding left/right.
3. The marker list keeps the shape recoverable.

Share prefixes across stored strings so lookups cost only the pattern's length.

a.k.a. prefix tree, autocomplete tree

Applies to

Prefix lookups, word lists, auto-complete

1. Node holds children (per char) and a wordEnd flag.
2. Insert walks/creates child by child.
3. Search walks the prefix; if it ends on a wordEnd, the full word exists.

Anagram = identical letter signature; sort or count to build the key.

a.k.a. anagram key, sorted key

Applies to

Detecting or grouping anagrams

1. Build a signature per string: sorted chars or 26 counts.
2. Compare signatures to test equality.
3. Group by signature to collect all anagram classes.

Precompute a failure/hash table so the backtrack on mismatch is O(1) amortised.

a.k.a. pattern search, rabin-karp, kmp

Applies to

Finding a pattern inside text efficiently

1. Precompute the failure table (longest proper prefix = suffix).
2. Slide the pattern pointer; on mismatch fall back via the table.
3. A completed pattern window is a match; report and continue.

A palindrome needs at most one character with an odd count.

a.k.a. palindrome permutation, palindrome by rearrange

Applies to

Can a string be rearranged into a palindrome

1. Count character frequencies.
2. Count how many frequencies are odd.
3. That count must be 0 or 1 for a rearrangement to exist.

Track counts inside a window plus a 'unique' counter to test validity in O(1).

a.k.a. char window counts, frequency window

Applies to

Window problems measured in letter counts

1. Keep char counts for the current window.
2. Track the number of chars that meet the condition.
3. Add/remove one char per slide and update the counters.

Read the rule, write with a StringBuilder, and understand that strings are immutable.

a.k.a. run length, string compression, zigzag

Applies to

Rewriting a string under a deterministic rule

1. Parse the rule: grouping, spacing, or rotating.
2. Write the output with a StringBuilder.
3. Verify against the formatted example before submitting.

A heap keeps the extreme element accessible in O(log n) per push/pop.

a.k.a. priority queue, top k

Applies to

Repeated minima/maxima, top-k queries, streaming

1. Choose min-heap vs max-heap for the invariant you need.
2. For top-k, cap the heap at size k.
3. For running medians, pair a min-heap and a max-heap.

Cap a min-heap of size k so the weakest candidate is evicted, not the strongest.

a.k.a. k most frequent, k largest

Applies to

The k biggest/frequent elements of a stream

1. Push each candidate into a size-k min-heap.
2. Evict the top when the heap exceeds k.
3. The surviving k elements are the top-k.

A max-heap for the lower half and a min-heap for the upper half balance around the median.

a.k.a. median heap, max-heap min-heap

Applies to

Streaming medians and percentiles

1. Insert into the appropriate half heap.
2. Rebalance so sizes differ by at most one.
3. The median is the top of the larger (or the mean of both tops).

A heap of the heads merges k lists in O(n log k).

a.k.a. merge k, multiway merge

Applies to

Merging many sorted sequences

1. Heap the current head of every list, keyed by value.
2. Pop the smallest, link it into the result.
3. Push that list's next node and repeat.

Take the most pressing job each tick — a heap picks it in O(log n).

a.k.a. task scheduler, meeting rooms heap

Applies to

Scheduling with availability constraints

1. Load tasks into a max-heap by demand.
2. Consume per time unit, deferring cooldown items.
3. Count units until the heap and cooldown queue are empty.

Build solutions incrementally, and undo the last choice when a branch fails.

a.k.a. dfs state, recursion, permutations

Applies to

Enumerate all configurations (combos, subsets, paths)

1. Decide the decision variables and the base case.
2. Make a choice, recurse, then undo the choice.
3. Prune branches early when a prefix is already invalid.

At each element decide include or skip; the recursion states enumerate all groups.

a.k.a. powerset, pick or skip

Applies to

Every subset or fixed-size group of a set

1. For subsets: two branches per element (take / skip).
2. For combinations: keep an index so you only move forward.
3. Snapshot the list when reaching a target length or the end.

Swap-in / used-flag recursion explores every ordering exactly once.

a.k.a. arrangements, all orderings

Applies to

Every ordering of a set (with or without duplicates)

1. Track used positions or swap to avoid repeats.
2. At full length, snapshot the permutation.
3. Sorting and skipping equal neighbours removes duplicate permutations.

Check every new placement against the constraints before recursing deeper.

a.k.a. n queens, candidate filtering

Applies to

Search spaces with hard row/column/diagonal rules

1. Keep sets for used rows, columns and diagonals.
2. Skip any placement that collides.
3. Recurse only into valid placements until the board fills.

Every state forks on include/exclude; memoise the state to stop re-exploring it.

a.k.a. choice tree, take or leave

Applies to

Optimum-search problems framed as choices

1. Define state = position + what changes (capacity, target).
2. Branch on take / skip and take the max or min.
3. Cache states so each is solved once.

Draw the recursion tree: branching factor and depth predict calls and stack usage.

a.k.a. recursion depth, stack trace

Applies to

Understanding and bounding recursive solutions

1. Count the branching factor and the depth of the tree.
2. Calls = branches^depth; stack use = depth, not calls.
3. Convert to iteration if depth risks stack overflow.

Explore as deep as possible along each branch before backtracking.

a.k.a. dfs, recursion tree

Applies to

Connected components, paths, tree traversals

1. Process the current node, then recurse into neighbours.
2. For graphs, mark visited to prevent revisits.
3. Pick pre-order or post-order work depending on what must happen first.

Process the frontier a layer at a time using a queue.

a.k.a. bfs, queue

Applies to

Shortest paths (unweighted), level-order, flood fill

1. Seed the queue with start nodes.
2. Drain one layer, enqueueing all neighbours.
3. The layer count measures distance, so first arrival is shortest.

Treat the grid as a graph; each cell is a node with up/down/left/right edges.

a.k.a. grid, islands

Applies to

2D grids and board problems

1. Check bounds before any neighbour visit.
2. Mark cells visited (often by mutation) to avoid revisits.
3. Flood-fill via BFS or DFS to explore one component.

Union-Find tracks connected components near-instant amortised time.

a.k.a. disjoint set, dsu, connectivity

Applies to

Connectivity, dynamic grouping, cycle checks

1. Each node starts in its own set.
2. Union merges two sets; Find returns the representative.
3. Two nodes in the same set ⇒ a cycle or shared component.

Visited + inStack marks expose back edges; union-find catches undirected cycles.

a.k.a. detect cycle, back edge

Applies to

Whether a directed/undirected graph has a cycle

1. DFS with a recursion stack: on return to a node still on it, cycle.
2. For undirected graphs, skip the edge back to the parent.
3. Union-find answers the same question incrementally during building.

Colour alternately during BFS/DFS; a same-colour edge disproves bipartiteness.

a.k.a. 2 colour, graph colouring

Applies to

Can vertices split into two sets with no intra-set edges

1. Colour start nodes red.
2. Neighbours always get the opposite colour.
3. A neighbour already same-coloured is an immediate contradiction.

Enqueue every source at distance 0 together; BFS then computes nearest-source distances.

a.k.a. 0-1 bfs, starting set

Applies to

Distance from the nearest of many sources

1. Seed the queue with all sources at distance 0.
2. Expand level by level, skipping visited cells.
3. Each cell inherits the distance of the layer that first reaches it.

Order nodes so every edge points forward; only acyclic graphs have an order.

a.k.a. topo, prereq, kahn

Applies to

Ordering tasks with dependencies

1. Count in-degrees. Enqueue all nodes with zero.
2. Process the queue, decrementing neighbours.
3. Fewer than N nodes processed ⇒ a cycle exists.

A priority queue always relaxes the currently-cheapest frontier node.

a.k.a. weighted shortest, priority bfs

Applies to

Shortest paths in graphs with non-negative weights

1. Distances start at infinity; start node is 0.
2. Pop the cheapest node and relax its edges.
3. Stop when the target is popped — no shorter route exists.

Kruskal: sort edges, union if they don't already connect. Prim: grow from a root via a heap.

a.k.a. kruskal, prim

Applies to

Cheapest connected subgraph spanning all nodes

1. Sort edges by weight (Kruskal) or seed a heap (Prim).
2. Add an edge only when it connects two different components.
3. Stop at V−1 edges: that is the spanning tree.

Sort intervals, then walk them greedily, merging or counting as required.

a.k.a. merge intervals, meeting rooms

Applies to

Scheduling and overlapping ranges

1. Sort by start time.
2. Keep a running current interval and extend when the next overlaps.
3. Emit or branch when the next interval begins after the current ends.

Pick the move that looks best now, then prove swapping any other in cannot improve.

a.k.a. locally optimal, exchange argument

Applies to

Optimisation where the best local move is globally optimal

1. State the greedy rule precisely.
2. Justify with an exchange argument that any optimal solution can adopt the greedy pick.
3. Implement the rule in one pass where possible.

Sort by end time and always take the interval that finishes first.

a.k.a. meeting rooms, max meetings

Applies to

Maximising the number of non-overlapping intervals

1. Sort by end time.
2. Take an interval if its start is after the last taken end.
3. Update the last end and count it.

Sort by start; extend the current range whenever the next start is inside it.

a.k.a. overlap merge, union ranges

Applies to

Collapsing ranges that touch or overlap

1. Sort intervals by start.
2. If the next start ≤ current end, extend current end.
3. Else emit current and start a new one.

Turn ranges into start/end events; sweep sorted events and track active count.

a.k.a. event sweep, skyline

Applies to

Counting active ranges across time

1. Flatten intervals into (position, ±1) events.
2. Sort and sweep, accumulating the running count.
3. Read the answer where activity peaks or boundaries break.

Process jobs by profit; slot each into the latest free time before its deadline.

a.k.a. job scheduling, early deadline

Applies to

Maximising profit under deadlines

1. Sort jobs by decreasing profit.
2. For each job, find the latest free slot at or before its deadline.
3. Fill that slot with the job.

Solve each state once, store the result, and build bigger answers from smaller ones.

a.k.a. dp, memoization, overlapping subproblems

Applies to

Optimal substructure over overlapping subproblems

1. Define state clearly: what changes as you recurse.
2. Write the recurrence between states.
3. Pick an iteration order or use memoised recursion.

The best subarray ending here is the current element or it plus the best ending before.

a.k.a. max subarray, running best

Applies to

Best contiguous sum ending at each position

1. Track bestEnding and bestGlobal.
2. bestEnding = max(x, bestEnding + x).
3. Answer is the max of bestEnding over all positions.

Ways to reach state i are the ways to reach its predecessor states summed.

a.k.a. staircase, climb stairs

Applies to

Linear recurrences over step-by-step paths

1. Identify a small, fixed recurrence between steps.
2. Solve bottom-up iterating over positions.
3. Keep only the last two or k values to save memory.

For each amount, best = 1 + best[amount − coin] over every coin.

a.k.a. coin change, unbounded dp

Applies to

Counting/optimising with reusable items

1. Start dp[0]=0, the rest at infinity.
2. For each amount, relax against every coin.
3. Constants like 2× amount loops are fine at these bounds.

At each item choose skip (keep previous best) or take (its value + best two before).

a.k.a. house robber, no two adjacent

Applies to

Selecting non-adjacent items for max value

1. dp[i] = max(dp[i−1], nums[i] + dp[i−2]).
2. Walk forward maintaining only the last two results.
3. Rotate conveniently if the input is a circle.

dp[i] says whether prefix i is segmentable; try each dictionary word after every true prefix.

a.k.a. sentence split, dictionary split

Applies to

Segmenting a string into dictionary words

1. dp[0]=true for the empty prefix.
2. For each true prefix, mark every prefix extended by a word.
3. Answer is dp[n] at the full length.

Ways to reach a cell are the sum of reaching it from above and the left.

a.k.a. unique paths, lattice paths

Applies to

Counting or weighting monotonic grid routes

1. Seed the top row and left column with base values.
2. Fill interior cells from their two incoming neighbours.
3. Read the target cell's final value.

For each item decide skip or take (value + best at remaining capacity).

a.k.a. bounded dp, capacity dp

Applies to

Choosing a subset under a capacity/weight budget

1. dp over (item index, capacity).
2. take = value[i] + dp[i−1][capacity − weight[i]] when it fits.
3. Keep whichever side is larger; roll to one row for space.

dp[i][j] = cost to convert a[..i] to b[..j], combining match, insert, delete, replace.

a.k.a. levenshtein, min edits

Applies to

Minimum insert/delete/replace between two strings

1. Initialise the empty-to-something rows.
2. Four-way transition per cell: match, insert, delete, replace.
3. dp[m][n] is the answer.

Equal chars extend the diagonal; otherwise the best of the two smaller prefixes wins.

a.k.a. lcs, common subsequence

Applies to

Shared ordered subsequences of two strings

1. dp[i][j] over the two string prefixes.
2. Match char → 1 + diagonal.
3. Mismatch → max of the two neighbours.

A substring is palindromic if its ends match and its interior is palindromic.

a.k.a. palindrome table, expand dp

Applies to

Counting/longest palindromic substrings

1. Length-1 and length-2 substrings are base cases.
2. For each length, verify ends match plus interior palindrome.
3. Expand outward or rely on the table for the answer.

Try every split point; the optimal is the best split's left + right cost.

a.k.a. mcm, split dp

Applies to

Costs that depend on where you split a range

1. dp over (start, end) ranges, shortest first.
2. For each split inside the range, combine subcosts with the split cost.
3. The full range's best is the answer.

A few primitives — XOR, masks, shifts — replace loops for parity and set membership.

a.k.a. bitwise, xor, masks

Applies to

XOR dancing, set/count bits, mask tricks

1. Know x ^ x = 0 and x ^ 0 = x.
2. Count set bits with x &= (x − 1) or a precomputed table.
3. Extract the last set bit with x & −x.

Compress keys via modular arithmetic and exploit divisibility symmetries.

a.k.a. mod, gdc, divisibility

Applies to

Arithmetic that folds into hashes or modular invariants

1. Reduce everything modulo a power or prime when overflow looms.
2. Detect pairs by residue: complements live in the same bucket.
3. Verify with small examples before scaling up.

Square-and-multiply halves the exponent each step: O(log n) multiplications.

a.k.a. modular exponentiation, fast pow

Applies to

Large powers, matrix exponents, modular inverses

1. While exponent > 0, square the base and halve the exponent.
2. When the bit is set, fold the base into the answer.
3. Keep everything modulo to stay in range.

Extract the last digit with %10, rebuild with ×10+digit.

a.k.a. reverse int, digit extract

Applies to

Reading and rebuilding number digits

1. Loop while n is nonzero: digit = n % 10.
2. Accumulate: result = result * 10 + digit.
3. Watch overflow by checking before multiplying.

Cross out every multiple of each prime — O(n log log n) to the limit.

a.k.a. sieve of eratosthenes, prime counting

Applies to

Counting or listing primes below a bound

1. Mark everything as prime.
2. For each unmarked value, cross out its multiples.
3. The unmarked survivors are the primes; count them.