Appendix

A contiguous, index-addressed sequence: O(1) access by position, O(n) to insert or delete in the middle.

Search from the start and the goal at once and stop where the frontiers meet, about 2·b^(d/2) states instead of b^d.

Precompute every node's 2^k-th ancestor so any k-th ancestor, and so the LCA, takes O(log n) jumps.

A rooted tree in which every node has at most two children, left and right.

Treat integers as bit vectors: masks, shifts, and XOR in place of arithmetic or extra memory.

Strings of opening and closing brackets; balanced means the running depth never dips below zero and ends at zero.

Scatter values into buckets by range or frequency, then read the buckets in order: linear when the key range is bounded.

Count arrangements and selections (permutations, combinations, Catalan numbers), usually modulo a prime.

Knapsack in which every item may be taken any number of times, so the DP walks capacity upward and reuses the row.

Tally occurrences in a hash map or fixed array, then answer from the counts instead of the raw input.

Implement a class to an API spec, choosing the internals so every operation meets its time bound.

A directed graph with no cycles, which is exactly what lets its nodes be put in a topological order.

Split the input into independent parts, solve each recursively, and combine their answers.

A linked list whose nodes point to both neighbours, so a node you already hold is unlinked in O(1).

A slow and a fast pointer meet inside any cycle; restarting one from the head finds the cycle's entry, in O(1) space.

Points, lines, and areas on a plane or grid: distances, slopes, overlaps, and orientation by cross product.

Nodes joined by edges, directed or not, weighted or not, stored as an adjacency list or matrix.

A binary tree that splits k-dimensional points on alternating axes, for nearest-neighbour and range queries.

Pick items with weights and values to maximise value under a capacity; the 0/1 version is an O(n·W) DP.

The longest sequence that appears in order, not necessarily contiguously, in two strings: the classic O(n·m) 2-D DP.

The deepest node of a rooted tree that is an ancestor of both given nodes.

An arithmetic or number-theory insight (modular arithmetic, GCD, digit manipulation, a closed form) in place of brute force.

Cache a pure function's result per argument so every subproblem is solved once: top-down dynamic programming.

Sort each half recursively, then merge the two sorted halves: O(n log n), stable, O(n) extra space.

First in, first out: push at the back, pop from the front, both O(1).

Partition around a pivot and recurse into one side only, finding the k-th smallest element in O(n) on average.

Partition around a pivot, then sort each side in place: O(n log n) on average, O(n²) at worst.

Solve a problem by calling the same function on smaller inputs until a base case answers directly.

Carry out the process the statement describes, step by step; the work is modelling the state faithfully.

Order the input first so a later step, such as two pointers, a greedy choice, or binary search, becomes possible.

A sequence of characters; solutions lean on its small alphabet, its substrings, and its immutability.

A winner tree of pairwise comparisons: the root is the extreme element, and replaying one path yields the next in O(log n).

A connected acyclic graph, usually rooted, in which every node but the root has exactly one parent.