# AlgoScope

> See algorithms. Build intuition.

## Data Structures

- [Adjacency List](https://algoscope.net/topics/adjacency-list): For each vertex, a list of its neighbours. Compact for sparse graphs.
- [Adjacency Matrix](https://algoscope.net/topics/adjacency-matrix): A V x V grid where cell (u, v) marks an edge from u to v.
- [Array](https://algoscope.net/topics/array): Numbered slots side by side, so reaching any one of them costs the same.
- [Binary Heap](https://algoscope.net/topics/binary-heap): A complete tree where every parent outranks its children, stored in a plain array.
- [Binary Search Tree](https://algoscope.net/topics/binary-search-tree): Smaller values sit left, larger sit right, so a search walks one path down.
- [Binary Tree](https://algoscope.net/topics/binary-tree): Each node has at most two children. Every tree lesson here builds on this shape.
- [Call Stack](https://algoscope.net/topics/call-stack): The runtime stack of function frames, pushed on every call and popped on every return. The reason recursion works and overflows.
- [Directed Graph](https://algoscope.net/topics/directed-graph): Edges have a direction. In-degree and out-degree differ.
- [Dynamic Array](https://algoscope.net/topics/dynamic-array): An array that doubles its capacity when full, so appends are amortized O(1).
- [Graph](https://algoscope.net/topics/graph): Vertices joined by edges. The model for networks, maps and dependencies.
- [Hash Map](https://algoscope.net/topics/hash-map): A hash table storing key-value pairs. The key picks the bucket and the value travels with it.
- [Hash Set](https://algoscope.net/topics/hash-set): A hash table holding keys only, to answer whether something is present.
- [Hash Table](https://algoscope.net/topics/hash-table): Turns a key into a slot number so lookup does not have to search.
- [Max Heap](https://algoscope.net/topics/max-heap): A binary heap whose root is the largest value.
- [Min Heap](https://algoscope.net/topics/min-heap): A binary heap whose root is the smallest value.
- [Priority Queue](https://algoscope.net/topics/priority-queue): Always hands back the highest-priority item, usually by keeping a binary heap underneath.
- [Queue](https://algoscope.net/topics/queue): You join at the back and leave from the front, like a queue at a counter.
- [Singly Linked List](https://algoscope.net/topics/singly-linked-list): Each node points at the next. To reach the tenth you walk the first nine.
- [Stack](https://algoscope.net/topics/stack): Only the top is reachable. The last thing down is the first thing up.
- [String](https://algoscope.net/topics/string): An array of characters, so most string algorithms are array algorithms with characters in the cells.
- [Weighted Graph](https://algoscope.net/topics/weighted-graph): Each edge carries a cost. The setting for shortest paths and spanning trees.
- [AVL Tree](https://algoscope.net/topics/avl-tree): A search tree that rotates itself back into balance whenever two sides differ in height by two.
- [Circular Queue](https://algoscope.net/topics/circular-queue): A fixed array where front and rear indices wrap around, so no space is wasted.
- [Deque](https://algoscope.net/topics/deque): Insert and remove at both ends in O(1).
- [Directed Acyclic Graph](https://algoscope.net/topics/directed-acyclic-graph): A directed graph with no cycles, which is exactly when a topological order exists.
- [Disjoint Set Union](https://algoscope.net/topics/disjoint-set-union): A parent array where following pointers leads to a root that names the set. Union links two roots.
- [Doubly Linked List](https://algoscope.net/topics/doubly-linked-list): Each node points to both neighbours, so a node can be unlinked in O(1) given only the node, as the LRU cache's moves rely on.
- [Edge List](https://algoscope.net/topics/edge-list): A flat list of (u, v, weight) triples, the natural input for Kruskal, which sorts it by weight.
- [Fenwick Tree](https://algoscope.net/topics/fenwick-tree): An array where cell i holds the sum of a range whose length is its lowest set bit.
- [Hash Function](https://algoscope.net/topics/hash-function): Turns a key into a slot number. Here it is key mod capacity, weak on purpose so collisions show.
- [LRU Cache](https://algoscope.net/topics/lru-cache): Evicts the least recently used entry. A hash map plus a recency list gives O(1) get and put.
- [Linear Probing](https://algoscope.net/topics/linear-probing): On a collision, walk forward one slot at a time until a free one turns up.
- [Matrix](https://algoscope.net/topics/matrix): Rows and columns of cells addressed by two indices. Row-major storage.
- [Monotonic Queue](https://algoscope.net/topics/monotonic-queue): A deque kept sorted so the window maximum is always at the front.
- [Monotonic Stack](https://algoscope.net/topics/monotonic-stack): A stack kept sorted by popping while the top violates the order. Answers next-greater queries in O(n).
- [Segment Tree](https://algoscope.net/topics/segment-tree): A binary tree whose leaves are the array and whose every parent summarises its two children.
- [Separate Chaining](https://algoscope.net/topics/separate-chaining): Each bucket holds a chain of colliding entries. A lookup hashes once and compares keys along that chain.
- [Trie](https://algoscope.net/topics/trie): A tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.
- [B-Tree](https://algoscope.net/topics/b-tree): A wide, shallow search tree tuned for block storage. Nodes hold many keys.
- [Bitset](https://algoscope.net/topics/bitset): An 8-bit word as an array of bits: get, set, clear and toggle are one mask operation each.
- [Circular Linked List](https://algoscope.net/topics/circular-linked-list): The last node links back to the first. Traversal wraps around.
- [Double Hashing](https://algoscope.net/topics/double-hashing): Each key probes with its own stride, 1 + key mod (size - 1), so keys with the same home follow different paths.
- [Quadratic Probing](https://algoscope.net/topics/quadratic-probing): Probe i jumps i^2 slots from the home slot, so a run of taken slots is left behind instead of growing.
- [Red-Black Tree](https://algoscope.net/topics/red-black-tree): A search tree kept within 2 log n height by one colour bit per node and a fixup after each insert.
- [Sparse Table](https://algoscope.net/topics/sparse-table): Row k holds the minimum of every window of length 2^k, each from two half windows above: O(n log n) once.
- [Suffix Array](https://algoscope.net/topics/suffix-array): The starting indices of all suffixes, sorted. Binary search finds substrings.
- [2-3 Tree](https://algoscope.net/topics/2-3-tree): A perfectly balanced search tree whose nodes hold one or two keys.
- [2-3-4 Tree](https://algoscope.net/topics/2-3-4-tree): Nodes hold one to three keys. Isomorphic to red-black trees.
- [B+ Tree](https://algoscope.net/topics/b-plus-tree): A B-tree where all values live in linked leaves, making range scans sequential.
- [Binomial Heap](https://algoscope.net/topics/binomial-heap): A forest of binomial trees supporting O(log n) merge.
- [Bloom Filter](https://algoscope.net/topics/bloom-filter): A probabilistic set: k hash functions set k bits. False positives possible, false negatives impossible.
- [Fibonacci Heap](https://algoscope.net/topics/fibonacci-heap): A lazy mergeable heap with O(1) amortized decrease-key, the theoretical best for Dijkstra.
- [Interval Tree](https://algoscope.net/topics/interval-tree): A BST of intervals augmented with subtree maximum endpoints for overlap queries.
- [KD-Tree](https://algoscope.net/topics/kd-tree): A space-partitioning BST alternating split axes. Nearest-neighbour and range search in k dimensions.
- [LFU Cache](https://algoscope.net/topics/lfu-cache): Evicts the least frequently used entry, breaking ties by recency.
- [Multigraph](https://algoscope.net/topics/multigraph): Allows parallel edges and self-loops.
- [Radix Tree](https://algoscope.net/topics/radix-tree): A trie where chains of single-child nodes are merged into one edge labelled with a string.
- [Range Tree](https://algoscope.net/topics/range-tree): A BST on one coordinate with a secondary structure per node for orthogonal range queries.
- [Skip List](https://algoscope.net/topics/skip-list): Layered linked lists where higher levels skip ahead, giving expected O(log n) search.
- [Splay Tree](https://algoscope.net/topics/splay-tree): A self-adjusting BST that moves each accessed node to the root.
- [Suffix Tree](https://algoscope.net/topics/suffix-tree): A compressed trie of all suffixes. Answers substring queries in O(m).
- [d-ary Heap](https://algoscope.net/topics/d-ary-heap): A heap where each node has d children. Shallower, cheaper decrease-key, costlier extract.

## Array Algorithms and Techniques

- [Array Delete](https://algoscope.net/topics/array-delete): Close the gap by shifting everything after the slot one place left.
- [Array Insert](https://algoscope.net/topics/array-insert): Make room by shifting everything after the slot one place right, then write.
- [Array Search](https://algoscope.net/topics/linear-search): Check each slot in turn until the value turns up or the array runs out.
- [Array Traversal](https://algoscope.net/topics/array-traversal): Visit every slot once, in order. Nothing is skipped and nothing is revisited.
- [Kadane's Algorithm](https://algoscope.net/topics/kadane-s-algorithm): Carry the best run ending here. A negative run only hurts, so drop it and start over.
- [Partition](https://algoscope.net/topics/partition): Push everything smaller than the pivot to its left, then drop the pivot between the groups.
- [Prefix Sum](https://algoscope.net/topics/prefix-sum): Store running totals once, and any range sum becomes two lookups and a subtraction.
- [Reverse Array](https://algoscope.net/topics/reverse-array): Swap the outermost pair and step both pointers inward until they meet.
- [Two Pointer Traversal](https://algoscope.net/topics/two-pointer-traversal): Two indices walk the array under a rule instead of a nested loop.
- [Difference Array](https://algoscope.net/topics/difference-array): Record range updates as two endpoint deltas. A final prefix sum applies them all.
- [Dutch National Flag](https://algoscope.net/topics/dutch-national-flag): Three pointers sort the array into less, equal and greater in one pass.
- [Maximum Subarray](https://algoscope.net/topics/maximum-subarray): The largest total of any run of neighbours. Kadane solves it in one pass.
- [Range Sum Query](https://algoscope.net/topics/range-sum-query): The sum of a range is the total up to its end minus the total before its start.
- [Rotate Array](https://algoscope.net/topics/rotate-array): Shift every value k places round. Reverse the whole thing, then each part, and it is done in place.
- [Subarray Sum Patterns](https://algoscope.net/topics/subarray-sum-patterns): Count subarrays with a given sum in one pass: each prefix looks up how often prefix - k occurred before.

## Searching

- [Binary Search](https://algoscope.net/topics/binary-search): Compare with the middle of a sorted array and half of it stops mattering.
- [Linear Search](https://algoscope.net/topics/linear-search): Check every slot in order. On average half the array, in the worst case all of it.
- [Exponential Search](https://algoscope.net/topics/exponential-search): Double the probe index until the value passes the target, then binary search the last doubling: O(log i).
- [Interpolation Search](https://algoscope.net/topics/interpolation-search): Probe where a straight line through the range ends would put the target. Log log n on even data.
- [Jump Search](https://algoscope.net/topics/jump-search): Jump sqrt(n) at a time while the block's last value is below the target, then scan one block.
- [Ternary Search](https://algoscope.net/topics/ternary-search): Split into thirds with two probes. Useful for unimodal functions, not faster than binary search on arrays.

## Sorting

- [Bubble Sort](https://algoscope.net/topics/bubble-sort): Swap neighbours that are out of order until each pass floats one value home.
- [Insertion Sort](https://algoscope.net/topics/insertion-sort): Take the next value and slide it left past larger values into the sorted prefix.
- [Merge Sort](https://algoscope.net/topics/merge-sort): Merge two sorted runs by always taking the smaller front value.
- [Quick Sort](https://algoscope.net/topics/quick-sort): Pick a pivot, push everything smaller left, and the pivot is home for good.
- [Selection Sort](https://algoscope.net/topics/selection-sort): Scan for the smallest value left, then swap it home. At most n-1 swaps.
- [Counting Sort](https://algoscope.net/topics/counting-sort): Count occurrences of each key, prefix-sum the counts, place each element at its final index.
- [Heap Sort](https://algoscope.net/topics/heap-sort): Build a max-heap in place, then repeatedly swap the root to the end of the shrinking heap and sift the new root down.
- [Quickselect](https://algoscope.net/topics/quickselect): Partition like quick sort, but only follow the side that holds the k-th value.
- [Radix Sort](https://algoscope.net/topics/radix-sort): Counting-sort by each digit from least significant to most. Stability makes it work.
- [3-Way Quick Sort](https://algoscope.net/topics/3-way-quick-sort): Partition into smaller, equal and larger zones. The equal zone is final, so duplicates cost O(n).
- [Bottom-Up Merge Sort](https://algoscope.net/topics/bottom-up-merge-sort): Merge sort with no recursion, doubling the run width on every pass.
- [Bucket Sort](https://algoscope.net/topics/bucket-sort): Scatter values into equal value ranges, sort each small bucket, gather in order: linear on even data.
- [Shell Sort](https://algoscope.net/topics/shell-sort): Insertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.
- [TimSort](https://algoscope.net/topics/timsort): Find natural ascending runs, extend short ones by insertion sort, then merge neighbouring runs.
- [IntroSort](https://algoscope.net/topics/introsort): Quick sort that switches to heap sort when recursion gets too deep and to insertion sort on small ranges.

## Linked List Algorithms

- [Delete Node](https://algoscope.net/topics/delete-node): Route the predecessor's pointer around the node, then drop it.
- [Detect Cycle](https://algoscope.net/topics/detect-cycle): If fast ever lands on slow, the list loops. On a straight list fast just runs out.
- [Find Middle](https://algoscope.net/topics/find-middle): Slow moves one, fast moves two. When fast runs out, slow is halfway.
- [Insert at Head](https://algoscope.net/topics/insert-at-head): Point the new node at the old head, then move head onto it. Nothing else shifts.
- [Insert at Position](https://algoscope.net/topics/insert-at-position): Walk to the node before the gap, then relink it and the new node in order.
- [Insert at Tail](https://algoscope.net/topics/insert-at-tail): Walk to the last node and attach the new node after it.
- [Merge Two Sorted Lists](https://algoscope.net/topics/merge-two-sorted-lists): Repeatedly take the smaller head and hang it on the merged tail. Relink instead of copying.
- [Reverse Linked List](https://algoscope.net/topics/reverse-linked-list): Walk the list with three pointers and flip each arrow to face the other way.
- [Traversal](https://algoscope.net/topics/traversal): Follow next pointers from head until null.
- [Find Cycle Entry](https://algoscope.net/topics/find-cycle-entry): After they meet, restart one at the head and walk both by one. They meet again at the entry.
- [Merge K Sorted Lists](https://algoscope.net/topics/merge-k-sorted-lists): Keep the current heads in a min-heap so the global smallest is always one pop away.
- [Remove Nth From End](https://algoscope.net/topics/remove-nth-from-end): Lead one pointer n ahead, then walk both until the leader runs out. Trail is just before the target.
- [Intersection of Two Lists](https://algoscope.net/topics/intersection-of-two-lists): Walk pa down A then B and pb down B then A. They meet at the shared node after the same distance, or at null together.
- [Palindrome Linked List](https://algoscope.net/topics/palindrome-linked-list): Middle by slow and fast, reverse the second half, compare front against back, reverse it back.
- [Remove Cycle](https://algoscope.net/topics/remove-cycle): After slow and fast meet, walk from the head and the meeting point to the entry, then once round the loop to cut the arrow before it.
- [Reorder List](https://algoscope.net/topics/reorder-list): Middle by slow and fast, reverse the second half, weave first and second alternately.
- [Reverse in Groups of k](https://algoscope.net/topics/reverse-in-groups-of-k): Count k ahead, reverse that run with prev and curr, hook the previous group's tail onto the new front.
- [Rotate List](https://algoscope.net/topics/rotate-list): Close the list into a ring through the tail, then cut it n - k mod n steps in.

## Stack and Queue Algorithms

- [Balanced Parentheses](https://algoscope.net/topics/balanced-parentheses): Push openers and pop on closers. Balanced when every closer matches the top and the stack ends empty.
- [Dequeue](https://algoscope.net/topics/dequeue): Remove the item at the front, which has waited longest.
- [Enqueue](https://algoscope.net/topics/enqueue): Add an item at the rear. It waits behind everything already there.
- [Peek](https://algoscope.net/topics/peek): Read the top item without removing it.
- [Pop](https://algoscope.net/topics/pop): Take the top item off. Only the top is ever touched.
- [Push](https://algoscope.net/topics/push): Place an item on top. Nothing else moves, so it is O(1).
- [Expression Evaluation](https://algoscope.net/topics/expression-evaluation): Two stacks, values and operators, evaluate infix in one pass. Brackets fence the operator stack.
- [Infix to Postfix](https://algoscope.net/topics/infix-to-postfix): Operands go straight to the output. Operators wait on a stack until a lower-precedence one arrives.
- [Next Greater Element](https://algoscope.net/topics/next-greater-element): Scan with a monotonic stack. Each pop resolves an element's answer.
- [Postfix Evaluation](https://algoscope.net/topics/postfix-evaluation): Push numbers. An operator pops two, applies itself, and pushes the result.
- [Sliding Window Maximum](https://algoscope.net/topics/sliding-window-maximum): A monotonic deque of indices keeps the window maximum at the front in amortized O(1).
- [Stack-based DFS](https://algoscope.net/topics/dfs-iterative): Iterative DFS: push the start, pop, visit, push unvisited neighbours.
- [Largest Rectangle in Histogram](https://algoscope.net/topics/largest-rectangle-in-histogram): Keep a stack of rising bars. Popping a bar bounds its rectangle by the nearest shorter bars on both sides.
- [Next Smaller Element](https://algoscope.net/topics/next-smaller-element): The nearest smaller value to the right.
- [Previous Greater Element](https://algoscope.net/topics/previous-greater-element): The nearest larger value to the left, via a monotonic stack.
- [Queue Using Two Stacks](https://algoscope.net/topics/queue-using-two-stacks): Enqueue onto an in stack. When the out stack is empty, pour everything across to reverse the order.
- [Stack Using Queues](https://algoscope.net/topics/stack-using-queues): Rotate the queue after each push so the newest item sits at the front.

## Hashing

- [Hash Table Insert](https://algoscope.net/topics/hash-table-insert): Hash the key to a slot, then walk forward past anything already there.
- [Hash Table Lookup](https://algoscope.net/topics/hash-table-lookup): Hash the key and walk the same path the insert would have walked.
- [Hash Table Delete](https://algoscope.net/topics/hash-table-delete): Mark the slot as used-and-emptied, because a real hole would cut the probe chain.
- [Load Factor](https://algoscope.net/topics/load-factor): Entries divided by buckets. Drives expected probe length and when to rehash.
- [Rehashing](https://algoscope.net/topics/rehashing): When the load factor exceeds a threshold, double the buckets and reinsert every key.

## Tree Algorithms

- [BST Delete](https://algoscope.net/topics/bst-delete): A leaf just goes, one child is spliced past, two children need a successor.
- [BST Insert](https://algoscope.net/topics/bst-insert): Search for the value and hang a new leaf wherever the search runs out of tree.
- [BST Search](https://algoscope.net/topics/bst-search): Compare with the node, go left if smaller, right if larger.
- [Find Minimum and Maximum](https://algoscope.net/topics/find-minimum-and-maximum): The minimum is all the way left and the maximum all the way right. One path each.
- [Inorder Traversal](https://algoscope.net/topics/inorder-traversal): Left subtree, then the node, then the right. On a search tree that comes out sorted.
- [Level Order Traversal](https://algoscope.net/topics/level-order-traversal): Walk depth by depth with a queue rather than the call stack.
- [Postorder Traversal](https://algoscope.net/topics/postorder-traversal): Finish both subtrees before writing the node down, so the root comes last.
- [Preorder Traversal](https://algoscope.net/topics/preorder-traversal): Write the node down first, then walk its left subtree and then its right.
- [AVL Insert with Rebalancing](https://algoscope.net/topics/avl-insert-with-rebalancing): Insert as a BST, walk back up updating heights, and rotate the first unbalanced node.
- [BST Range Search](https://algoscope.net/topics/bst-range-search): Report every value in a range, entering only the subtrees that could hold one.
- [BST from Sorted Array](https://algoscope.net/topics/bst-from-sorted-array): Take the middle as the root and recurse on both halves, for a tree of height log n.
- [Balance Factor](https://algoscope.net/topics/balance-factor): Left height minus right height. Every node must stay within -1, 0 or 1.
- [Left Rotation](https://algoscope.net/topics/left-rotation): The right child comes up and the old node drops to its left.
- [Left-Right and Right-Left Rotations](https://algoscope.net/topics/left-right-and-right-left-rotations): A zig-zag needs two rotations. Straighten the child first, then rotate the node.
- [Lowest Common Ancestor](https://algoscope.net/topics/lowest-common-ancestor): Walk down while both values are on the same side. Where they split is the answer.
- [Right Rotation](https://algoscope.net/topics/right-rotation): The left child comes up and the old node drops to its right.
- [Successor and Predecessor](https://algoscope.net/topics/successor-and-predecessor): The next value up is the last node you turned left at, or the minimum of the right subtree.
- [Validate BST](https://algoscope.net/topics/validate-bst): Every node must sit inside a window inherited from all its ancestors, not just its parent.
- [AVL Delete with Rebalancing](https://algoscope.net/topics/avl-delete-with-rebalancing): Delete like a BST, then rebalance every ancestor. Unlike insert, several rotations may be needed.
- [BST Reconstruction from Preorder](https://algoscope.net/topics/bst-reconstruction-from-preorder): Keep a stack of nodes with an open right side. A smaller value is the top's left child, a larger one the right child of the last node popped.
- [Red-Black Insert Fix-up](https://algoscope.net/topics/red-black-insert-fix-up): Red uncle: recolour and move up. Black uncle: one or two rotations plus a recolour, then stop.
- [Red-Black Rules](https://algoscope.net/topics/red-black-rules): Root black, no red under red, equal black count on every path. Checked bottom-up by black height.
- [Reverse Level Order](https://algoscope.net/topics/reverse-level-order): Level order pushed onto a stack, right child first, then popped: bottom level first, left to right.
- [Zigzag Level Order](https://algoscope.net/topics/zigzag-level-order): Level order with the reading direction flipped on every level.
- [Morris Traversal](https://algoscope.net/topics/morris-traversal): O(1)-space traversal by temporarily threading each node's inorder predecessor to it.
- [Red-Black Delete Fix-up](https://algoscope.net/topics/red-black-delete-fix-up): Removing a black node creates a "double black" that is pushed up or resolved by sibling cases.

## Heap Algorithms

- [Extract Min / Max](https://algoscope.net/topics/extract-min-max): Take the root, move the last leaf up into it, then let that value sink.
- [Heap Insert](https://algoscope.net/topics/heap-insert): Drop the value in the next free slot, then let it climb until its parent outranks it.
- [Heapify (Build Heap)](https://algoscope.net/topics/heapify-build-heap): Sift every parent down, last one first. The whole build costs O(n), not O(n log n).
- [Sift Down](https://algoscope.net/topics/sift-down): Swap with the better child while a child outranks the value. One path, O(log n).
- [Sift Up](https://algoscope.net/topics/sift-up): Compare with the parent and swap while the value outranks it. One path, O(log n).
- [K-th Largest / Smallest](https://algoscope.net/topics/k-th-largest-smallest): Keep a min heap of size k. The root is the k-th largest after scanning everything.
- [Binomial Heap Merge](https://algoscope.net/topics/binomial-heap-merge): Merge two heaps by linking trees of equal degree like binary addition.
- [Fibonacci Heap Decrease-Key](https://algoscope.net/topics/fibonacci-heap-decrease-key): Cut the node to the root list. Cascading cuts keep the potential bounded.

## Graph Traversal

- [Breadth-First Search](https://algoscope.net/topics/breadth-first-search): Explore layer by layer with a queue. Discovers shortest paths in unweighted graphs.
- [Connected Components](https://algoscope.net/topics/connected-components): Run BFS or DFS from every unvisited vertex. Each run colours one component.
- [DFS Recursive](https://algoscope.net/topics/dfs-recursive): The natural recursive form. Each call frame is one vertex, and the current path is the call stack.
- [Depth-First Search](https://algoscope.net/topics/depth-first-search): Go as deep as possible before backtracking. The recursion stack is the frontier.
- [Flood Fill](https://algoscope.net/topics/flood-fill): BFS or DFS on a grid, treating same-coloured neighbours as edges.
- [Bipartite Check](https://algoscope.net/topics/bipartite-check): Two-colour the graph with BFS. An edge between two vertices of the same colour means an odd cycle.
- [Cycle Detection](https://algoscope.net/topics/cycle-detection): Undirected: an edge to a seen vertex other than the parent. Directed: an edge to a vertex still on the DFS path.
- [DFS Iterative](https://algoscope.net/topics/dfs-iterative): Explicit stack of vertices. Avoids recursion depth limits.
- [Number of Islands](https://algoscope.net/topics/number-of-islands): Count connected components on a grid with flood fill from every unvisited land cell.

## Shortest Path

- [Dijkstra](https://algoscope.net/topics/dijkstra): Repeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.
- [A* Search](https://algoscope.net/topics/a-search): Best-first search ordered by g + h, distance so far plus an admissible estimate of what is left. Optimal and far more focused than BFS.
- [Bellman-Ford](https://algoscope.net/topics/bellman-ford): Relax every edge V-1 times. A further improvement means a negative cycle.
- [Floyd-Warshall](https://algoscope.net/topics/floyd-warshall): Admit one stopover vertex per round and relax every pair through it. The matrix converges in n rounds.
- [0-1 BFS](https://algoscope.net/topics/0-1-bfs): A deque replaces the heap when weights are 0 or 1: a 0 edge pushes to the front, a 1 edge to the back.
- [DAG Shortest Path](https://algoscope.net/topics/dag-shortest-path): Relax each vertex's edges once, in topological order: one pass, negative weights allowed.

## Minimum Spanning Tree

- [Kruskal](https://algoscope.net/topics/kruskal): Sort the edges by weight and take each one that joins two different components, which union-find answers.
- [Prim](https://algoscope.net/topics/prim): Grow one tree from a start vertex, always adding the cheapest edge that leaves it.
- [Boruvka](https://algoscope.net/topics/boruvka): Every component picks its cheapest outgoing edge simultaneously. Components halve each round.

## Connectivity and Topological Order

- [DFS Topological Sort](https://algoscope.net/topics/dfs-topological-sort): Reverse postorder of a DFS is a topological order, and a back edge means there is none.
- [Kahn's Algorithm](https://algoscope.net/topics/kahn-s-algorithm): Repeatedly place a vertex with in-degree zero and lower the counts of everything it points to.
- [Union-Find Operations](https://algoscope.net/topics/union-find-operations): find climbs to the root then flattens the path. Union hangs the smaller root under the larger.
- [Articulation Points](https://algoscope.net/topics/articulation-points): A vertex is an articulation point when some DFS child has low\[v\] >= disc\[u\], or it is the root with two subtrees.
- [Bridges](https://algoscope.net/topics/bridges): One DFS with discovery times and low-links. A tree edge u-v is a bridge when low\[v\] > disc\[u\].
- [Kosaraju](https://algoscope.net/topics/kosaraju): Finish order from one DFS, reverse every edge, then DFS from the latest finisher to paint each component.
- [Strongly Connected Components](https://algoscope.net/topics/strongly-connected-components): Maximal sets where every vertex reaches every other. The condensation is a DAG.
- [Tarjan SCC](https://algoscope.net/topics/tarjan-scc): Push on entry, lower low-links through open vertices, pop a whole component when low\[u\] == disc\[u\].

## Network Flow

- [Bipartite Matching](https://algoscope.net/topics/bipartite-matching): Unit-capacity network from a source through left and right to a sink. Each augmenting path is an alternating path.
- [Edmonds-Karp](https://algoscope.net/topics/edmonds-karp): Ford-Fulkerson with BFS, so each path is shortest. O(V E^2) regardless of capacities.
- [Ford-Fulkerson](https://algoscope.net/topics/ford-fulkerson): Any augmenting path will do. Push its bottleneck, and undoing flow along a backward residual edge is allowed.
- [Maximum Flow](https://algoscope.net/lesson/max-flow#maximum-flow): The most that can be sent from source to sink. Grows by augmenting paths in the residual graph until none is left.
- [Minimum Cut](https://algoscope.net/topics/minimum-cut): The vertices still reachable in the final residual graph are S. The saturated edges leaving S sum to the max flow.
- [Dinic](https://algoscope.net/topics/dinic): Build a level graph with BFS, then push blocking flows with DFS. O(V^2 E).

## String Algorithms

- [Naive Pattern Matching](https://algoscope.net/topics/naive-pattern-matching): Try every alignment and compare left to right, throwing away what was read at each mismatch.
- [Knuth-Morris-Pratt](https://algoscope.net/topics/knuth-morris-pratt): On a mismatch, drop j to pi\[j - 1\] so the pattern slides without re-reading any text character.
- [Prefix Function](https://algoscope.net/topics/prefix-function): For each prefix, the length of its longest proper prefix that is also a suffix, built by falling back through shorter borders.
- [Prefix Search and Autocomplete](https://algoscope.net/topics/prefix-search-and-autocomplete): Walk the prefix, then enumerate every terminal below it with a DFS.
- [Rabin-Karp](https://algoscope.net/topics/rabin-karp): Compare a rolling hash of each window with the pattern hash and read characters only on a hash hit.
- [Trie Insert](https://algoscope.net/topics/trie-insert): Walk existing character edges, create the missing ones, and mark the final node terminal.
- [Trie Search](https://algoscope.net/topics/trie-search): Walk the characters. The word exists if the walk succeeds and ends on a terminal node.
- [Boyer-Moore](https://algoscope.net/topics/boyer-moore): Compare from the right. On a mismatch slide so the pattern's last copy of the bad character lines up, or past it.
- [Suffix Array Construction](https://algoscope.net/topics/suffix-array-construction): Sort suffixes by doubling the compared prefix length each round.
- [Trie Delete](https://algoscope.net/topics/trie-delete): Unmark the terminal. Prune nodes upward while they have no children and are not terminal.
- [Z Algorithm](https://algoscope.net/topics/z-algorithm): z\[i\] is the longest prefix match starting at i. Inside the rightmost match box copy from the mirror, then extend.
- [Aho-Corasick](https://algoscope.net/topics/aho-corasick): A trie of all patterns plus failure links. Matches many patterns in one pass over the text.
- [Manacher](https://algoscope.net/topics/manacher): Longest palindromic substring in O(n) by reusing mirrored palindrome radii.

## Dynamic Programming

- [0/1 Knapsack](https://algoscope.net/topics/0-1-knapsack): dp\[i\]\[w\] = max(dp\[i-1\]\[w\], dp\[i-1\]\[w - wt\] + val). Each item is taken at most once.
- [Base Case](https://algoscope.net/topics/base-case): States whose values are known without recursion. They seed the table.
- [Climbing Stairs](https://algoscope.net/topics/climbing-stairs): Ways to reach step n = ways(n-1) + ways(n-2).
- [Coin Change](https://algoscope.net/topics/coin-change): Fewest coins for amount a = 1 + min over coins c of best(a - c). Ways variant counts combinations.
- [Edit Distance](https://algoscope.net/topics/edit-distance): min(insert, delete, replace) = 1 + min(left, up, diagonal). Match copies the diagonal.
- [Fibonacci](https://algoscope.net/topics/fibonacci): f(n) = f(n-1) + f(n-2). The smallest example of memoization versus tabulation.
- [Longest Common Subsequence](https://algoscope.net/topics/longest-common-subsequence): Match - diagonal + 1. Otherwise max of up and left. Trace back to recover the subsequence.
- [Memoization](https://algoscope.net/topics/memoization): Top-down recursion that caches each result. The recursion tree collapses to one expansion per state.
- [Optimal Substructure](https://algoscope.net/lesson/grid-dp#optimal-substructure): An optimal solution is built from optimal solutions of subproblems.
- [Overlapping Subproblems](https://algoscope.net/topics/overlapping-subproblems): The same subproblem recurs many times in the naive recursion. That repetition is what memoization removes.
- [Recurrence](https://algoscope.net/lesson/grid-dp#recurrence): Defining a value in terms of smaller instances of the same problem.
- [State](https://algoscope.net/lesson/grid-dp#state): The minimal parameters that identify a subproblem. They become the table's dimensions.
- [Tabulation](https://algoscope.net/topics/tabulation): Bottom-up filling of the table in an order where dependencies are already computed.
- [Transition](https://algoscope.net/lesson/grid-dp#transition): The rule that computes one state from earlier states.
- [Unique Grid Paths](https://algoscope.net/topics/unique-grid-paths): paths(r, c) = paths(r-1, c) + paths(r, c-1). Pascal's triangle on a grid.
- [House Robber](https://algoscope.net/topics/house-robber): best(i) = max(best(i-1), best(i-2) + value(i)). Take or skip.
- [Longest Common Substring](https://algoscope.net/topics/longest-common-substring): Like LCS but a mismatch resets the cell to 0. The answer is the largest cell.
- [Longest Increasing Subsequence](https://algoscope.net/topics/longest-increasing-subsequence): O(n^2) DP over predecessors, or O(n log n) with patience sorting and binary search.
- [Maximum Subarray (DP view)](https://algoscope.net/topics/maximum-subarray-dp-view): best-ending-here(i) = max(a\[i\], best-ending-here(i-1) + a\[i\]).
- [Minimum Path Sum](https://algoscope.net/topics/minimum-path-sum): cost(r, c) = grid(r, c) + min(cost(r-1, c), cost(r, c-1)).
- [Unbounded Knapsack](https://algoscope.net/topics/unbounded-knapsack): Items may repeat. The transition reads the same row instead of the previous one.
- [Bitmask DP](https://algoscope.net/topics/bitmask-dp): A bitmask encodes which elements are used. Classic for TSP on small n.
- [Decode Ways](https://algoscope.net/topics/decode-ways): ways\[i\] adds ways\[i-1\] when the digit is not 0 and ways\[i-2\] when the pair before it lies in 10..26.
- [Interval DP](https://algoscope.net/topics/interval-dp): Fill a triangular table by range length. Each range takes the cheapest split into two shorter ranges.
- [Matrix Chain Multiplication](https://algoscope.net/topics/matrix-chain-multiplication): dp\[i\]\[j\] is the cheapest way to multiply Mi..Mj, trying every position for the last multiplication.
- [Tree DP](https://algoscope.net/topics/tree-dp): Compute each node's value from its children's values in postorder.
- [Digit DP](https://algoscope.net/topics/digit-dp): Count numbers in a range with a digit property by processing digits with a "tight" flag.

## Greedy

- [Activity Selection](https://algoscope.net/topics/interval-scheduling): Sort by finish time. Always take the next activity that starts after the last chosen one ends.
- [Fractional Knapsack](https://algoscope.net/topics/fractional-knapsack): Sort by value per weight. Take whole items until one must be split to fill the remaining room exactly.
- [Huffman Coding](https://algoscope.net/topics/huffman-coding): Repeatedly merge the two least frequent symbols. The merge tree gives prefix-free codes.
- [Interval Scheduling](https://algoscope.net/topics/interval-scheduling): Maximum set of non-overlapping intervals. Earliest finish first is optimal by an exchange argument.
- [Meeting Rooms](https://algoscope.net/topics/meeting-rooms): Minimum rooms = maximum number of simultaneous meetings. Sweep sorted starts and ends.
- [Interval Partitioning](https://algoscope.net/topics/interval-partitioning): Sort by start. Assign each interval to the first room that is free, else open a new room.
- [Job Sequencing with Deadlines](https://algoscope.net/topics/job-sequencing-with-deadlines): Richest job first, placed in the latest free slot before its deadline. No free slot means it is dropped.
- [Minimum Platforms](https://algoscope.net/topics/minimum-platforms): Arrivals and departures sorted as one event list. The peak number open is the platforms needed.

## Divide and Conquer

- [Divide and Conquer](https://algoscope.net/topics/divide-and-conquer): Split the input, solve the parts recursively, combine the results.
- [Binary Search (recursive view)](https://algoscope.net/topics/binary-search-recursive-view): Each call probes the middle and recurses into the half that can still hold the target. Depth O(log n).
- [Closest Pair (divide and conquer)](https://algoscope.net/topics/closest-pair-of-points): Split points by x, recurse, then check a strip around the split line.
- [Karatsuba Multiplication](https://algoscope.net/topics/karatsuba-multiplication): Multiply n-digit numbers with three half-size products instead of four.
- [Strassen Matrix Multiplication](https://algoscope.net/topics/strassen-matrix-multiplication): Seven block products instead of eight.

## Backtracking

- [Backtracking](https://algoscope.net/topics/backtracking): Build a solution one choice at a time and undo the last choice when it cannot lead to a solution.
- [N-Queens](https://algoscope.net/topics/n-queens): Place one queen per row. A column or diagonal conflict forces backtracking.
- [Permutations](https://algoscope.net/topics/permutations): Swap each remaining element into the next position, recurse, and swap back. n! leaves.
- [Subsets](https://algoscope.net/topics/subsets): Include or exclude each element in turn. Every leaf of that binary tree is one subset, 2^n in all.
- [Combination Sum](https://algoscope.net/topics/combination-sum): Choose candidates with reuse, in non-decreasing order, until the sum hits the target. Prune the moment a pick would overshoot.
- [Combinations](https://algoscope.net/topics/combinations): Choose k of n in increasing index order so each combination appears once. Prune when too few remain.
- [Rat in a Maze](https://algoscope.net/topics/rat-in-a-maze): Move through open cells toward the exit. Retreat from dead ends.
- [Word Search](https://algoscope.net/topics/word-search): DFS from each cell holding the first letter, extending through neighbours that hold the next one. Cells on the path are used once.
- [Constraint Search and Pruning](https://algoscope.net/topics/constraint-search-and-pruning): Checking a constraint at each placement prunes whole subtrees before they are explored.
- [Sudoku Solver](https://algoscope.net/topics/sudoku-solver): Fill empty cells with a digit that satisfies row, column and box. Backtrack on dead ends.

## Recursion

- [Base Case and Recursive Case](https://algoscope.net/topics/base-case-and-recursive-case): The recursive case shrinks the problem and the base case stops it. Without a base case the stack overflows.
- [Recursion](https://algoscope.net/topics/recursion): A function that calls itself on a smaller input until a base case, each call parked as a frame until the one above it returns.
- [Recursion Tree](https://algoscope.net/lesson/recursion-tree#recursion-tree): Every call is a node, every recursive call a child. The size of the tree is the running time.
- [Memoized Recursion](https://algoscope.net/lesson/recursion-tree#memoized-recursion): Cache results by argument. A repeated call becomes a leaf that returns at once.
- [Recursion to Iteration](https://algoscope.net/topics/recursion-to-iteration): A tail call is a loop in disguise: replace the call with an update of the arguments and jump back.
- [Tail Recursion](https://algoscope.net/lesson/call-stack#tail-recursion): The recursive call is the last action, so the frame can be reused and the stack never grows.
- [Tree Recursion](https://algoscope.net/lesson/recursion-tree#tree-recursion): A function that makes more than one recursive call, so its calls form a tree that doubles with n.

## Sliding Window

- [Fixed-Size Window](https://algoscope.net/topics/fixed-size-window): A window of size k. Add what enters, subtract what leaves, never re-add the middle.
- [Maximum Sum Subarray of Size k](https://algoscope.net/topics/maximum-sum-subarray-of-size-k): Slide a fixed window across the array and keep the best sum it ever held.
- [Sliding Window](https://algoscope.net/topics/sliding-window): Keep a contiguous range and update its summary as it moves, instead of rescanning it.
- [Variable-Size Window](https://algoscope.net/topics/variable-size-window): Grow the right end until a condition holds, then shrink the left end while it still does.
- [Frequency Map + Window](https://algoscope.net/topics/frequency-map-plus-window): Track counts of what is inside the window to answer "at most k distinct" style questions.
- [Longest Substring Without Repeating Characters](https://algoscope.net/topics/longest-substring-without-repeating-characters): Variable window plus the last index of each character. A repeat inside jumps the left edge past its earlier copy.
- [Minimum Window Substring](https://algoscope.net/topics/minimum-window-substring): Expand until the window covers all required characters, then shrink while it still does.

## Two Pointers

- [Fast and Slow Pointers](https://algoscope.net/topics/fast-and-slow-pointers): One pointer moves twice as fast as the other. Finds middles and cycles in one pass.
- [Opposite Direction Pointers](https://algoscope.net/topics/opposite-direction-pointers): Start at both ends and move inward. The comparison decides which one moves.
- [Remove Duplicates from Sorted Array](https://algoscope.net/topics/remove-duplicates-from-sorted-array): The writer only copies a value that differs from the last one it kept.
- [Same Direction Pointers](https://algoscope.net/topics/same-direction-pointers): A reader scans ahead while a writer lags, compacting the array in place.
- [Two Pointers](https://algoscope.net/topics/two-pointers): Two indices moving under a rule do in one pass what a nested loop needs n squared for.
- [Two Sum (sorted)](https://algoscope.net/topics/two-sum-sorted): Too small, move left up. Too big, move right down. The sorted order makes that safe.
- [Container With Most Water](https://algoscope.net/topics/container-with-most-water): Move the pointer at the shorter line inward. The taller one can never improve the area alone.
- [Three Sum](https://algoscope.net/topics/three-sum): Fix one element, run two-sum on the rest. Skip duplicates.

## Range Queries

- [2D Prefix Sum](https://algoscope.net/topics/2d-prefix-sum): P\[i\]\[j\] = a + P\[i-1\]\[j\] + P\[i\]\[j-1\] - P\[i-1\]\[j-1\]. Any rectangle sum in O(1).
- [Fenwick Update and Query](https://algoscope.net/topics/fenwick-update-and-query): Query walks i to i minus lowbit(i). Update walks i to i plus lowbit(i).
- [Range Minimum Query](https://algoscope.net/topics/range-minimum-query): The minimum of a range, answered from O(log n) nodes of a min tree.
- [Segment Tree Query and Update](https://algoscope.net/topics/segment-tree-query-and-update): A query takes whole nodes inside the range and splits only the ones on its edge.
- [Difference Matrix](https://algoscope.net/topics/difference-matrix): Four corner writes per rectangle, then a prefix pass along rows and down columns.
- [Lazy Propagation](https://algoscope.net/topics/lazy-propagation): Range updates are stored on nodes and pushed to children only when needed.
- [Sparse Table Build and Query](https://algoscope.net/topics/sparse-table-build-and-query): k = floor(log2(len)). The answer is min of the windows starting at l and ending at r, overlap harmless.

## Bit Manipulation

- [Clear Bit](https://algoscope.net/topics/clear-bit): AND with the inverse of that mask, so only bit i is forced to 0.
- [Count Set Bits](https://algoscope.net/topics/count-set-bits): Clear the lowest 1 with n and (n - 1) until nothing is left, counting rounds.
- [Get Bit](https://algoscope.net/topics/get-bit): Shift right by i and keep the last bit.
- [Set Bit](https://algoscope.net/topics/set-bit): OR with a mask that has a single 1 at bit i.
- [Toggle Bit](https://algoscope.net/topics/toggle-bit): XOR with the mask flips bit i and nothing else.
- [Bitmask](https://algoscope.net/topics/bitmask): Use the bits of an integer as a set of booleans.
- [Brian Kernighan's Algorithm](https://algoscope.net/topics/brian-kernighan-s-algorithm): n and (n - 1) wipes the lowest set bit, so the loop runs once per 1 bit.
- [Lowest Set Bit](https://algoscope.net/topics/lowest-set-bit): n and -n keeps only the lowest 1. It is the step a Fenwick tree takes.
- [Power of Two Check](https://algoscope.net/topics/power-of-two-check): Exactly one 1 bit, so clearing the lowest one leaves zero.
- [Subset Enumeration](https://algoscope.net/topics/subset-enumeration): Counting from 0 to 2^n - 1 enumerates every subset. sub = (sub - 1) & mask enumerates submasks.
- [XOR Pairing (Single Number)](https://algoscope.net/topics/xor-pairing-single-number): XOR everything. Duplicates cancel and the unpaired value remains.
- [XOR Properties](https://algoscope.net/topics/xor-properties): a ^ a = 0, a ^ 0 = a, commutative and associative. Pairs cancel.
- [Gray Code](https://algoscope.net/topics/gray-code): g = n xor (n shr 1). Each row of codes flips exactly one bit of the row above.

## Mathematics

- [Euclidean Algorithm](https://algoscope.net/topics/euclidean-algorithm): Replace (a, b) with (b, a mod b) until b is 0. The last non-zero value is the gcd.
- [Fast Exponentiation](https://algoscope.net/topics/fast-exponentiation): Square the base once per bit of the exponent, and multiply in on every 1 bit.
- [Greatest Common Divisor](https://algoscope.net/topics/greatest-common-divisor): The largest number that divides both. Euclid finds it in O(log n) steps.
- [Modular Arithmetic](https://algoscope.net/topics/modular-arithmetic): Arithmetic on a clock with m positions. Reduce at every step and nothing ever grows past m.
- [Primality Test](https://algoscope.net/topics/primality-test): Try each divisor up to the square root. No hit means prime.
- [Sieve of Eratosthenes](https://algoscope.net/topics/sieve-of-eratosthenes): Mark multiples of each prime. What survives is prime.
- [Combinations](https://algoscope.net/topics/combinations): C(n, k) = n! / (k! (n-k)!). Computed safely via Pascal's rule or multiplicative formula.
- [Extended Euclidean Algorithm](https://algoscope.net/topics/extended-euclidean-algorithm): Also finds x, y with ax + by = gcd(a, b) by carrying coefficients back up the division table. The route to modular inverses.
- [Fermat's Little Theorem](https://algoscope.net/topics/fermat-s-little-theorem): For prime p and a not divisible by p, a^(p-1) = 1 mod p.
- [Least Common Multiple](https://algoscope.net/topics/least-common-multiple): lcm(a, b) = a * b / gcd(a, b).
- [Modular Inverse](https://algoscope.net/topics/modular-inverse): x with ax = 1 mod m. Via extended Euclid, or a^(m-2) when m is prime.
- [Pascal's Triangle](https://algoscope.net/topics/pascal-s-triangle): Each entry is the sum of the two above it. Row n holds C(n, k).
- [Prime Factorization](https://algoscope.net/topics/prime-factorization): Divide out each candidate while it divides. Whatever is left above 1 is prime.
- [Modular Multiplication](https://algoscope.net/topics/modular-multiplication): Double and add along the bits of b, reducing every partial result, so nothing exceeds 2m.
- [Segmented Sieve](https://algoscope.net/topics/segmented-sieve): Sieve a large range in cache-sized blocks using primes up to sqrt(high).

## Computational Geometry

- [Convex Hull](https://algoscope.net/topics/convex-hull): The smallest convex polygon containing all points, built by monotone chain from sorted points.
- [Cross Product](https://algoscope.net/topics/cross-product): The 2D cross product is twice the signed area of the triangle. Its sign is the turn direction.
- [Distance](https://algoscope.net/topics/distance): Euclidean distance sqrt(dx^2 + dy^2). Compare squared distances to avoid the root.
- [Dot Product](https://algoscope.net/topics/dot-product): a . b = |a||b| cos theta. The sign tells whether vectors point the same way.
- [Orientation](https://algoscope.net/topics/orientation): Clockwise, counter-clockwise or collinear from the sign of the cross product of (b - a) and (c - a).
- [Points and Vectors](https://algoscope.net/topics/points-and-vectors): A point is a position. A vector is a displacement between points, drawn as an arrow.
- [Polygon Area](https://algoscope.net/topics/polygon-area): Half the absolute sum of cross products of consecutive vertices, the shoelace formula.
- [Segment Intersection](https://algoscope.net/topics/segment-intersection): Two segments cross when each straddles the other's line, decided by four orientation tests.
- [Closest Pair of Points](https://algoscope.net/topics/closest-pair-of-points): Divide by x, recurse, then check the strip around the divider. O(n log n).
- [Graham Scan](https://algoscope.net/topics/graham-scan): Sort points by angle around the lowest point. Keep a stack, popping on right turns.
- [Line Intersection](https://algoscope.net/topics/line-intersection): Where two segments meet is decided by orientations, then the point by cross-product ratios.
- [Monotone Chain](https://algoscope.net/topics/monotone-chain): Sort by x, then build the lower and upper chains, popping while the turn is not a left turn.
- [Sweep Line](https://algoscope.net/topics/sweep-line): Move a line across the plane, processing events in order and maintaining an active set.

## Complexity Analysis

- [Best, Average and Worst Case](https://algoscope.net/topics/best-average-and-worst-case): The same algorithm costs differently on different inputs. Each case is a separate statement.
- [Big O](https://algoscope.net/topics/big-o): An upper bound on growth. O(n^2) means at most proportional to n^2 for large n, read off as what happens when n doubles.
- [Space Complexity](https://algoscope.net/topics/space-complexity): Memory used as a function of input size, counting temporary arrays and the call stack.
- [Time Complexity](https://algoscope.net/lesson/complexity#time-complexity): Operation count as a function of input size. The classes separate within a few doublings of n.
- [Amortized Analysis](https://algoscope.net/topics/amortized-analysis): Average cost per operation over a sequence, even when a few operations are expensive.
- [Auxiliary Space](https://algoscope.net/lesson/complexity#auxiliary-space): Extra memory beyond the input itself, such as merge sort's buffer or a recursion's frames.
- [Big Omega](https://algoscope.net/topics/big-omega): A lower bound. The cost is at least a constant times the reference for large n.
- [Big Theta](https://algoscope.net/lesson/complexity#big-theta): A tight bound. The function stays between two scaled copies of the reference from some n0 on.
- [In-place](https://algoscope.net/lesson/complexity#in-place): O(1) auxiliary space. The input is rearranged within itself.
- [Master Theorem](https://algoscope.net/topics/master-theorem): Compare f(n) with n^(log_b a), the leaf count of the recursion tree, to read off T(n) in three cases.
- [Recurrence Relations](https://algoscope.net/lesson/recursion-tree#recurrence-relations): T(n) = a T(n / b) + f(n), the cost equation of a recursive algorithm, read off its recursion tree.
- [Stable Sorting](https://algoscope.net/topics/stable-sorting): Equal keys keep their original relative order.
- [Accounting Method](https://algoscope.net/lesson/complexity#accounting-method): Each cheap append deposits credit that a later resize spends, so the average stays O(1).
- [Adaptive Algorithms](https://algoscope.net/topics/adaptive-algorithms): Timsort on already sorted input finds a single run and finishes in one pass.
- [Aggregate Method](https://algoscope.net/lesson/complexity#aggregate-method): Total cost of n operations divided by n.
- [Expected Time](https://algoscope.net/topics/expected-time): Average over the algorithm's own random choices, for any input.
- [Potential Method](https://algoscope.net/topics/potential-method): A potential function on the data structure state pays for expensive operations.

## Algorithmic Paradigms

- [Backtracking](https://algoscope.net/topics/backtracking): Depth-first search over partial solutions, undoing choices that cannot work.
- [Brute Force](https://algoscope.net/topics/brute-force): Try every candidate. Correct by construction, the baseline to beat.
- [Divide and Conquer](https://algoscope.net/topics/divide-and-conquer): Split, solve recursively, combine, as a balanced tree of ranges.
- [Dynamic Programming](https://algoscope.net/topics/dynamic-programming): Solve each overlapping subproblem once and reuse the answer.
- [Greedy](https://algoscope.net/topics/greedy): Take the locally best choice and never look back. Correct only when an exchange argument holds.
- [Branch and Bound](https://algoscope.net/topics/branch-and-bound): Backtracking with a bound. Prune any branch whose best possible outcome cannot beat the current best.
- [Incremental Algorithms](https://algoscope.net/topics/incremental-algorithms): Grow the sorted prefix by one element at a time, repairing the order as each arrives.
- [Randomized Algorithms](https://algoscope.net/topics/randomized-algorithms): Use random choices so no single input is always bad (Las Vegas) or accept a small error chance (Monte Carlo).

## Problem-Solving Patterns

- [Backtracking](https://algoscope.net/topics/backtracking): Recognize it for "all solutions" and constraint-satisfaction questions.
- [Divide and Conquer](https://algoscope.net/topics/divide-and-conquer): Recognize it when the problem splits into independent halves with a cheap combine.
- [Fast and Slow Pointers](https://algoscope.net/topics/fast-and-slow-pointers): Reach for it on linked lists for cycles, middles and the nth from the end.
- [Frequency Map / Hashing](https://algoscope.net/topics/frequency-map-hashing): Recognize it for counting, grouping, anagram and "seen before" questions.
- [Greedy](https://algoscope.net/topics/greedy): Recognize it when a local choice can be proven safe by an exchange argument.
- [Memoization](https://algoscope.net/topics/memoization): Recognize it when a recursive solution repeats subproblems.
- [Prefix Sum](https://algoscope.net/topics/prefix-sum): Reach for it when many range sums are asked about an array that does not change.
- [Sliding Window](https://algoscope.net/topics/sliding-window): Reach for it when the question is about contiguous subarrays or substrings.
- [Tabulation](https://algoscope.net/topics/tabulation): Recognize it when the dependency order of states is clear and iteration avoids recursion depth.
- [Two Pointers](https://algoscope.net/topics/two-pointers): Reach for it when two indices moving under a rule can replace a nested loop.
- [Binary Search on Answer](https://algoscope.net/topics/binary-search-on-answer): Recognize it when 'is x feasible?' is monotonic in x. Binary search the answer space with one feasibility check per probe.
- [Bitmasking](https://algoscope.net/topics/bitmask): Recognize it when subsets of at most about 20 items must be tracked. Every mask from 0 to 2^n - 1 is one subset.
- [Difference Array](https://algoscope.net/topics/difference-array): Recognize it when many range updates precede a single read.
- [Monotonic Queue](https://algoscope.net/topics/monotonic-queue): Recognize it for sliding-window extrema.
- [Monotonic Stack](https://algoscope.net/topics/monotonic-stack): Recognize it for "next greater or smaller" and span questions.
- [Topological Sort](https://algoscope.net/topics/kahn-s-algorithm): Recognize it for dependency ordering and "can all tasks finish" questions.
- [Union-Find](https://algoscope.net/topics/union-find-operations): Recognize it for dynamic connectivity and grouping questions.
- [Coordinate Compression](https://algoscope.net/topics/coordinate-compression): Sort the distinct values and replace each value by its rank. Order survives, the range shrinks.
- [Meet in the Middle](https://algoscope.net/topics/meet-in-the-middle): Split the input in two, enumerate each half, combine with sorting or hashing. 2^(n/2) instead of 2^n.
- [Sweep Line](https://algoscope.net/topics/sweep-line): Sort the endpoints as events and sweep once, tracking how many intervals are open.