Cheatsheets
Data structures & Big-O
Complexity classes plus the core structures, traversals, and sorts.
Visualize
Binary search tree — search (3D)
Each comparison goes left or right, halving the search space — O(log n).
Stack — LIFO
Push and pop from the top.
Push and pop to see LIFO order.
Queue — FIFO
Enqueue at the back, dequeue from the front.
Enqueue and dequeue to see FIFO order.
Big-O growth
How the number of operations scales with input size.
- O(2ⁿ)Horrible
- O(n²)Bad
- O(n log n)Fair
- O(n)Good
- O(log n)Excellent
- O(1)Excellent
Sorting — bubble sort
Watch comparisons and swaps; the sorted tail grows green.
Press play to watch bubble sort run.
BST traversals
In-, pre-, and post-order over a binary search tree.
Left, node, right → visits a BST in sorted order.
Hash table
hash(key) % N picks a bucket; collisions chain.
hash(key) % N picks the bucket. Two keys in one bucket = a collision, resolved by chaining (a list per bucket). Good hashing keeps chains short → average O(1).
Binary search
Halve the range each step to find a target in O(log n).
O(log n) — each step halves the search space.
Linked list
Insert and delete by re-pointing next.
Insert/delete at a known node is O(1) — just re-point next. (Finding the node first is still O(n).)
38 entries
Big-O complexity7
O(1)Constant — array index, hash lookup, stack push/pop.
O(log n)Logarithmic — binary search, balanced-tree ops.
O(n)Linear — one pass over the data.
O(n log n)The good comparison sorts (merge, heap, Timsort).
O(n²)Nested loops — bubble/insertion sort, naive pair scans.
O(2ⁿ) / O(n!)Exponential / factorial — brute-force subsets & permutations.
Amortized O(1)Dynamic array append, hash insert.
Arrays & strings6
access O(1) · search O(n)Index is instant; finding a value scans.
insert / delete (middle) O(n)Everything after the gap must shift.
Two pointersPair/partition scans in O(n) time, O(1) space.
Sliding windowSubarray/substring problems in O(n) instead of O(n²).
Prefix sumRange-sum queries in O(1) after O(n) prep.
Binary searchO(log n) lookup in sorted data.
Stacks & queues4
Stack (LIFO)push / pop / peek all O(1). Last in, first out.
Queue (FIFO)enqueue / dequeue O(1). First in, first out.
DequeO(1) push/pop at BOTH ends.
Monotonic stackStack kept sorted — next-greater-element in O(n).
Linked lists3
Linked listO(1) insert/delete at a known node; O(n) search (no indexing).
Reverse a listIterative pointer flip, O(n) time / O(1) space.
Fast / slow pointersCycle detection & middle node in one pass.
Hashing3
Hash mapavg O(1) get/set/delete; O(n) worst case (collisions).
SetMembership test in avg O(1); union/intersection built in.
Collision handlingChaining (buckets of entries) vs open addressing (probe to next slot).
Trees & heaps5
BSTsearch/insert/delete O(log n) if balanced, O(n) if it degenerates to a list.
Balanced (AVL / Red-Black)Rotations keep height ~log n, so worst case stays O(log n).
Heap (priority queue)peek-min O(1); push/pop O(log n).
Traversalsin / pre / post-order (DFS) and level-order (BFS).
TriePrefix lookup in O(key length), independent of how many keys are stored.
Graphs5
Adjacency list vs matrixList: O(V+E) space, sparse graphs. Matrix: O(V²), O(1) edge test, dense graphs.
BFSShortest path in an UNWEIGHTED graph; O(V + E).
DFSExplore/backtrack; cycle detection, topological sort; O(V + E).
DijkstraShortest path with non-negative weights; O(E log V) with a heap.
Union-Find (DSU)Near-O(1) connectivity with path compression + union by rank.
Sorting5
list.sort() / sorted()Timsort: O(n log n), stable, fast on real-world (partly sorted) data.
QuicksortO(n log n) average, O(n²) worst (bad pivots), in-place, NOT stable.
MergesortO(n log n) always, STABLE, needs O(n) extra space.
HeapsortO(n log n), in-place, not stable — sort via a heap.
Counting / radixO(n) for integers/keys in a small fixed range — not comparison-based.