Algorithms & Data Structures

Repeatedly compares adjacent pairs and swaps them if out of order. After each full pass the largest remaining element 'bubbles' to the end.

Grow a sorted prefix one element at a time: take the next value and slide it left past everything larger. Quadratic in general, but linear on nearly-sorted data — which is why real sorts fall back to it on small runs.

Repeatedly scan the unsorted region for its smallest value and swap it into place. Always makes the same number of comparisons whatever the input — but never more than n swaps, which matters when writing is expensive.

Divide-and-conquer sort: recursively split the array in half, sort each half, then merge the two sorted halves back together in linear time.

Pick a pivot, partition elements into 'less than' and 'greater than' groups, then recursively sort each partition. Uses Lomuto partitioning here.

Rearrange the array into a max-heap, then repeatedly swap the root to the end and sift down. O(n log n) in the worst case like merge sort, but in O(1) space — the heap lives inside the array itself.

Check each element in turn until the target is found. Slower than binary search, but it makes no demands on the data: the array does not have to be sorted, which is the one thing binary search cannot do without.

Search a sorted array in O(log n) by repeatedly halving the search range — compare the target with the middle element and discard the half it can't be in.

Explore a graph layer by layer using a queue. Guarantees shortest path in an unweighted graph because nodes are visited in order of their distance from the source.

Explore as far along one branch as possible before backtracking, using a stack. Visits the same nodes as BFS but in a completely different order.

Greedy single-source shortest path on non-negative weighted graphs. Always expands the unvisited node with the smallest tentative distance, relaxing edges to its neighbours.

Order the nodes of a directed graph so every edge points forwards — build order, course prerequisites, task scheduling. Repeatedly take a node nothing depends on, and remove it. If anything is left over, the graph had a cycle.

Connect every node as cheaply as possible: sort the edges by weight and take each one unless it would close a cycle. Union-find answers 'would this close a cycle?' in near-constant time.

BFS on a 2D grid — the shortest-path workhorse behind maze solving and flood fill. Each walkable cell is a node; edges connect 4-neighbours. Shortest path by cell count is guaranteed.

DFS on a 2D grid — explores as far as possible along one direction before backtracking. Great for maze generation, connected-component labelling, and 'can I reach X?' checks.

Dijkstra on a grid where each cell has its own entry cost (digit 1–9). Finds the lowest-total-cost path from S to E. '.' cells cost 1, walls '#' are blocked.

Insert values into a Binary Search Tree one at a time. At each node, go left if the new value is smaller, right if larger — place it in the first empty slot.

Depth-first traversals of a binary search tree. In-order yields sorted values; pre-order is useful for copying; post-order for tree deletion and expression evaluation.

Store words by their shared prefixes so lookup costs the length of the word, not the size of the dictionary. This is what sits behind autocomplete and spell-checking.

Append, prepend, delete, and reverse operations on a singly linked list. Reversal flips every next-pointer with three moving references (prev / curr / next).

The same operations applied to both containers at once. A stack removes the most recently added item, a queue removes the oldest. That single difference is what separates DFS from BFS, undo from a print spooler.

Compute the nth Fibonacci number by filling a table from the bottom up. Each entry depends only on its two predecessors — the textbook introduction to dynamic programming.

Choose items to maximise value without exceeding a weight limit. Each item is taken whole or not at all — which is what makes the greedy 'best value per kilo' rule wrong and dynamic programming necessary.

Find the longest run of values that increases left to right, not necessarily adjacent. The O(n²) table is shown here because it is the version you can actually see working.

Make a target amount with as few coins as possible, given unlimited coins of each denomination. Greedy 'always take the biggest coin' works for real currencies and fails for others — so the table is built instead.

Find a pattern in a text without ever re-reading a character of the text. A precomputed failure table says how far the pattern can jump forward after a mismatch, using the fact that part of it has already matched.