Lucent Owl logo Lucent Owl

Data Structures and Algorithms Diagrams

Last updated:

14 related guides
diagrams complexity-analysis growth-rates

How Common Growth Rates Compare

Chart

Operations performed as input size grows, for six growth rates.

Growth of six common complexity classes A line chart of operations against input size n from 0 to 20, with the vertical axis capped at 100 operations. O(2ⁿ) leaves the chart before n reaches 7 and O(n²) at n equals 10. O(n log n) reaches about 86 at n equals 20. O(n) reaches 20, O(log n) about 4, and O(1) stays at 1. Constant factors are ignored. 5 10 15 20 25 50 75 100 0 input size n operations O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)

Upper, Lower, and Tight Bounds

Chart

O, Ω, and Θ as curves that hold f(n) in from n₀ onward.

Big O, Big Omega, and Big Theta as bounding curves Three small charts of the same wavy cost function f(n). In the first, a line c times g(n) lies above f(n) for every n from a point n₀ onward, although f(n) is above it at small n: f(n) is O(g(n)). In the second, a line c times g(n) lies below f(n) from n₀ onward: f(n) is Omega(g(n)). In the third, f(n) stays between a lower line c₁ times g(n) and an upper line c₂ times g(n) from n₀ onward: f(n) is Theta(g(n)). Shapes are illustrative. f(n) = O(g(n)) n₀ n c · g(n) f(n) f(n) stays below c · g(n) for every n ≥ n₀ f(n) = Ω(g(n)) n₀ n c · g(n) f(n) f(n) stays above c · g(n) for every n ≥ n₀ f(n) = Θ(g(n)) n₀ n c₂ · g(n) c₁ · g(n) f(n) f(n) stays between c₁ · g(n) and c₂ · g(n) for every n ≥ n₀

Merge Sort's Recursion Tree

Structure

Work per level of merge sort on eight elements, summed.

Recursion tree for merge sort on eight elements A tree of calls for merge sort on 8 elements. The root sorts 8 elements and splits into two calls on 4, which split into four calls on 2, which split into eight base cases of 1. The merges at each level handle 8 elements in total: one merge of 8, two of 4, and four of 2. The base cases merge nothing. Three levels of merging times 8 elements gives 24, which is n log₂ n. n = 8 n = 4 n = 4 n = 2 n = 2 n = 2 n = 2 1 1 1 1 1 1 1 1 WORK AT THIS LEVEL 8 1 merge of 8 elements 8 2 merges of 4 elements 8 4 merges of 2 elements 0 base cases: no merge 24 3 levels × 8 = n log₂ n log₂ 8 = 3 levels of merging, each doing n = 8 elements of work

The Call Stack During Factorial(4)

C4 · Dynamic

Four stack frames pushed by the calls, then popped by the returns.

Call stack for a recursive factorial of 4 A caller invokes Factorial(4), which calls Factorial(3), then Factorial(2), then Factorial(1). Each call pushes a new frame on top of the stack, and each waiting frame holds its own n. Factorial(1) is the base case and returns 1. The returns then pop the frames in reverse order: Factorial(2) returns 2, Factorial(3) returns 6, and Factorial(4) returns 24 to the caller. Factorial(1) base case: returns 1 Factorial(2) n = 2, waiting on 2 × Factorial(1) Factorial(3) n = 3, waiting on 3 × Factorial(2) Factorial(4) n = 4, waiting on 4 × Factorial(3) Caller of Factorial(4) returns 1 returns 2 returns 6 returns 24 CALLS PUSH FRAMES RETURNS POP FRAMES top of stack

Naive Fibonacci's Repeated Calls

Structure

The calls F(5) makes, and the ones memoization removes.

The call tree of naive recursive Fibonacci for n = 5, with memoization's savings marked The call tree of FibonacciNaive(5). F(5) calls F(4) and F(3). F(4) calls F(3) and F(2). Each F(3) calls F(2) and F(1), and each F(2) calls F(1) and F(0), for 15 calls in all. F(3) is computed twice and F(2) three times. With memoization, the calls down the left edge compute F(5), F(4), F(3), and F(2) once each and store them, along with the base cases F(1) and F(0) and one more F(1). The second F(2), under F(4), and the second F(3), under F(5), become lookups of stored values, so the 6 calls beneath them never happen. The memoized version makes 9 calls. F(5) F(4) F(3) F(2) F(1) F(0) F(1) F(2) F(1) F(0) F(3) F(2) F(1) F(0) F(1) Computed once and stored Base case, n ≤ 1 Already stored: a memo hit Never called with memoization The naive version makes all 15 calls. F(3) is computed twice and F(2) three times. Memoized, it makes 9: the 6 faded calls never happen, because F(3) and F(2) are looked up instead.

Append Cost in a Doubling Dynamic Array

Chart

Cost of each of 33 appends, with copies at each doubling.

Cost of each append to a dynamic array that doubles from capacity 4 A bar chart of 33 appends to a dynamic array that starts at capacity 4 and doubles when full. Most appends cost one element write. Appends 5, 9, 17, and 33 find the array full and also copy 4, 8, 16, and 32 elements into a new array twice the size. A line showing the average cost per append so far stays below 3 and ends at about 2.8. 10 20 30 1 copy 4 5 8 copy 8 9 16 copy 16 17 24 32 copy 32 33 average cost per append so far: 2.8 append number cost (element writes) write the new element copy into a doubled array

A Variable-Size Sliding Window

Flow

The windows the shortest-sum scan passes through, edge by edge.

The windows a variable-size sliding window passes through while finding the shortest run with sum at least 7 The array 2, 3, 1, 2, 4, 3 at indexes 0 to 5, searched for the shortest run of elements whose sum reaches 7. Each row shows a window the inner loop checks while its sum is at least 7, just before the left edge moves right. Indexes 0 to 3 sum to 8, length 4. Indexes 1 to 4 sum to 10, length 4. Indexes 2 to 4 sum to 7, length 3. Indexes 3 to 5 sum to 9, length 3. Indexes 4 to 5 sum to 7, length 2, the shortest. Elements to the left of each window have already been dropped, and elements to the right have not been reached yet. Both edges only move right, so each element enters and leaves the window at most once. Index 5 never leaves. EACH WINDOW THAT REACHES THE TARGET OF 7 0 1 2 3 4 5 2 3 1 2 4 3 0..3 sum 8, length 4 2 3 1 2 4 3 1..4 sum 10, length 4 2 3 1 2 4 3 2..4 sum 7, length 3 2 3 1 2 4 3 3..5 sum 9, length 3 2 3 1 2 4 3 4..5 sum 7, length 2 shortest Each row is a window the inner loop checks with sum at least 7, just before the left edge moves right. Both edges only move right, so each element enters the window once and leaves it at most once. In the window Shortest window found Already dropped from the left Not reached yet

Rectangular and Jagged Arrays in Memory

Structure

One contiguous block versus an array of separate row arrays.

How a rectangular array and a jagged array are laid out in memory Top: the rectangular array int[,] with rows 1, 2, 3 and 4, 5, 6 is one contiguous block of six elements stored row by row, so element [r, c] sits at position r times 3 plus c, and reading row by row walks memory in order. Bottom: the jagged array int[][] with rows of length 1, 2, and 3 is an array of three references, each pointing to its own row array stored separately in memory. Reaching element [r][c] takes two lookups, first the row reference and then the element within that row. RECTANGULAR: int[,] grid = { { 1, 2, 3 }, { 4, 5, 6 } } One contiguous block, stored row by row 1 [0,0] 2 [0,1] 3 [0,2] 4 [1,0] 5 [1,1] 6 [1,2] Element [r, c] sits at position r × 3 + c. Reading row by row walks memory in order. JAGGED: int[][] triangle, rows of length 1, 2, and 3 An array of references, each pointing to its own row array somewhere else in memory [0] [1] [2] 0 0 0 0 0 0 Element [r][c] takes two lookups: the row reference, then the element within that row.

Singly and Doubly Linked Lists

Structure

Nodes joined by pointers, and an insertion that changes two of them.

Singly linked, doubly linked, and inserting a node Three rows. First, a singly linked list: head points to node A, A points to B, B points to C, and C points to null. Each node holds a value and one pointer to the next node. Second, a doubly linked list of A, B, and C where each node also points back to the previous node, with head at A and tail at C. Third, inserting X after A in a singly linked list: first X's next pointer is set to B, which A currently points to, then A's next pointer is changed to X. The old link from A to B is replaced, and no other node moves. SINGLY LINKED: EACH NODE POINTS TO THE NEXT head A B C null DOUBLY LINKED: EACH NODE ALSO POINTS BACK head A B C tail INSERTING X AFTER A: TWO POINTER CHANGES, NOTHING SHIFTS A B old link X 2. A.Next = X 1. X.Next = A.Next (B)

Reversing a Linked List

Flow

How the previous and current references flip one Next pointer per pass until the list points the other way.

Reversing the list A, B, C one pointer at a time Four rows show the list A, B, C during reversal. At the start, A points to B, B to C, and C to null, with previous at null and current at A. After one pass, A points to null, and B still points to C; previous is A and current is B, with no link between them. After two passes, B points back to A and A to null, C still points to null; previous is B and current is C. After three passes, C points to B, B to A, and A to null; previous is C, the new head, and current is null. Each pass saves current's Next, points current back at previous, and moves both references one node right. The missing link between the reversed part and the rest is why the next node must be saved before flipping. START null null A B C previous current AFTER ONE PASS null null A B C previous current AFTER TWO PASSES null null A B C previous current AFTER THREE PASSES: DONE null null A B C previous current Each pass saves current.Next, points current back at previous, then moves both references one node right. The gap between the flipped part and the rest is why next must be saved first. Previous ends on C, the new head.

Floyd's Cycle Detection

Flow

A slow and a fast reference closing on each other inside a loop.

Floyd's cycle detection on a list whose last node points back into it A linked list of nodes 1 to 8 where node 8 points back to node 3, so nodes 1 and 2 lead into a loop of six nodes, 3 through 8. A slow reference moves one node per step and a fast reference two. Both start at node 1. After step 1, slow is at 2 and fast at 3. After step 2, slow is at 3 and fast at 5, both inside the loop, with fast 4 nodes behind slow going around. Each later step closes that gap by 1: slow 4 and fast 7 with gap 3, slow 5 and fast 3 with gap 2, slow 6 and fast 5 with gap 1, and after step 6 both are at node 7, where they meet. A LIST WHOSE LAST NODE POINTS BACK TO NODE 3 1 2 3 4 5 6 7 8 Nodes 1 and 2 lead in. Nodes 3 to 8 form a loop of 6. The references meet at node 7. EACH STEP: SLOW +1, FAST +2 StepSlowFastGap 011 123 2354 3473 4532 5651 6770 Gap: how far fast is behind slow around the loop. Once both are in it, each step closes it by exactly 1.

A Queue in a Circular Buffer

Structure

Head and tail indices wrapping around a fixed array.

Queue stored in a circular buffer of eight slots An array of eight slots, indexed 0 to 7. Slots 5, 6, and 7 hold A, B, and C, and slots 0 and 1 hold D and E. Slots 2, 3, and 4 are empty. The head index is 5, where the next dequeue reads, and the tail index is 2, where the next enqueue writes. An arrow from the end of the array back to the start shows that the index after 7 is 0, computed as index plus one modulo the capacity. The queue's order from front to back is A, B, C, D, E. D 0 E 1 2 3 4 A 5 B 6 C 7 index head = 5 next Dequeue reads here tail = 2 next Enqueue writes here after index 7, the next index is 0: (index + 1) % capacity Queue order, front to back: A, B, C, D, E. Count = 5, capacity = 8.

Growing a Wrapped Circular Buffer

Flow

Why growing a full, wrapped queue copies its elements front first instead of slot by slot.

A full, wrapped circular buffer of capacity 4 growing to capacity 8 Top: a full circular buffer of four slots holding C, D, A, B at indexes 0 to 3. The head and the tail are both at index 2. The count of 4 says the buffer is full, because an empty buffer also has head equal to tail. Bottom: after growing to eight slots, the elements are copied in queue order, front first, so A, B, C, D occupy slots 0 to 3, the head is 0, and the tail is 4. Arrows run from each old slot to its new slot: A from 2 to 0, B from 3 to 1, C from 0 to 2, D from 1 to 3. Copying the slots in place would have kept C, D, A, B, the wrong queue order. FULL AND WRAPPED, CAPACITY 4 0 C 1 D 2 A 3 B head = 2, tail = 2 Count = 4, so head == tail means full. An empty queue also has head == tail. Grow copies in queue order, front first: A, B, C, D land in slots 0 to 3. AFTER GROW, CAPACITY 8 0 A 1 B 2 C 3 D 4 5 6 7 head = 0 tail = 4 Copying the slots as they sit would give C, D, A, B, and the queue would come out in the wrong order.

Two Ways to Resolve a Collision

Structure

Chaining and linear probing placing two keys that share a slot.

Separate chaining compared with linear probing Four keys hash into an eight-slot table: cat to slot 2, dog to 5, emu to 2, and fox to 6, so cat and emu collide. With separate chaining, slot 2 holds cat and a chain that links on to emu, and every other key sits in its own slot. With open addressing and linear probing, every key sits in the table itself: slot 2 is already taken by cat, so emu probes the next slot and lands in slot 3. KEYS AND THEIR SLOTS: hash(key) % 8 cat → 2 dog → 5 emu → 2 fox → 6 SEPARATE CHAINING 0 1 2 3 4 5 6 7 cat dog fox emu emu collides with cat and joins slot 2's chain OPEN ADDRESSING, LINEAR PROBING 0 1 2 3 4 5 6 7 cat dog fox emu slot 2 is taken, so emu probes the next slot, 3

Inside Dictionary

Structure

How a .NET dictionary keeps its chains as integer links inside two arrays instead of as linked nodes.

A dictionary's buckets array pointing into its entries array A dictionary with five buckets and an entries array of five slots. The keys cat, dog, emu, and fox were added in that order and sit in entries 0 to 3; entry 4 is not used yet. Cat and emu both reduce to bucket 2, dog to bucket 0, and fox to bucket 4. Buckets 1 and 3 are empty. Bucket 0 points to entry 1, bucket 2 to entry 2, and bucket 4 to entry 3. Each new entry goes to the head of its chain, so emu's next field holds 0, linking to cat, whose next marks the end of the chain. Looking up cat reads bucket 2, checks emu, and follows the next link to cat. Enumerating the dictionary walks the entries array in index order, which matches insertion order until a removal frees a slot that a later add reuses. BUCKETS first entry in each chain ENTRIES each also caches its hash code 0 entry 1 1 empty 2 entry 2 3 empty 4 entry 3 key value next 0 "cat" 3 end 1 "dog" 5 end 2 "emu" 7 0 3 "fox" 1 end 4 not used yet same chain Keys cat and emu both reduce to bucket 2. Each new entry goes to the head of its chain, so bucket 2 names emu, and emu's next names cat. Looking up cat: bucket 2, then entry 2 (emu, no match), then its next, entry 0 (cat, match).

Parts of a Tree

Structure

Root, internal nodes, leaves, depth, height, and a subtree in one tree.

A six-node binary tree labelled with tree vocabulary A binary tree with root A at depth 0. A's children are B and C at depth 1. B's children are D and E, and C has one right child, F, all at depth 2. A is the root. Like B and C, it is also an internal node, because it has children. D, E, and F are leaves. A box around B, D, and E marks the subtree rooted at B. A bracket on the right shows the tree's height is 2, the number of edges from A down to the deepest leaf. subtree rooted at B A B C D E F depth 0 depth 1 depth 2 height = 2 (edges from A down to the deepest leaf) root internal node leaf root internal node (has children) leaf (no children) The root has children too, so it is also an internal node.

The Same Keys, Two Tree Shapes

Structure

Insertion order decides a binary search tree's height.

A balanced and a skewed binary search tree holding the same keys Two binary search trees holding the keys 1 to 7. Inserted in the order 4, 2, 6, 1, 3, 5, 7, the tree is balanced: 4 at the root, 2 and 6 below it, and 1, 3, 5, 7 as leaves, with height 2. Searching for 5 visits 4, 6, then 5. Inserted in sorted order 1 through 7, every key becomes the right child of the one before, forming a chain of height 6, and searching for 5 visits 1, 2, 3, 4, and 5. INSERTED AS 4, 2, 6, 1, 3, 5, 7 4 2 6 1 3 5 7 Height 2. Searching for 5 visits 4, 6, 5. A search never visits more than 3 nodes. INSERTED AS 1, 2, 3, 4, 5, 6, 7 1 2 3 4 5 6 7 Height 6. Searching for 5 visits 1, 2, 3, 4, 5. The tree has become a linked list.

Deleting a Node with Two Children

Flow

How a binary search tree replaces a deleted key with its in-order successor and keeps its ordering rule.

Deleting 50 from a binary search tree by way of its in-order successor, 60 Before: a binary search tree with 50 at the root, 30 and 70 below it, 20 and 40 under 30, 60 and 80 under 70, and 65 as 60's right child. Deleting 50, which has two children, starts by finding its in-order successor: one step right to 70, then left as far as possible, to 60. After: 60 has been copied into the root, and the old 60 node has been removed. That removal is the one-child case, because 60 has no left child, so its right child 65 moves up to become 70's left child. The tree is 60 at the root, 30 with 20 and 40 on the left, and 70 with 65 and 80 on the right, and the ordering rule still holds. BEFORE: DELETE 50, WHICH HAS TWO CHILDREN 50 30 70 20 40 60 80 65 deleted key successor: right once, then left to the end AFTER 60 30 70 20 40 65 80 60 copied into the root 65 moved up into 60's old place 60 is the smallest key in 50's right subtree, so it is larger than everything on the left and smaller than the rest on the right. Removing 60 from its old spot is the one-child case: it has no left child, and its right child, 65, takes its place.

A Binary Heap as a Tree and as an Array

Structure

One min-heap drawn as a tree and stored as an array.

A min-heap shown as a tree and as the array that stores it A min-heap holding 1, 3, 6, 5, 9, 8. As a tree, 1 is the root at index 0, its children are 3 at index 1 and 6 at index 2, the children of 3 are 5 and 9 at indexes 3 and 4, and the left child of 6 is 8 at index 5. Every parent is less than or equal to its children. As an array, the same values sit in level order: 1, 3, 6, 5, 9, 8. Arrows from index 1 to indexes 3 and 4 show that the children of index i are at 2i + 1 and 2i + 2, and the parent of i is at (i − 1) / 2. 1 [0] 3 [1] 6 [2] 5 [3] 9 [4] 8 [5] AS A TREE: EVERY PARENT ≤ ITS CHILDREN AS AN ARRAY: LEVEL BY LEVEL, LEFT TO RIGHT 1 0 3 1 6 2 5 3 9 4 8 5 index children of i: 2i + 1 and 2i + 2 parent of i: (i − 1) / 2

Removing the Minimum from a Heap

Flow

How a min-heap refills its root and sifts the moved element down one path to restore the order rule.

Sifting down after removing the minimum from a min-heap Three steps on the min-heap built from 10, 5, 20, 3, 8, 15, whose array is 3, 5, 15, 10, 8, 20. Step 1: the minimum, 3, is removed and the last element, 20, moves into the root, giving the array 20, 5, 15, 10, 8. The root's children are 5 and 15, and 5 is smaller, so 20 and 5 swap. Step 2: the array is 5, 20, 15, 10, 8, and 20 now has children 10 and 8. 8 is smaller, so 20 and 8 swap. Step 3: the array is 5, 8, 15, 10, 20. 20 is a leaf, every parent is at most its children, and the heap is valid again with 5 at the root. The moved element travelled one path from the root to a leaf, at most the height of the tree. 1. 3 REMOVED, 20 MOVED TO THE ROOT 20 5 15 10 8 20 0 5 1 15 2 10 3 8 4 Children 5 and 15: 5 is smaller, so 20 and 5 swap. 2. 20 SWAPPED WITH 5 5 20 15 10 8 5 0 20 1 15 2 10 3 8 4 Children 10 and 8: 8 is smaller, so 20 and 8 swap. 3. 20 SWAPPED WITH 8: DONE 5 8 15 10 20 5 0 8 1 15 2 10 3 20 4 20 is a leaf now. Every parent is at most its children again.

A Trie Holding Four Words

Structure

car, cart, cat, and dog stored letter by letter, sharing prefixes.

A trie storing the words car, cart, cat, and dog A trie whose root holds no letter. The root has two children, c and d. Under c is a, and under a are r and t. Under r is another t. Under d is o, and under o is g. The nodes r, t under a, g, and the t under r are marked as word ends, spelling car, cat, dog, and cart along the path from the root. The path c then a is shared by car, cart, and cat, so the prefix ca is stored once. The node r marks the end of car and still has a child, because car is also the start of cart. root (no letter) c d a o r “car” t “cat” g “dog” t “cart” A word ends here Letter on a path Prefix “ca”, stored once “car” is a word and also the start of “cart”, so its node is marked and still has a child.

A Tree Rotation

Structure

A right rotation at y lifts x without breaking search order.

A right rotation and its inverse, a left rotation Before: node y has left child x and right subtree C. Node x has left subtree A and right subtree B. A right rotation at y makes x the root of this part of the tree, with A as its left subtree and y as its right child. Subtree B moves across to become y's left subtree, and C stays y's right subtree. A left rotation at x reverses the change. In both trees an in-order walk reads A, x, B, y, C, so the binary search tree order is preserved. A moves up one level, C moves down one level, and B keeps its depth under a new parent. BEFORE y x C A B x is y’s left child. B is x’s right subtree. rotate right at y rotate left at x AFTER x y A B C x takes y’s place. B becomes y’s left subtree. In both trees an in-order walk reads A, x, B, y, C, so the search-tree order holds. A moves up one level, C moves down one, and B keeps its depth under a new parent.

An AVL Double Rotation

Structure

The left-right case fixed by a left rotation, then a right rotation.

Fixing the left-right case in an AVL tree with two rotations Step 1: node z is out of balance. Its left child is x, and its right subtree is D. x has left subtree A and right child y, and y has subtrees B and C. The extra height is under x's right child, the left-right case. Step 2: a left rotation at x moves y above x. y becomes z's left child, with x as y's left child holding A and B, and C as y's right subtree. The tall part is now on the outside, a left-left case. Step 3: a right rotation at z makes y the root of this part of the tree, with x as its left child holding A and B, and z as its right child holding C and D. The result is balanced and one level shorter. An in-order walk reads A, x, B, y, C, z, D in all three trees. B and C are the subtrees that change parent. 1. LEFT-RIGHT CASE AT z z x y D A B C z’s left side is 2 taller, and the extra height is under x’s right child. 2. ROTATE LEFT AT x z y x D C A B y moves above x. The tall part is now on the outside, a left-left case. 3. ROTATE RIGHT AT z y x z A B C D y takes z’s place with x and z as its children. Balanced, one level shorter. In-order reads A, x, B, y, C, z, D in all three trees. y’s subtrees B and C are split between x and z. Out of balance Subtrees that change parent

A Segment Tree Answering a Range Sum

Structure

Sum(2, 6) over eight values, answered from three stored sums.

A segment tree over eight values answering the sum of indexes 2 to 6 A segment tree over the array 5, 8, 6, 3, 2, 7, 2, 6. Each node holds the sum of a range of indexes. The root covers 0 to 7 with sum 39. Its children cover 0 to 3 with sum 22 and 4 to 7 with sum 17. The next level covers 0 to 1 (13), 2 to 3 (9), 4 to 5 (9), and 6 to 7 (8), and the leaves hold the eight single values. To sum indexes 2 to 6, the query splits at the root, at 0 to 3, at 4 to 7, and at 6 to 7. It uses the stored sums of 2 to 3 (9), 4 to 5 (9), and the single index 6 (2), for a total of 20. The nodes for 0 to 1 and index 7 lie outside the range and return 0, and the leaves under them and under 2 to 3 and 4 to 5 are never visited. [0] 5 [1] 8 [0..1] 13 [2] 6 [3] 3 [2..3] 9 [0..3] 22 [4] 2 [5] 7 [4..5] 9 [6] 2 [7] 6 [6..7] 8 [4..7] 17 [0..7] 39 query: sum of indexes 2 to 6 Fully inside: stored sum used Partly inside: both children asked Outside: returns 0 Never visited Sum(2, 6) = 9 + 9 + 2 = 20, read from three stored nodes instead of adding five array values.

What Each Fenwick Tree Slot Covers

Structure

The block each slot sums, and the slots a query and an update touch.

The blocks of positions covered by the slots of an eight-element Fenwick tree Eight positions numbered 1 to 8, with one bar per slot showing the positions it sums. Slots 1, 3, 5, and 7 cover one position each. Slot 2 covers 1 to 2, slot 6 covers 5 to 6, slot 4 covers 1 to 4, and slot 8 covers 1 to 8. Each bar's length is the lowest set bit of the slot number. Left: a prefix sum through position 7 adds slots 7, 6, and 4, which cover positions 7, 5 to 6, and 1 to 4, stepping 7, 6, 4, 0 by removing the lowest set bit each time. Right: adding to position 5 updates slots 5, 6, and 8, every block that holds position 5, stepping 5, 6, 8, 16 by adding the lowest set bit each time and stopping past the end. PREFIX SUM THROUGH POSITION 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Adds slots 7, 6, then 4: positions 7, 5–6, and 1–4. Each step removes the lowest set bit: 7 → 6 → 4 → 0, stop. ADD TO POSITION 5 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Updates slots 5, 6, then 8: every block holding 5. Each step adds the lowest set bit: 5 → 6 → 8 → 16, past the end, stop. Each bar is one slot of the array. It stores the sum of the positions it spans, and its length is the lowest set bit of the slot number. Positions count from 1 here. The code’s index i uses slot i + 1.

One Graph, Two Representations

Structure

The same four-vertex graph as an adjacency list and a matrix.

An undirected graph stored as an adjacency list and as an adjacency matrix An undirected graph with vertices A, B, C, and D and edges A–B, A–C, B–C, and C–D. As an adjacency list, A lists B and C, B lists A and C, C lists A, B, and D, and D lists C, for 8 entries, since each undirected edge appears in both endpoints' lists. As an adjacency matrix, a 4 by 4 grid holds 1 where the row and column vertices share an edge and 0 elsewhere. The matrix is symmetric and has 16 cells regardless of how many edges exist. THE GRAPH A B C D 4 vertices, 4 undirected edges ADJACENCY LIST A B C B A C C A B D D C Each vertex lists its neighbors. 8 entries: each edge appears twice. ADJACENCY MATRIX A A 0 1 1 0 B B 1 0 1 0 C C 1 1 0 1 D D 0 0 1 0 Row A, column B holds 1 if A–B is an edge. 16 cells whatever the edge count.

Breadth-First and Depth-First Visit Order

Flow

The order BFS and DFS reach the same six vertices.

Breadth-first and depth-first search on the same graph, starting from A An undirected graph with edges A–B, A–C, B–D, B–E, C–F, and E–F, searched twice from A, taking neighbors in the order they were added. Breadth-first search visits A, then B and C at distance 1, then D, E, and F at distance 2. It first reaches each vertex along A–B, A–C, B–D, B–E, and C–F, and the edge E–F leads only to a vertex already visited. Depth-first search visits A, B, D, E, F, then C. It goes from A to B, down to D, back up to B, then to E, on to F, and reaches C last through F. The edge A–C leads only to a vertex already visited. BREADTH-FIRST FROM A distance 0 distance 1 distance 2 A 1 B 2 C 3 D 4 E 5 F 6 Visits A, B, C, D, E, F: every vertex at distance 1 before any at distance 2. DEPTH-FIRST FROM A A 1 B 2 C 6 D 3 E 4 F 5 Visits A, B, D, E, F, C: it follows one branch as far as it goes, reaching C last, through F. Edge that first reached a vertex Edge to a vertex already visited 1Visit order

Detecting a Cycle in a Directed Graph

Flow

An edge to a finished vertex versus an edge back into the current path.

Two moments in a depth-first cycle check on a directed graph Left: a directed graph with edges A to B, A to C, and C to B, searched from A. The search has already explored B, which is done. It is now at C, reached from A, so A and C are in progress. The edge C to B leads to a done vertex, so it closes no cycle. Right: a directed graph with edges A to B, B to C, and C to A, searched from A. A, B, and C are all in progress on the current chain of calls. The edge C to A leads back to an in-progress vertex, closing the cycle A to B to C to A. EDGES A → B, A → C, C → B A B C checking C → B B finished before the search reached C. An edge to a done vertex closes nothing. No cycle EDGES A → B, B → C, C → A A B C checking C → A A, B, and C are all on the current chain of calls. An edge back to A closes the loop A → B → C → A. Cycle In progress Done Current chain of calls Explored earlier

Dijkstra's Algorithm on a Small Graph

Flow

The order vertices settle, and the distance each settles at.

Dijkstra's algorithm run from A on a five-vertex weighted graph An undirected weighted graph with edges A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 7, and D–E 2. Dijkstra's algorithm from A settles A at 0, then C at 2 via A, then B at 3 via C, then D at 8 via B, then E at 9 via C. The edges on these shortest paths are A–C, C–B, B–D, and C–E. B was first reached directly from A at distance 4, and when C settled at 2, the edge C–B offered 2 plus 1 equals 3, so B's distance dropped to 3. 4 2 1 5 8 7 2 A 0 1 B 3 3 C 2 2 D 8 4 E 9 5 SETTLED IN ORDER 1 A at 0, via start 2 C at 2, via A → C 3 B at 3, via A → C → B 4 D at 8, via A → C → B → D 5 E at 9, via A → C → E B was first reached directly from A at 4. When C settled at 2, the edge C–B offered 2 + 1 = 3, so B’s distance dropped to 3. Edge on a shortest path from A 8Shortest distance from A 4Order settled

Cells Explored by Dijkstra and A*

Chart

The same grid search with and without a distance estimate.

The cells expanded by Dijkstra and by A* on the same grid A 25 by 15 grid with a vertical wall in the middle column, from row 3 to row 11. The search runs from S on the left to G on the right, moving up, down, left, or right at cost 1. With an estimate of 0, which is Dijkstra's algorithm, the search expands 337 cells, spreading out in every direction from S, including away from the goal. With the Manhattan distance to G as the estimate, A* expands 151 cells, mostly in a band between S and the openings above and below the wall. Both find a path of 26 steps around the end of the wall. DIJKSTRA (ESTIMATE 0) S G 337 cells expanded, path of 26 steps A* (MANHATTAN DISTANCE) S G 151 cells expanded, path of 26 steps Expanded Path found Wall Never expanded

A Topological Order of Build Steps

Flow

Six build steps with dependencies, ordered so each follows its prerequisites.

A directed acyclic graph of build steps and a topological order of them Six build steps connected by "must finish before" arrows: restore to compile, compile to test, compile to docs, test to pack, docs to pack, and pack to publish. Restore has in-degree 0, pack has in-degree 2, and the others have in-degree 1. Kahn's algorithm starts with restore, the only step with in-degree 0. Finishing a step lowers the in-degree of each step it points to, and a step becomes ready when its in-degree reaches 0, so pack waits for both test and docs. The order produced is restore, compile, test, docs, pack, publish. Swapping test and docs is also a valid order. restore in-degree 0 1 compile in-degree 1 2 test in-degree 1 3 docs in-degree 1 4 pack in-degree 2 5 publish in-degree 1 6 EACH ARROW MEANS “MUST FINISH BEFORE” Only restore starts with in-degree 0. Finishing a step lowers the in-degree of each step it points to, and a step becomes ready at 0. pack waits for both test and docs. One valid order: restore, compile, test, docs, pack, publish. Swapping test and docs is also valid. 1Position in the order Kahn’s algorithm produces

Path Compression in Union-Find

Structure

One Find flattening the path it walked to the root.

A union-find tree before and after Find(1) with path compression Before: a set stored as a tree of parent pointers with root 4, a shape that forms without union by rank. Vertices 3 and 6 point to 4, 2 points to 3, and 1 points to 2. Find(1) follows 1 to 2 to 3 to 4 to reach the root. After: path compression has made 1, 2, and 3 point straight at 4, and 6 still points at 4, so the next Find on 1, 2, or 3 takes one step. BEFORE Find(1) 4 3 6 2 1 Find(1) follows 1 → 2 → 3 → 4 to reach the root. A chain this long forms without union by rank. AFTER Find(1) 4 1 2 3 6 Every vertex on that path now points straight at 4, so the next Find on 1, 2, or 3 takes one step. Parent pointer Root, which names the set On the Find path

Kruskal's Algorithm Building a Minimum Spanning Tree

Flow

Edges taken cheapest first, skipping any that would close a cycle.

Kruskal's algorithm on a five-vertex weighted graph The same weighted graph: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 7, and D–E 2. Kruskal's algorithm takes edges in order of weight. It takes B–C (1), A–C (2), and D–E (2). It skips A–B (4) because A and B are already joined through C. It takes B–D (5), which joins the two pieces. It skips C–E (7) and C–D (8) because their ends are already connected. The four edges taken join all five vertices with total weight 10. 4 2 1 5 8 7 2 A B C D E EDGES IN WEIGHT ORDER B–C (1) take A–C (2) take D–E (2) take A–B (4) skip: A and B already joined B–D (5) take C–E (7) skip: C and E already joined C–D (8) skip: C and D already joined 4 edges join all 5 vertices. Total weight 10. In the tree Skipped: its ends were already connected, so it would close a cycle

A Reverse Edge Undoing a Poor Choice

Flow

How a residual reverse edge lets a later path reroute earlier flow.

Maximum flow found by pushing flow back along a reverse edge A network with source s, sink t, and vertices a and b. Every edge has capacity 1: s to a, s to b, a to b, a to t, and b to t. Step 1: a first path chosen without breadth-first search is s to a to b to t, carrying 1. After it, every path from s to t in the original edges runs into a full edge. Step 2, showing only the edges the second path uses: spare capacity remains on s to b and a to t, and using a to b created a reverse edge from b to a with capacity 1. The path s to b to a to t uses that reverse edge. Step 3: the final flow sends 1 along s to a to t and 1 along s to b to t, and a to b carries nothing, because the second path cancelled the first path's use of it. The maximum flow is 2. 1. A POOR FIRST PATH: s → a → b → t 1/1 1/1 1/1 0/1 0/1 s a b t Flow 1. Every path left from s to t now runs into a full edge. 2. THE SECOND PATH 1 1 1 back s a b t Using a → b created spare capacity b → a. Path s → b → a → t uses it. 3. FINAL FLOW 1/1 1/1 1/1 1/1 0/1 s a b t Flow 2. The second path cancelled the first path’s use of a → b. Carrying flow (flow/capacity) Spare capacity on the second path Reverse edge

Binary Search Step by Step

Flow

How binary search halves the range it still has to check with each comparison until it finds a match or the range is empty.

Binary search for 63 in a sorted array of 15 values A sorted array of 15 values, 3, 8, 12, 17, 21, 25, 30, 34, 41, 47, 52, 58, 63, 70, 77, at indexes 0 to 14, searched for 63. Step 1: the range is 0 to 14, the middle is index 7, and 34 is less than 63, so the left half is ruled out and left becomes 8. Step 2: the range is 8 to 14, the middle is index 11, and 58 is less than 63, so left becomes 12. Step 3: the range is 12 to 14, the middle is index 13, and 70 is more than 63, so right becomes 12. Step 4: the range is just index 12, which holds 63, a match. Four comparisons cover 15 values, because each one rules out half of what remains. SEARCHING FOR 63 IN 15 SORTED VALUES 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 step 1 3 8 12 17 21 25 30 34 41 47 52 58 63 70 77 left 0, right 14, mid 7. sorted[7] is 34, less than 63, so left = 8. step 2 3 8 12 17 21 25 30 34 41 47 52 58 63 70 77 left 8, right 14, mid 11. sorted[11] is 58, less than 63, so left = 12. step 3 3 8 12 17 21 25 30 34 41 47 52 58 63 70 77 left 12, right 14, mid 13. sorted[13] is 70, more than 63, so right = 12. step 4 3 8 12 17 21 25 30 34 41 47 52 58 63 70 77 left 12, right 12, mid 12. sorted[12] is 63: found at index 12. Still in range Middle, compared Match Ruled out

A Rotated Sorted Array

Chart

A rotated sorted array cut at its first midpoint, with the sorted half marked.

The values of a rotated sorted array plotted against their indexes, cut at the midpoint The array 40, 50, 60, 10, 20, 30 plotted as value against index 0 to 5. The points form two rising runs: 40, 50, 60 at indexes 0 to 2, then a drop, then 10, 20, 30 at indexes 3 to 5. A vertical line marks the first midpoint, index 2, holding 60. The part from index 0 to the midpoint is shaded as the sorted half, since 40 is at most 60. The part from the midpoint on holds the drop. A target between 40 and 60, if present, must be in the sorted half, and any other target must be in the other half. Because there is only one drop, it lies on one side of any midpoint, so the other side is always one ascending run. THE ROTATED ARRAY 40, 50, 60, 10, 20, 30, VALUE BY INDEX sorted half: 40 to 60 other half holds the drop 0 1 2 3 4 5 index the drop mid = 2 40 50 60 10 20 30 values[0] = 40 is at most values[2] = 60, so the left half is sorted. A target from 40 up to 60, if present, must be there, and any other target must be on the right. Wherever the midpoint falls, the drop can be on only one side of it, so the other side is always one ascending run.

A Comparison Sort as a Decision Tree

Structure

The comparisons a sort makes on three elements, drawn as a tree with one leaf per possible order.

Decision tree of an insertion-style sort on three elements A binary tree of comparisons for sorting a, b, and c. The root asks whether a is at most b. If yes, the next question is whether b is at most c: yes ends at the order a, b, c; no asks whether a is at most c, ending at a, c, b for yes and c, a, b for no. If a is more than b, the next question is whether a is at most c: yes ends at b, a, c; no asks whether b is at most c, ending at b, c, a for yes and c, b, a for no. The six leaves are the six possible orders of three elements. A binary tree of height 2 has at most 4 leaves, so at least one input needs 3 comparisons; two inputs finish after 2 and four take 3. ANY COMPARISON SORT ON a, b, c CAN BE DRAWN AS A TREE LIKE THIS yes no yes no yes no yes no yes no a ≤ b ? b ≤ c ? a ≤ c ? a, b, c a ≤ c ? b, a, c b ≤ c ? a, c, b c, a, b b, c, a c, b, a Each box asks one comparison, and each shaded leaf is the sorted order it concludes. The 3! = 6 possible input orders need 6 leaves. A tree of height 2 holds at most 4 leaves, so some input must take 3 comparisons. Here, two orders finish after 2 and four take 3.

The Edit Distance Table

Structure

The dynamic programming table for turning horse into ros, with the path of edits traced back from the answer.

Edit distance table for horse and ros A grid with the prefixes of horse down the side (empty, h, o, r, s, e) and the prefixes of ros across the top (empty, r, o, s). Row by row, the values are 0 1 2 3; 1 1 2 3; 2 2 1 2; 3 2 2 2; 4 3 3 2; 5 4 4 3. The bottom-right cell, 3, is the edit distance. A shaded path runs back from it to the top-left corner through the cells 3, 2, 2, 1, 1, 0, which spell out the edits: substitute h with r, keep o, delete r, keep s, delete e. A side panel shows that each cell is computed from its diagonal neighbor (a match or a substitution), the cell above (a deletion), or the cell to the left (an insertion). The first row and column are base cases, one edit per character. EDIT DISTANCE FROM "horse" TO "ros" "" r o s "" h o r s e 0 1 2 3 1 1 2 3 2 2 1 2 3 2 2 2 4 3 3 2 5 4 4 3 EACH CELL COMES FROM ONE OF THREE diagonal above left d[i, j] From the diagonal: match (free) or substitute. From above: delete a character of "horse". From the left: insert a character of "ros". The shaded path walks back from the answer, 3, to the empty-string corner: substitute h with r, keep o, delete r, keep s, delete e. The first row and column are the base cases: turning a prefix into an empty string, or back, costs one edit per character.

Scheduling Meetings by Earliest Finish

Chart

Six meeting requests on a timeline, with the three that earliest-finish-first selects.

Six meetings on a timeline from 0 to 11, with A, D, and F selected Six meeting requests drawn as bars on a timeline from 0 to 11, in order of end time: A from 1 to 4, B from 3 to 5, C from 0 to 6, D from 5 to 7, E from 3 to 9, and F from 8 to 11. The greedy rule takes the meeting that ends earliest, A, which frees the room at 4. B, C, and E overlap a taken meeting and are skipped. D starts at 5, after 4, so it is taken, freeing the room at 7. F starts at 8 and is taken. The result is A, D, and F. SIX MEETING REQUESTS, SORTED BY END TIME 0 1 2 3 4 5 6 7 8 9 10 11 A 1–4 taken B 3–5 skipped: overlaps C 0–6 skipped: overlaps D 5–7 taken E 3–9 skipped: overlaps F 8–11 taken room free at 4 free at 7 Earliest finish first takes A, D, and F. Each meeting it skips overlaps one already taken.
Structure

The partial boards a backtracking search visits for four queens, with dead ends pruned and both solutions found.

The pruned search tree for the four-queens problem A tree of partial placements for four queens on a 4 by 4 board, one queen per row. From the start, row 0 can take a queen in any of columns 0 to 3. Column 0 leads to row 1 columns 2 and 3. The row 1 queen in column 2 is a dead end with no safe square in row 2, and the one in column 3 leads to row 2 column 1, a dead end in row 3. Column 1 in row 0 leads to 3, then 0, then 2, a solution. Column 2 in row 0 leads to 0, then 3, then 1, the second solution. Column 3 mirrors column 0 and dead-ends. The search visits 16 partial boards, compared with 256 ways to place one queen in each row, and finds two solutions. PLACING FOUR QUEENS, ONE ROW AT A TIME start 0 2 dead end 3 1 dead end 1 3 0 2 2 0 3 1 3 0 2 dead end 1 dead end row 0 row 1 row 2 row 3 Each circle is a queen placed in that row, labeled with its column. A branch stops as soon as no column in the next row is safe. The search visits 16 partial boards instead of the 256 complete ones, and finds the two solutions: columns 1, 3, 0, 2 and 2, 0, 3, 1. No safe square in the next row All four queens placed

Found this useful? Share it:

Share on LinkedIn