Learn

A fixed-size block of contiguous memory holding elements of one type, addressable by index in O(1).

An array that grows automatically by doubling its capacity, giving amortized O(1) append with O(1) indexed access.

An immutable (in most languages) sequence of characters stored as an array, with its own family of matching and counting algorithms.

A rectangular grid of values indexed by (row, column), stored as an array of rows or one flattened row-major array.

A sequence of nodes where each node stores a value and a pointer to the next, giving O(1) insertion/deletion at a known position but O(n) access by index.

The simplest linked list: each node has a value and one `next` pointer, so traversal is forward-only and deletion needs the predecessor.

A linked list whose nodes carry both `prev` and `next` pointers, so any node can be removed in O(1) given just its reference and the list can be walked in both directions.

A linked list whose last node points back to the first, so traversal wraps around and a single tail pointer gives O(1) access to both ends.

A last-in, first-out collection where all insertions and removals happen at one end, the top.

A first-in, first-out collection: elements enter at the back and leave from the front.

A fixed-capacity queue over an array whose head and tail indices wrap around using modular arithmetic.

A queue that supports O(1) insertion and removal at both the front and the back.

A stack whose elements are kept in sorted order by popping everything that would violate the order before each push.

A deque kept in sorted order so the max (or min) of a sliding window is always at the front.

An abstract queue where the element with the highest (or lowest) priority is always removed first, typically backed by a binary heap.

An array of buckets indexed by a hash of the key, giving expected O(1) insert, lookup, and delete.

A key → value store backed by a hash table with expected O(1) get, put, and delete.

A collection of unique keys backed by a hash table, with expected O(1) add, contains, and remove.

Strategies for storing two keys whose hashes map to the same bucket without losing either.

Collision resolution where each bucket holds a linked list (or small array) of all entries that hash to it.

Collision resolution where every entry lives in the bucket array itself and collisions are resolved by probing other slots.

A hierarchical structure where every node has at most two children, the foundation of BSTs, heaps and expression trees.

A binary tree where every left descendant is smaller and every right descendant is larger, giving O(h) ordered search, insert and delete.

A self-balancing BST that keeps every node's subtree heights within 1 of each other using rotations, guaranteeing O(log n) operations.

A self-balancing BST that colors nodes red or black and enforces color rules so that no path is more than twice as long as any other.

A rooted tree in which each node can have any number of children, stored as a child list, and traversed with the same DFS/BFS ideas as binary trees.

A tree keyed by characters where each root-to-node path spells a prefix, giving O(L) insert, lookup and prefix search independent of how many words are stored.

A binary tree over array intervals that answers range queries (sum, min, max, gcd) and point or range updates in O(log n).

A compact array-based tree that supports prefix-sum queries and point updates in O(log n) using the binary representation of indices.

A balanced BST of intervals keyed by start, augmented with the maximum end in each subtree, to find all intervals overlapping a point or range in O(log n + k).

A balanced multiway search tree with wide nodes holding many keys, designed to minimize disk or cache-line reads for very large ordered data.

A B-tree variant that stores all records in linked leaf nodes and uses internal nodes only as a routing index, giving fast point lookups and sequential range scans.

A complete binary tree stored in an array where every parent is ≤ its children, so the minimum is always at the root.

A complete binary tree in array form where every parent is ≥ its children, so the maximum is always at the root.

The array-encoded complete binary tree behind min-heaps and max-heaps: parent/child indices are computed, not stored.

A collection of heap-ordered trees with lazy consolidation giving amortized O(1) insert, merge, and decrease-key, and O(log n) extract-min.

A set of vertices connected by one-way edges: an edge u→v does not imply v→u.

Vertices joined by two-way edges: {u, v} can be traversed in either direction.

A graph whose edges carry numeric weights (cost, distance, capacity), so path length is a sum of weights rather than a hop count.

A graph where every edge counts the same, so the shortest path is the one with the fewest edges and BFS finds it in O(V + E).

A directed graph with no cycles, guaranteeing a topological order in which every edge points forward.

A V×V grid where cell [u][v] stores whether (or how heavily) u connects to v, giving O(1) edge lookup at O(V²) space.

For each vertex, a list of its neighbors (and edge weights), giving O(V + E) space and O(deg) neighbor iteration — the default graph representation.

The graph as a flat list of (u, v[, w]) tuples — minimal, sortable, and exactly what Kruskal and Bellman-Ford need.

Tracks a partition of elements into disjoint sets with near-constant-time find and union, using path compression and union by rank.

A precomputed table of answers over power-of-two-length blocks that answers idempotent range queries (min, max, gcd) in O(1) after O(n log n) build, for static arrays.

A bit array plus k hash functions that answers "possibly in the set" or "definitely not" in O(k) with a tiny memory footprint and no false negatives.

A fixed-capacity key-value store that evicts the least recently used entry, with O(1) get and put via a hash map plus a doubly linked list.

A fixed-capacity cache that evicts the entry with the lowest access count (ties broken by least recent), in O(1) using a map of frequency buckets.

A sorted linked list with randomised express lanes stacked on top, giving expected O(log n) search, insert, and delete without any rebalancing.

Scan elements one by one until the target is found or the input is exhausted.

Find a target in a sorted array by repeatedly halving the search range.

Find the extremum of a unimodal function by discarding one third of the range per step.

Search a sorted array by jumping ahead in fixed blocks of size √n, then scanning linearly within the block.

Double an index until the target is bracketed, then binary search inside that bracket.

Find the k-th smallest element in expected O(n) by partitioning like quicksort but recursing into only one side.

Repeatedly swap adjacent out-of-order pairs so the largest remaining element bubbles to the end each pass.

Repeatedly select the minimum of the unsorted suffix and swap it into place; exactly n−1 swaps.

Build a sorted prefix by inserting each new element into its correct place among the ones before it.

Split the array in half, sort each half recursively, then merge the two sorted halves in linear time.

Pick a pivot, partition elements into smaller and larger sides, and recursively sort each side.

Build a max-heap in place, then repeatedly swap the root to the end and restore the heap.

Count occurrences of each key in a small integer range, then place elements by prefix sums — linear time, no comparisons.

Sort integers digit by digit from least significant to most, using a stable counting sort per digit.

Distribute elements into buckets by value range, sort each bucket, and concatenate — linear on uniform data.

Insertion sort over elements h apart with a shrinking gap sequence, finishing with a plain insertion sort.

Adaptive, stable hybrid of merge sort and insertion sort that exploits existing sorted runs; the default sort in Python and Java.

Walk one pointer in from each end of a sorted (or monotone-bounded) array, moving whichever side cannot improve the answer.

A read pointer scans every element while a write pointer marks the end of the finished prefix, compacting or filtering an array in place in one pass.

Advance one pointer twice as fast as another through a linked structure to find cycles, cycle starts, midpoints, and k-th-from-end nodes in O(1) space.

Rearrange an array in place so that elements less than, equal to, and greater than a pivot occupy contiguous regions, using pointers that mark region boundaries.

Maintain an aggregate over every length-k contiguous subarray by adding the entering element and removing the leaving one, turning O(n·k) into O(n).

Grow a window from the right while a condition holds and shrink it from the left when it breaks, finding the longest or shortest valid contiguous subarray in O(n).

Slide a window over a string while a hash map tracks character counts and a "formed" counter says how many required characters are satisfied — the engine behind anagram search and minimum window substring.

Precompute P[i] = a[0] + … + a[i-1] once so that any subarray sum a[l..r] is P[r+1] − P[l] in O(1).

Precompute S[i] = a[i] + … + a[n-1] by scanning right to left, so questions about "everything after index i" are answered in O(1) — usually paired with a prefix sum.

Apply many range increments in O(1) each by writing +v at l and −v at r+1, then recover the final array with a single prefix-sum pass.

Precompute X[i] = a[0] ^ … ^ a[i-1] so any range XOR a[l..r] is X[r+1] ^ X[l] — XOR is its own inverse, so no subtraction is needed.

Precompute P[i][j] = sum of the rectangle from (0,0) to (i-1,j-1) so any submatrix sum is four lookups via inclusion–exclusion.

Solve a problem by reducing it to smaller copies of itself; backtracking explores a tree of partial choices and undoes each one after exploring it.

Enumerate all 2^n subsets of a set by deciding, for each element in turn, whether to include it.

Enumerate all n! orderings of a sequence by choosing an unused element for each position in turn.

Enumerate all size-k subsets of n elements using the start-index template with a size-based base case and a "not enough elements left" prune.

Place n queens on an n×n board so none attack each other, by filling one row at a time and pruning columns and diagonals already under attack.

Fill empty cells one by one with digits that do not conflict in their row, column, or 3×3 box, backtracking on dead ends.

Find a path from start to exit in a grid by recursively stepping into open neighbors, marking cells on the current path and unmarking on retreat.

Check whether a word can be traced through adjacent grid cells without reuse, by DFS from every matching start cell with in-place visited marking.

Split a problem into independent subproblems of the same shape, solve them recursively, and combine the answers; the Master theorem tells you whether the split pays off.

Find the two closest points among n points in the plane in O(n log n) by splitting on x, recursing, and checking only a thin strip around the split line.

Pick the maximum number of mutually compatible activities by repeatedly taking the one that finishes earliest.

The family of interval problems: unweighted selection (greedy by finish), interval partitioning into minimum rooms (greedy by start with a min-heap), and weighted selection (DP with binary search).

Maximize value in a capacity-limited knapsack when items can be taken in fractions: take items in decreasing value-per-weight order.

Build an optimal prefix-free binary code by repeatedly merging the two least frequent symbols with a min-heap.

Schedule unit-length jobs with deadlines and profits to maximize total profit: take jobs in profit order and place each in the latest free slot before its deadline.

Find the unique start on a circular route from which a car can complete the loop, in one pass: whenever the running tank goes negative, restart from the next station.

Sort intervals by start and sweep once, extending the current interval while the next one overlaps and emitting it when a gap appears.

Build a solution by repeatedly taking the locally best choice — correct only when an exchange argument proves that choice never hurts.

Solve a problem by defining subproblems whose answers are reused, so exponential recursion collapses to polynomial time.

Write the natural recursion, then cache every result by its arguments so each distinct subproblem is computed once.

Fill a table of subproblem answers in an explicit order from base cases upward, with loops instead of recursion.

State is a single index into a sequence; dp[i] is the best answer for the prefix (or suffix) ending at i.

State is a pair of prefix lengths (i, j) over two sequences; dp[i][j] combines answers for shorter prefixes of each.

State is (position, small status flag); transitions are the edges of a tiny automaton evaluated once per input element.

State is a cell (r, c); the answer for a cell comes from its allowed predecessor cells (usually up and left).

State is (items considered, capacity used); choose items to maximize value or count/decide subsets hitting a target sum.

State is "best subsequence ending at index i"; transition scans all earlier j that can precede i.

State is a contiguous range [l, r]; the answer is built by choosing a split point or the last element removed inside the range.

State is a node (plus a small flag); each node combines the answers of its children in post-order.

State is a bitmask encoding which of n ≤ ~20 elements are used, plus optionally the last element; transitions add one bit.

Count numbers in [0, N] with a digit property by scanning N's digits with a "tight" flag and a small property state.

State is a vertex; process vertices in topological order so every predecessor is finalized before its successors.

Compute F(n) = F(n-1) + F(n-2) in linear time by reusing the two previous values instead of recomputing them.

Count the ways to reach step n taking 1 or 2 steps at a time — a Fibonacci recurrence in disguise.

Choose a subset of items, each used at most once, maximizing total value without exceeding a weight capacity.

Maximize value under a capacity when every item may be taken any number of times — the 0/1 loop run forward.

Find the fewest coins that sum to an amount (or count the ways) using unlimited coins of given denominations.

Find the length of the longest strictly increasing subsequence — O(n²) DP or O(n log n) with patience sorting.

Find the longest subsequence shared by two sequences using a 2D table over prefix pairs.

Minimum number of insertions, deletions, and substitutions to turn one string into another via a 2D prefix table.

Choose the parenthesization of a matrix product that minimizes scalar multiplications — the archetypal interval DP.

Find the maximum-sum contiguous subarray in one pass by tracking the best sum ending at each position.

Maximize the sum of chosen array elements with no two adjacent — a take-or-skip 1D DP with two rolling variables.

Explore a graph layer by layer from a source using a FIFO queue, visiting every node at distance d before any node at distance d + 1.

Explore a graph by following one path as deep as possible before backtracking, using recursion or an explicit stack.

Shortest path in an unweighted graph: BFS from the source, record parents, then walk parents back from the target to reconstruct the path.

Single-source shortest paths on graphs with non-negative edge weights, greedily settling the closest unsettled node using a min-priority queue.

Single-source shortest paths that tolerate negative edge weights: relax every edge V - 1 times, then one more pass to detect negative cycles.

All-pairs shortest paths by dynamic programming over the set of allowed intermediate nodes: three nested loops, O(V³), handles negative edges.

Shortest paths when every edge weighs 0 or 1: a deque replaces the heap — weight-0 edges push to the front, weight-1 edges to the back — giving O(V + E).

Point-to-point shortest path that steers Dijkstra toward the goal with a heuristic h(v): pop by f = g + h; optimal when h never overestimates.

Minimum spanning tree by growing one tree from a start node, always adding the cheapest edge that crosses from the tree to a new node.

Minimum spanning tree by sorting all edges and greedily adding each edge that joins two different components, tracked with union-find.

Partition an undirected graph into maximal groups of mutually reachable vertices with one traversal per group.

Maximal vertex sets of a directed graph in which every vertex can reach every other; computed in linear time by Tarjan or Kosaraju.

Find all strongly connected components in one DFS using discovery indices, low-link values and an explicit stack.

Find strongly connected components with two DFS passes: record finish order, then DFS the reversed graph in decreasing finish time.

Order the vertices of a directed acyclic graph so that every edge points forward; exists iff the graph has no cycle.

Topologically sort a DAG by repeatedly emitting vertices whose in-degree has dropped to zero; leftover vertices reveal a cycle.

Run DFS, record vertices as they finish, and reverse that list; a grey-to-grey edge during the search means a cycle.

Decide whether a graph has a cycle: three-colour DFS for directed graphs; DFS with parent tracking or union-find for undirected graphs.

Colour vertices with two colours so every edge joins different colours; succeeds iff the graph has no odd cycle.

Find every edge of an undirected graph whose removal disconnects it, using DFS discovery times and low-link values.

Find every vertex of an undirected graph whose removal disconnects it, via DFS low-link values with a special rule for the root.

A walk that uses every edge exactly once; exists under simple degree conditions and is built greedily by Hierholzer's algorithm in O(E).

A closed walk using every edge exactly once; exists iff the graph is connected on its edges and every vertex is balanced.

Try every alignment of the pattern against the text and compare character by character.

Linear-time pattern matching that never re-reads text characters, using a precomputed failure (LPS) table of the pattern.

Compare a rolling hash of each text window with the pattern hash and verify only on hash hits.

Compute for every position the length of the longest substring starting there that matches a prefix of the string, in linear time.

Compute the palindrome radius around every center in O(n) by reusing mirrored radii inside the rightmost known palindrome.

Precompute prefix hashes so the hash of any substring — and hence substring equality — can be evaluated in O(1).

Search a text for every word of a dictionary simultaneously by walking a trie augmented with KMP-style failure links.

Sort all suffixes of a string by index; with the LCP array it answers substring search, distinct-substring counts and longest-repeat queries.

A compressed trie of all suffixes of a string; answers substring search in O(m), longest repeat and distinct-substring counts directly from its structure.

The six primitive operations on the binary representation of integers: AND, OR, XOR, NOT, left shift and right shift.

Represent a set of up to 64 booleans as one integer so that set operations become single bitwise instructions.

The four single-bit primitives: set with OR, clear with AND-NOT, toggle with XOR, test with AND on a shifted 1.

Count the 1-bits of an integer with Kernighan's loop, a byte lookup table, a hardware popcount, or a DP over all numbers up to n.

Test for powers of two with n & (n-1), isolate the lowest set bit with n & -n, and round up to the next power of two with shift-or smearing.

Enumerate every subset of n items by counting masks from 0 to 2^n - 1, and every submask of a mask with s = (s - 1) & mask.

Exploit XOR's self-cancelling property to find unpaired elements, missing numbers, swap without a temporary, and answer range-XOR queries.

Compute the greatest common divisor by repeatedly replacing (a, b) with (b, a mod b); the extended form also finds x, y with ax + by = gcd.

Compute the least common multiple as a / gcd(a, b) * b, dividing before multiplying to avoid overflow.

Find every prime up to n by crossing out multiples of each prime starting from its square, in O(n log log n).

Decompose n into prime powers by trial division up to sqrt(n), or in O(log n) per query using a precomputed smallest-prime-factor table.

Compute x^n in O(log n) multiplications by squaring x and multiplying it in wherever the binary expansion of n has a 1 bit.

Do arithmetic on remainders: reduce after every add, subtract and multiply so results stay small, and use a prime modulus like 1e9+7 so division works.

Find a^-1 mod m — the number that multiplies a to 1 — via Fermat's little theorem when m is prime or the extended Euclidean algorithm for any coprime m.

Count arrangements and selections: nCr via factorial and inverse-factorial tables mod p, Pascal's triangle, stars and bars, and inclusion-exclusion.