Data structures and algorithms

7 lessons · 2 equations. Each lesson below gives its formulas and key rules; open the lesson for the full explanation.

Complexity: reading it off, and deriving it

The master theorem

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)

Compare $f(n)$ with $n^{\log_b a}$ : whichever dominates gives the answer, and if they match you gain a $\log n$ .

Remember

Know the four-column table for the standard structures without thinking.

Linear structures: arrays, hash maps and monotonic stacks

Key rules

Choose from the access pattern: index, key, order, or ends.
Hash maps are $O(1)$ average, $O(n)$ worst case, and need immutable keys.
A hash map trades $O(n)$ space to remove a factor of $n$ from the time.

Trees and heaps: BSTs, priority queues and range queries

The Fenwick tree’s one trick

\text{query: } i \leftarrow i - (i \,\&\, {-i}), \qquad \text{update: } i \leftarrow i + (i \,\&\, {-i})

A Fenwick (binary indexed) tree stores partial sums in a flat array. Index $i$ holds the sum of the last $i \,\&\, {-i}$ elements up to $i$ ; stripping or adding the lowest set bit walks the $O(\log n)$ nodes a prefix query or a point update needs.

Remember

A BST gives ordered operations; a hash map gives only exact lookup.

Graphs: traversal, shortest paths and union–find

Key rules

BFS for minimum hops, DFS for connectivity and ordering.
Dijkstra needs non-negative weights; Bellman–Ford handles negatives and finds negative cycles.
Negative log rates turn arbitrage into a negative-cycle problem.

Core techniques: binary search on the answer, two pointers, sliding windows

Key rules

Binary search needs a monotone predicate, not a sorted array.
"Minimum $x$ such that it works" is a binary search over the answer.
Sliding windows are linear because each index enters and leaves once.

Dynamic programming, and why it is the same as an EV recursion

Key rules

State, transition, base cases, evaluation order — in that order, out loud.
Memoisation visits only what is reachable; tabulation often reduces the space.
An expected-value recursion is a dynamic programme with probabilistic transitions.

Bit manipulation and modular arithmetic

Key rules

$x \,\&\, (x-1)$ clears the lowest set bit; $x \,\&\, -x$ isolates it.
XOR is self-inverse, so it cancels everything appearing twice.
Addition and multiplication commute with the modulus; division does not.

Detailed formula cards

The master theorem