Premium

Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an `O(n)` operation. So why do textbooks still call append `O(1)`? Because amortized over a long sequence of appends, the rare expensive operation is paid for by many cheap ones. **Amortized Analysis** is the formal machinery that makes this kind of argument rigorous. This lesson teaches the three classical methods. The **aggregate method** sums the total cost of `n` operations and divides by `n` for a per-operation bound. The **accounting (banker's) method** charges each operation a fixed amount and stores credits on the data structure to pay for future expensive ones. The **potential (physicist's) method** defines a potential function `Phi` and computes amortized cost as actual cost plus the change in `Phi`. You will apply all three to dynamic array doubling, stacks with multipop, and binary counters, and see how amortized `O(1)` differs from worst-case `O(1)` and from average-case analysis. This lesson stands on the shoulders of **Big-O Notation (Upper Bound)** and **Time Complexity Analysis Techniques**. From those lessons you can already analyze a single operation; amortized analysis is what you reach for when the cost of *one* operation is misleading and the right object of study is a *sequence* of operations. Next you will move to **Recurrence Relations**, the other major analysis tool, used when an algorithm's cost is most naturally written recursively rather than as a running total.

Goldbach's conjecture has been verified for every even integer up to 4 * 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a hundred unit tests and still fail on the empty list or the input size your tests never reached. **Basic Proof Techniques** equips you with the small set of argument styles that turn intuition into certainty about correctness, complexity bounds, and data structure invariants. Direct proof chains definitions and prior facts to a claim. Proof by contradiction assumes the opposite and derives a logical impossibility, as in the irrationality of `sqrt(2)` and the `Omega(n log n)` lower bound for comparison sorts. Mathematical induction, in weak and strong forms, proves statements over the natural numbers via a base case and an inductive step, the backbone of recurrence solutions and loop invariants. Proof by contraposition swaps `P implies Q` for the equivalent `not Q implies not P`, and proof by cases breaks a claim into exhaustive subcases. This lesson builds on **Discrete Mathematics Basics**, where you met sets, propositional logic, implications, and the first taste of formal proof. Here those informal sketches become the disciplined patterns that algorithm analysis, theoretical CS, and clean engineering arguments all rely on. With proofs in hand, you have completed the foundations track and are ready to step into **Arrays & Strings** and the rest of the data structures curriculum, armed to analyze every operation rigorously.

Some problems have algorithms that finish in seconds on inputs of size a million. Others, like finding the shortest tour through 30 cities, can defeat the world's fastest computers no matter how cleverly you code. The boundary between these two worlds is studied formally in **complexity theory**, and the rough map of that boundary is given by **complexity classes**: `P`, `NP`, `NP-Complete`, and `NP-Hard`. This lesson introduces those classes conceptually. You will see how `P` collects problems solvable in polynomial time, how `NP` collects problems whose solutions can be *verified* in polynomial time (even if finding them might be slow), and how `NP-Complete` and `NP-Hard` capture the hardest problems in `NP` and beyond. You will meet famous examples (Traveling Salesman, SAT, the knapsack problem), get a light introduction to **polynomial-time reductions** as the tool used to prove a new problem is `NP-Complete`, and confront the legendary `P vs NP` question along with why it matters for cryptography and the entire structure of computer science. This lesson assumes you are fluent with all the basic asymptotic machinery from **Asymptotic Analysis Fundamentals**, **Big-O Notation (Upper Bound)**, **Time Complexity Analysis Techniques**, **Space Complexity Fundamentals**, and **Little-o and Little-omega Notations**. Complexity classes use those same growth-rate ideas to draw lines between "polynomial" and "exponential" rather than between specific functions like `n^2` and `n log n`. From here you will move into **Amortized Analysis**, shifting from broad problem classification back to the fine-grained per-operation analysis that complex data structures demand.

When a paper claims an algorithm runs in `O(n^2)`, that statement leaves a question wide open: does the algorithm *actually* take quadratic time, or could the bound be loose? **Little-o** and **little-omega** are the notations that close that gap. `f(n) = o(g(n))` says `f` grows *strictly* slower than `g`, never matching its rate, and `f(n) = omega(g(n))` says `f` grows strictly faster. They are the precision tools of theoretical CS. This lesson defines both notations using the formal limit-based criterion: `f(n) = o(g(n))` iff `lim f(n)/g(n) = 0`, and `f(n) = omega(g(n))` iff `lim f(n)/g(n) = infinity`. You will prove and disprove `o` and `omega` claims for common function pairs (`n` vs `n^2`, `log n` vs `n`, `n` vs `n log n`, `2^n` vs `n^k`), use these notations to rank growth rates strictly, and see how the full five-notation system fits together: `O` and `Omega` allow equality, `Theta` requires it, while `o` and `omega` forbid it. This lesson builds on three earlier asymptotic foundations. From **Big-O Notation (Upper Bound)** you have non-strict ceilings; from **Big-Omega Notation (Lower Bound)** you have non-strict floors; and from **Big-Theta Notation (Tight Bound)** you have the exact-rate case. Little-o and little-omega simply require the inequality to be strict, ruling out the matching case that Big-O and Big-Omega permit. With all five notations under your belt, you will be ready for **Complexity Classes (Conceptual Overview)**, where these comparisons get used to separate classes like `P` and `NP`.

Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo `10^9 + 7`", and you will find the same machinery underneath: **modular arithmetic**, the math of working with remainders rather than full integers. It is the bridge between number theory and a huge swath of real algorithms. This lesson develops that machinery from first principles. You will revisit the `mod` operation precisely (including its relationship to division and remainders), then prove and use the addition, subtraction, and multiplication rules that let you take `mod` at every step of a long calculation without changing the answer. From there you will implement **fast modular exponentiation** in `O(log n)` time using binary exponentiation, compute **modular inverses** with **Fermat's Little Theorem** when the modulus is prime, and see exactly why hash tables, RSA, and contest problems rely on these tricks to avoid overflow and to invert multiplications. This lesson builds on **Number Theory Fundamentals**, where you learned about primes, divisibility, `gcd`, and the Euclidean algorithm. Modular arithmetic uses all of those: primality lets you apply Fermat, `gcd` decides when an inverse exists, and divisibility underlies every congruence. From here the only foundations topic remaining is **Basic Proof Techniques**, where you will learn the proof tools (induction, contradiction, contraposition) that make the kinds of arguments you have just been waving at fully rigorous.

When you stare at merge sort or binary search, the running time is not naturally a simple sum like `n^2/2 + n/2`. It is something more interesting: the cost of a problem of size `n` is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a **recurrence relation**, an equation of the form `T(n) = ...` written in terms of `T` on smaller inputs. This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their `T(n)` equations: factorial gives `T(n) = T(n-1) + 1`, binary search gives `T(n) = T(n/2) + 1`, merge sort gives `T(n) = 2 T(n/2) + n`, and naive Fibonacci gives `T(n) = T(n-1) + T(n-2) + 1`. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces. This lesson builds on **Big-O Notation (Upper Bound)**, which gave you the language for expressing complexity, and on **Mathematical Sequences**, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded. Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, **Solving Recurrence Relations**.

Writing the recurrence `T(n) = 2 T(n/2) + n` for merge sort is the easy part. Turning it into the closed-form `O(n log n)` is where the real algorithm analysis happens, and it is exactly what this lesson is for. **Solving Recurrence Relations** gives you a small toolkit that, used well, can analyze nearly every recursive algorithm you will meet in interviews, papers, or production. This lesson walks through five methods. The **Substitution Method** has you guess the solution and prove it by induction, useful when you already suspect the bound. The **Recursion Tree Method** visualizes work level by level and sums it; this is how you see why merge sort spends `n` work per level over `log_2(n)` levels. The **Master Theorem** mechanically solves the divide-and-conquer form `T(n) = a T(n/b) + f(n)` via three cases, and you will memorize when each case fires. The **Extended Master Theorem** patches the gap when `f(n)` includes logarithmic factors. The **Akra-Bazzi Method** generalizes to unequal subproblem sizes that the basic theorem cannot handle. You will practice picking the right tool for each recurrence rather than blindly reaching for the same one every time. This lesson directly continues **Recurrence Relations**, where you learned to write `T(n)` from recursive code, and reuses ideas from **Big-O Notation (Upper Bound)** and **Mathematical Sequences** for the underlying summation arguments. With the analysis sub-track complete, you will pivot back to advanced math in **Modular Arithmetic**, where number-theoretic tools meet algorithm design.

A modern hard drive reads about 100 MB per second sequentially, but a single random seek still costs around 10 milliseconds; that gap is roughly seven orders of magnitude. A binary tree of a billion keys has 30 levels, which means 30 random seeks per lookup. **B-Trees and B+ Trees** keep each node fat enough to fill a disk page, branch into hundreds of children, and answer the same lookup in three or four seeks. That is why every relational database you have used relies on this family for its indexes. This lesson covers the B-Tree minimum-degree parameter `t` and the resulting key-and-child counts at every node, the proactive split during insert that keeps the height bounded by `O(log_t n)`, the merge-or-redistribute logic for delete, and the B+ Tree refinement that pushes all data to the leaf level and links those leaves together so range queries become a sequential scan after a single descent. In **Binary Search Tree (BST)**, every node held a single key and at most two children; that geometry is fine for memory but disastrous for disk because each comparison forces a separate I/O. B-Trees flip the design: keep every node wide so a single I/O resolves many comparisons at once. Next, **Splay Tree** explores a third self-balancing strategy in which the tree reshapes itself around access patterns rather than maintaining strict structural invariants.

Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with `O(n)` search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a **Balanced BST** does. AVL and Red-Black trees are the two most influential designs in this family. This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict `|bf| <= 1` invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ `std::map` and Java `TreeMap`, and analyze the height bound (`<= 2 log n`) that gives both their worst-case `O(log n)` guarantee. In **Binary Search Tree (BST)**, you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting `O(n)` worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant. Next, **B-Trees and B+ Trees** generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A **Circular Linked List** encodes that shape directly, with the last node's `next` pointer wired to the head instead of `null`. This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for `null`), insertion at the head and at the tail in `O(1)` when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal. In **Linked Lists (Singly)**, traversal terminated when you reached a `null` next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later). With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a **Fenwick Tree** (also called a Binary Indexed Tree, or BIT) is the right answer. This lesson covers the dynamic prefix-sum problem (static prefix sums are `O(1)` query and `O(n)` update; you want both in `O(log n)`), the `i & -i` lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in `O(log n)`, and the `prefix(R) - prefix(L-1)` identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting `O(log n)` range updates with `O(log n)` point queries. In **Arrays & Strings**, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. **Segment Tree** solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice. Next, **Sparse Table** addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with `O(1)` queries when no updates are involved.

Python's `dict` uses open addressing with a Robin Hood-inspired probe. Java's `HashMap` switches a bucket from a linked list to a red-black tree once chain length crosses eight. C++ `std::unordered_map` is required by the standard to use chaining. Three production hash tables, three different choices, all defending the same goal: keep expected `O(1)` lookups even as the table fills up. **Hash Table (Advanced)** unpacks the engineering decisions behind those choices. This lesson covers hash function design (division method, multiplication method, universal hashing), the two collision-resolution families (separate chaining and open addressing with linear, quadratic, or double hashing), the load-factor threshold that triggers a rehash, and the amortized `O(1)` cost of dynamic resizing. You will also see how tombstones make deletion correct under open addressing, and why Robin Hood and cuckoo hashing tame worst-case probe lengths. In **Hash Map (Dictionary) Basics**, you used a hash map as a black box; this lesson opens the box and replaces the hand-wave with a quantitative model. **Modular Arithmetic** is the workhorse behind every practical hash function: the `key % m` step that turns an arbitrary integer into a valid bucket index, and the `(h(k) + i*step) % m` formula behind double hashing. Next, **Skip List** answers the same fast-lookup question with a probabilistic, pointer-based design that has no hash function at all and no rehashing step.

Pull the next task in priority order from a stream of millions, and a sorted array gives you `O(1)` extract but `O(n)` insert; a sorted linked list flips the costs but stays linear; a balanced BST hits `O(log n)` for both but with substantial pointer overhead. A **Heap** quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root. This lesson covers the heap property, the parent-and-child index formulas (`parent = (i-1)/2`, `left = 2i+1`, `right = 2i+2`) that let array indices encode tree structure with no pointers, sift-up and sift-down for `O(log n)` insert and extract, and the linear-time `heapify` build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim. In **Trees: Binary Tree Fundamentals**, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. **Arrays & Strings** is what makes the implicit storage cheap: a flat array gives `O(1)` parent and child access through arithmetic, with no allocations per node. Next, **Binary Search Tree (BST)** trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.

Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both `get(key)` and `put(key, value)` in `O(1)`. No single primitive does that: a hash map gives `O(1)` lookup but no recency order, and a doubly linked list gives `O(1)` recency moves but no key index. The classical **LRU Cache** wires the two together so each compensates for what the other lacks. This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace `get` and `put` through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs. In **Hash Map (Dictionary) Basics**, you used a hash map for `O(1)` lookup by key. **Doubly Linked List** added the `prev` pointer that makes mid-list deletion `O(1)` once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here. The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Range minimum queries on a fixed array do not need updates, so the segment tree's `O(log n)` query is leaving performance on the table. A **Sparse Table** flattens the query down to genuine `O(1)`: precompute the minimum of every power-of-2 length window, and any range `[L, R]` can be answered by combining two such windows that together cover it, exploiting the fact that `min(min(A), min(B)) = min(A union B)` when the windows overlap. This lesson covers the `O(n log n)` preprocessing that fills a 2D table indexed by `(start, log2_length)`, the `O(1)` query trick for idempotent operations such as min, max, GCD, and bitwise OR, the `log2_floor` precomputation that makes every query branch-free, and the slower `O(log n)` query needed when the operation is not idempotent (like sum). You will see why this structure is the right tool for the Range Minimum Query (RMQ) problem and an essential building block in algorithms like Lowest Common Ancestor in `O(1)` per query. In **Arrays & Strings**, a flat array stored values; here the same shape stores precomputed answers indexed by a length exponent. **Logarithms & Exponentiation** is what makes the geometry work: power-of-two windows tile the index space the way binary representations tile integers, and the `O(1)` query depends on `floor(log2(length))`. With Sparse Tables in your toolkit, the curriculum next pivots to specialized structures for strings, immutability, and bounded integer universes.

Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A **Splay Tree** turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay `O(1)` after the first hit. This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields `O(log n)` per operation across any sequence of `m` operations even though individual operations can be `O(n)` in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition. In **Binary Search Tree (BST)**, accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere. Next, **Treap (Randomized BST)** keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.

Genome alignment tools like BWA and Bowtie find a 100-character read inside a 3-billion-base human reference in milliseconds, not by scanning the genome but by querying an index built once over all of its suffixes. **Suffix Array / Suffix Tree** is the family of data structures behind that workflow, and the same machinery powers full-text search, plagiarism detection, and the BWT-based compression in bzip2. This lesson covers the suffix array (a sorted array of starting positions of every suffix), the binary-search pattern match in `O(m log n)` for a pattern of length `m`, the LCP (Longest Common Prefix) array that captures shared prefixes between adjacent sorted suffixes, and the suite of substring problems the pair solves: longest repeated substring, number of distinct substrings, and longest common substring. You will also meet the suffix tree, a compressed trie of all suffixes that pushes pattern matching down to `O(m)` independent of text length, and weigh the suffix array's smaller memory footprint against the suffix tree's faster query. In **Arrays & Strings**, sorting and binary search worked over numbers; here the same primitives extend to strings, with a comparator that compares characters position by position. **Trie (Prefix Tree)** introduced the prefix-matching tree shape, and a suffix tree is a compressed trie built from every suffix of the input. Next, the curriculum explores data structures organized around a different axis entirely: preserving every historical version of themselves through time.

Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A **Treap** reaches the same expected `O(log n)` height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once. This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected `O(log n)` height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: `split(key)` cuts the treap into 'less than' and 'greater or equal' pieces, and `merge` glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting `O(log n)` insert-at-index and slicing. In **Binary Search Tree (BST)**, you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots. With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.

Type the letters `a-p-p` into a search box and the autocomplete dropdown produces `apple`, `application`, `apply`, and `appoint` before you finish the next keystroke. The data structure doing that work is a **Trie** (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once. This lesson covers the trie node layout (a `children` map plus an `isEndOfWord` flag), `insert`, `search`, and `startsWith` operations that all run in `O(m)` for a query of length `m` (independent of how many words the trie holds), and a `delete` that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit). In **Hash Map (Dictionary) Basics**, you used hashing to answer 'have I seen this exact key' in `O(1)`; a trie answers a strictly richer question (any prefix lookup) by trading `O(1)` exact-match for `O(m)` traversal. **Trees: Binary Tree Fundamentals** introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol. With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.

Given a million pairwise 'these two accounts belong to the same person' relations, decide whether two arbitrary accounts are now equivalent. Brute-force flood fills are `O(n)` per query; sorting is the wrong shape entirely. **Union-Find** answers each query in nearly `O(1)` amortized time after the relations are merged, with two primitives and a parent array. This lesson covers the disjoint-set abstraction, the `find` operation that walks parent pointers up to a representative, the `union` operation that links two representatives, and the two optimizations (path compression during `find` and union by rank during `union`) that together push the amortized cost to `O(alpha(n))`, where `alpha` is the inverse Ackermann function (effectively constant for any input you can fit in memory). You will trace the parent array as merges happen, and apply the structure to cycle detection in undirected graphs, connected components, equivalence classes, and Kruskal's minimum spanning tree. In **Arrays & Strings**, you saw that an array can encode a mapping from index to value in `O(1)`; a parent array is exactly that mapping, applied to representative pointers. **Graphs: Representation Basics** gave you the vertex-and-edge vocabulary that Union-Find uses to define connectivity, even though the structure itself stores no edges directly. With Union-Find in your toolkit, the curriculum continues with composite designs that combine multiple primitives, starting with the LRU cache pattern.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you actually care about (the shortest, cheapest, or fastest route), which is exactly the gap a **Weighted Graph** representation closes by attaching a number to every edge. This lesson covers three representations: a weighted adjacency list backed by arrays of `{node, weight}` pairs, a weighted adjacency matrix where `matrix[u][v]` is the edge cost (and infinity for non-edges), and a weighted edge list that stores `(u, v, weight)` triples. You will analyze the space and time trade-offs, see why Dijkstra wants the adjacency list, why Floyd-Warshall wants the matrix, and why Kruskal wants the edge list, and you will represent both directed and undirected weighted graphs correctly in each format. In **Graphs: Representation Basics**, you stored connectivity (whether an edge exists) using the same three shapes; the weighted version simply replaces a boolean or membership check with a numeric value. **Hash Map (Dictionary) Basics** is what makes the adjacency list work: a vertex maps to its neighbor-and-weight list in expected `O(1)`, the same way the unweighted version did. With weights in the picture, the algorithms track unlocks shortest-path and minimum-spanning-tree algorithms that read the weight on every edge during their core inner loop.

Iterating over all subsets of every subset of an `n`-element set sounds like `4^n` work. The actual cost is `3^n`: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution. **Advanced Bit Manipulation** collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the `for (s = mask; s > 0; s = (s - 1) & mask)` template, and master bit tricks like isolating the lowest set bit with `x & -x`, turning it off with `x & (x - 1)`, counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling. In **Bit Manipulation (Intro)**, you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium. Next, **Complexity & Proof Intuition (Optional)** revisits the theoretical foundations behind everything built so far.

Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A* with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand. Both algorithms use the same priority-queue framework; the only difference is that A* adds a heuristic estimate to the cost function and biases the search toward the goal. That single addition is what powers GPS, game-pathfinding, and motion planning in robotics. **Advanced Search Algorithms** covers the search refinements that go beyond plain BFS and DFS. You will implement A* with the `f(n) = g(n) + h(n)` cost function, derive what makes a heuristic admissible, and prove the optimality guarantee under admissibility. Bidirectional search runs BFS from both source and target until the frontiers meet, cutting `O(b^d)` to `O(b^(d/2))`. Iterative Deepening DFS combines BFS-style completeness with DFS-style `O(d)` memory, using repeated depth-limited DFS. The lesson finishes with two specialized array searches: Jump search at `O(sqrt(n))` for sorted arrays where binary search is awkward, and interpolation search at `O(log log n)` expected for uniformly distributed keys. In **BFS & DFS (Intro)**, you wrote the basic skeletons. **Graph Algorithms (Core)** introduced Dijkstra's priority-queue relaxation, which A* generalizes by adding the heuristic. Next, **Game Theory** turns to two-player adversarial search.

Finding the lowest common ancestor of two nodes by walking up parent pointers is `O(n)` per query, fine if you ask once but ruinous if you ask a million times on a tree of a million nodes. Binary Lifting precomputes the `2^k`-th ancestor of every node in `O(n log n)` total, then answers LCA in `O(log n)` per query. The same compute-once-then-query-fast pattern unlocks an entire family of advanced tree algorithms. **Advanced Tree Algorithms** covers that family. You will implement LCA via Binary Lifting and via the Euler Tour plus Range Minimum Query approach, where flattening the tree turns subtree queries into array-range queries. Heavy-Light Decomposition splits the tree into chains so path queries become `O(log^2 n)` segment-tree operations. Centroid Decomposition splits a tree of `n` nodes into `O(log n)` layers and powers distance and path-counting queries. The lesson finishes with the rerooting technique for tree DP, which computes DP results for every choice of root in linear total time instead of the naive `O(n^2)`. In **Tree Algorithms**, you mastered recursion-based tree problems and BST operations. This lesson trades simple recursion for preprocessing-and-query structures on top of the tree. Next, **Advanced Search Algorithms** revisits BFS and DFS with heuristic refinements.

Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the approximation ratio, is the difference between a heuristic that might be terrible and an algorithm with a written contract about how far from optimal its answer can be. **Approximation Algorithms** introduces that contract-based view of NP-hard optimization. You will define approximation ratio formally and walk through the classic constant-factor algorithms: a 2-approximation for Vertex Cover via greedy maximal matching, an `O(log n)`-approximation for Set Cover via greedy element-counting, and a 2-approximation for Metric TSP that exploits the triangle inequality on top of an MST. The lesson then covers approximation schemes (PTAS, polynomial in `n` for any fixed `epsilon`; FPTAS, polynomial in both), with Knapsack FPTAS as the canonical example. Throughout, the lesson contrasts approximation algorithms with heuristics, where heuristics give no guarantee at all. In **Greedy (Intro)**, you saw simple greedy strategies and their correctness proofs. **Dynamic Programming (Advanced)** introduced 0/1 Knapsack as an NP-hard exact algorithm. This lesson asks the next question: when exact is too slow, how close to optimal can we provably get? Next, **Advanced Bit Manipulation** turns to bit-level tricks for `O(1)` and bitmask-DP solutions.

Standard binary search returns an arbitrary index of a target if duplicates exist, but real problems usually want the _first_ such index, the _last_ such index, or the smallest capacity that ships every package within `D` days. Each variation needs a slightly different loop condition and return value, and getting one wrong produces an off-by-one bug or an infinite loop. **Binary Search Templates** turns those variations into a small set of memorable templates. You will work through first and last occurrence with `<=` versus `<` loop conditions, lower bound and upper bound (the templates behind Python's `bisect_left` and `bisect_right`), binary search on the answer space (the "minimize the maximum" pattern that solves Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum), and search in rotated sorted arrays where the invariant holds for exactly one half at each step. In **Binary Search (Intro)**, you wrote the canonical exact-match loop and learned why it is `O(log n)`. This lesson keeps the halving idea but switches the question from "is `target` here?" to "what is the smallest index that satisfies a monotonic predicate?". Next, **Linked List Algorithms** turns to pointer manipulation patterns.

Given an array where every element appears twice except one, find the loner. The hash-map solution is `O(n)` time and `O(n)` space. XOR-ing every element together solves it in `O(n)` time and `O(1)` space, in three lines, exploiting the fact that `a ^ a = 0` and `a ^ 0 = a`. Knowing how integers are laid out as bits unlocks solutions like that across an entire family of problems. **Bit Manipulation (Intro)** covers the building blocks. You will master the six bitwise operators (`&`, `|`, `^`, `~`, `<<`, `>>`) and the standard tricks: check whether `n` is a power of two with `n & (n - 1) == 0`, count set bits, get/set/clear/toggle the ith bit, and the XOR "single number" pattern. The lesson then introduces bitmasks as compact set representations and previews how subset enumeration powers later bitmask DP and TSP algorithms. In **How to Read Code (JS & Python)**, you saw integers and arithmetic. This lesson zooms in past arithmetic: the same integer is also a fixed-width string of bits you can address one at a time. Next, **Divide and Conquer (Intro)** returns to recursion with the recurrence framework that explains merge and quick sort.

0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound. **Branch and Bound** introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach. In **Backtracking (Intro)**, you walked an implicit decision tree with choose, explore, unchoose. **Greedy (Intro)** taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other. Next, **Divide and Conquer (Advanced)** turns to algebraic D&C tricks like Karatsuba and Strassen.

Comparison-based sorting cannot do better than `O(n log n)`. That is not a statement about merge sort or quick sort or any specific algorithm; it is a statement about every possible algorithm in this model, including ones nobody has invented yet. The proof is a counting argument over decision trees, and learning to read it changes how you reason about algorithmic limits forever. Lower bounds, NP-completeness, P versus NP, and loop invariants all live in the same theoretical neighborhood. **Complexity & Proof Intuition (Optional)** is an enrichment tour of that neighborhood. You will use loop invariants to prove iterative algorithms correct, revisit amortized analysis with the potential method, work through NP-completeness via polynomial-time reductions and the Cook-Levin theorem, examine the P vs. NP question and its implications, derive the `Omega(n log n)` comparison-sorting lower bound via decision trees, and meet the broader complexity zoo (co-NP, PSPACE, EXP). This lesson rests on three earlier ideas. **Asymptotic Analysis Fundamentals** gave you the language of growth rates that complexity classes refine. **Dynamic Programming (Intro)** and **Greedy (Intro)** showed you exact polynomial-time algorithms; this lesson asks which problems will never have one. This concludes the algorithms track. From here, the natural next step is sustained problem solving on hard interview problems and competitive programming contests that exercise the full toolkit you have built.

The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment intersection, and point-in-polygon tests all reduce to a sequence of cross-product evaluations with a careful eye on edge cases. Get the geometric primitive right and the rest of the field follows. **Computational Geometry** introduces those primitives and the algorithms built on them. You will start with cross products and the orientation test, then implement convex-hull algorithms three ways: Graham scan in `O(n log n)` (sort by polar angle, maintain a stack with the orientation invariant), Jarvis march in `O(nh)` for hulls with few vertices, and Andrew's monotone chain. The lesson then covers line-segment intersection, the sweep-line algorithm for many segments, the closest-pair-of-points algorithm in 2D, polygon computations using the Shoelace formula, and the ray-casting point-in-polygon test. In **Sorting (Elementary)**, you learned the comparison-based sorting that drives polar-angle preprocessing. **Divide and Conquer (Advanced)** taught you the closest-pair `O(n log n)` template via the strip combine step, which reappears here. Next, **Advanced Tree Algorithms** moves from planar geometry back to hierarchical structures with Binary Lifting and centroid decomposition.

Multiplying two `n`-bit integers the way you learned in school takes `O(n^2)` digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to `O(n^1.585)`. A few years later Strassen pulled the same trick on matrix multiplication, replacing eight recursive multiplications with seven and breaking the `O(n^3)` barrier for the first time. Both algorithms are pure divide-and-conquer with cleverly engineered combine steps, and they remain the gateway to a deeper view of D&C as algebraic restructuring. **Divide and Conquer (Advanced)** walks through that view. You will derive Karatsuba multiplication and apply the Master Theorem to its `T(n) = 3T(n/2) + O(n)` recurrence. You will work through Strassen's seven-multiplication identity for `2 x 2` blocks and discuss when its higher constant factor pays off in practice. You will solve closest-pair-of-points in 2D in `O(n log n)` via the strip optimization in the combine step, and look at convex-hull computation through a divide-and-conquer lens. In **Divide and Conquer (Intro)**, you applied the Master Theorem to merge sort and quick sort. **Recursion Fundamentals** gave you the call-stack model these algorithms still inhabit. This lesson keeps the recurrence framework but engineers cleverer combine steps. Next, **Mathematical Algorithms** turns to number-theoretic computation.

Merge sort and quick sort both run in `O(n log n)`, and once you write down their recurrences (`T(n) = 2T(n/2) + O(n)` and its expected-case sibling) the same `n log n` falls out of both. That is not a coincidence: divide and conquer is a paradigm with a precise mathematical signature, and the Master Theorem reads it directly off the recurrence. **Divide and Conquer (Intro)** introduces the three-step pattern (divide, conquer, combine) and the recurrence-relation toolkit that comes with it. You will analyze merge sort and quick sort as canonical D&C algorithms, look at binary search through the same lens, walk through the divide-and-conquer maximum subarray algorithm, and meet the closest-pair-of-points problem in 1D. Along the way the lesson formalizes the Master Theorem template `T(n) = aT(n/b) + f(n)` and shows you how to read time complexity off it without solving the recurrence by hand. It also draws the line between D&C (independent subproblems) and DP (overlapping subproblems) so you can spot which paradigm fits. In **Recursion Fundamentals**, you saw recursion as one frame calling another. D&C is the case where a frame makes _multiple_ recursive calls and combines their results. Next, **Matrix Algorithms** turns to two-dimensional arrays.

Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has `m * n` cells, each filled by looking at three neighbors. That single 2D recurrence is the gateway to a much larger family: longest common subsequence, knapsack, palindrome partitioning, regex matching, and many more. **Dynamic Programming (Advanced)** is where 1D DP graduates into the rest of the field. You will work through 2D grid and string DP (unique paths, edit distance, LCS, longest common substring), the knapsack family (0/1, unbounded, subset sum, coin change), sequence DP (LIS in `O(n^2)` and the patience-sorting `O(n log n)` variant, maximum product subarray, word break), string DP (palindromic subsequence and substring, regex and wildcard matching), DP on trees (diameter, max path sum, binary tree cameras), interval DP via matrix chain multiplication, and an introduction to bitmask DP for TSP and assignment problems. In **Dynamic Programming (Intro)**, you learned to define state, transition, and base cases on linear problems. This lesson layers a second dimension onto each. Next, **Advanced DP Techniques** introduces optimization tools that push DP beyond standard tabulation.

Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.

Standard tabulation gets you `O(n^2)` DP. The Convex Hull Trick brings the same recurrence down to `O(n log n)` whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with `n = 10^5` go from too-slow to fast enough on exactly that change. A whole sub-field of DP is dedicated to these recurrence-shaped optimizations, and this lesson is your entry into it. **Advanced DP Techniques** covers four directions of post-tabulation DP. Optimization methods include the Convex Hull Trick (offline sorted-slope and online Li Chao tree), Divide and Conquer DP for monotone-split problems, and Knuth's Optimization for optimal-BST-style recurrences. Digit DP teaches you how to count numbers with properties in a range `[L, R]` by carrying a tight-constraint flag through the recursion. Advanced bitmask DP solves TSP, Hamiltonian path, and grid-tiling profile DP. Probability DP turns recurrences over expected values into clean tables, and Kadane's algorithm generalizes to circular and 2D variants. In **Dynamic Programming (Advanced)**, you mastered multi-dimensional state and transitions. This lesson asks the next question: when the table is too big or the transition too slow, how do you optimize? Next, **Graph Algorithms (Advanced)** brings similar depth to graph theory.

Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game. **Game Theory** introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique. In **Dynamic Programming (Intro)**, you learned to recurse on subproblems and cache results. **Recursion Fundamentals** gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search. Next, **Randomized Algorithms** turns to a different way of taming worst-case inputs.

Dijkstra's shortest-path algorithm silently assumes every edge weight is non-negative. Hand it a graph with one negative edge and it can produce a wrong answer with full confidence, because the greedy choice that drives the algorithm no longer reflects the true cost. Real graphs (financial arbitrage detection, currency exchange, time-aware routing) routinely contain negative edges, and that single gap motivates an entire second wave of graph algorithms. **Graph Algorithms (Advanced)** covers that wave. Minimum-spanning-tree algorithms include Kruskal's (sort edges and union components) and Prim's (grow a tree using a priority queue), along with the cut property that explains why both produce the same minimum weight. Shortest paths gain Bellman-Ford for negative edges and negative-cycle detection, plus Floyd-Warshall for all-pairs shortest paths in `O(V^3)`. Strongly connected components are tackled by Kosaraju's (two DFS passes) and Tarjan's (single DFS with low-link values). The lesson also covers articulation points, bridges, Euler paths and circuits via Hierholzer's algorithm, and a first conceptual look at NP-complete Hamiltonian paths. In **Graph Algorithms (Core)**, you implemented Dijkstra, topological sort, and cycle detection. **Union-Find (Disjoint Set Union)** gave you the near-constant-time merge-and-query primitive that makes Kruskal's MST run in `O(E log E)`. From here, **Advanced Graph Algorithms (Network Flow)** turns to capacity-constrained optimization on directed graphs.

Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph algorithms power an enormous slice of real infrastructure, and almost all of them are short additions to a BFS or DFS skeleton you already wrote. **Graph Algorithms (Core)** covers that handful in detail. You will implement topological sort in two ways (Kahn's BFS-with-in-degree algorithm and the DFS-reverse-postorder algorithm), cycle detection on undirected graphs (DFS with parent tracking) and on directed graphs (DFS with white/gray/black coloring), Dijkstra's shortest-path algorithm with a min-heap and the relaxation invariant that makes it work, connected-component counting via DFS or Union-Find, and bipartite checking via two-color BFS. Along the way you will see why Dijkstra fails on negative edge weights, which motivates Bellman-Ford in the advanced lesson later. In **BFS & DFS (Intro)**, you wrote the two traversal skeletons. **Weighted Graph Representation** gave you the adjacency-list-of-tuples format that Dijkstra and friends actually consume. This lesson is where those primitives turn into named algorithms with clear use cases. From here, **Greedy (Intro)** introduces a different paradigm: instead of exploring every option, commit to the locally best choice at each step.

"For each element in the array, find the next greater element" is a brute-force `O(n^2)` problem until you notice that a stack maintained in decreasing order lets you answer every query as a side effect of a single left-to-right scan. The whole algorithm runs in `O(n)`, and the same monotonic-stack pattern solves trapping rain water, largest rectangle in a histogram, stock spans, and a long tail of related problems with the same template. **Advanced Greedy & Data Structures** is where greedy thinking meets specialized scaffolding. You will implement the monotonic stack pattern for next-greater and next-smaller variants, the monotonic deque for sliding-window maximum and minimum (also a key DP optimization), and sweep-line algorithms for interval and event problems (meeting rooms, interval merge, rectangle area union). The lesson closes with advanced greedy problems that need a heap or priority queue: full Huffman encoding, task scheduling with cooldown, the gas station problem, and activity selection with deadlines and profits. In **Greedy (Intro)**, you saw simple greedy strategies that needed only sorting. **Heaps & Priority Queue** taught you `O(log n)` access to the minimum or maximum, which is exactly what these advanced greedy patterns rely on for their efficiency. Next, **Branch and Bound** extends backtracking with the same kind of bounding-function pruning, applied to optimization search trees.

Given coin denominations of 1, 5, and 25, the greedy "take the largest coin that fits" strategy gives change optimally. Add a coin worth 10 to the system and greedy stays optimal. Replace 25 with 21 and greedy quietly breaks: making 63 cents now wants three 21s, but greedy says one 21 plus two 1s and ten more 1s. The same algorithm, the same input shape, and yet correctness depends entirely on a structural property of the problem. **Greedy (Intro)** explains exactly which property that is. You will learn to test for the greedy-choice property and optimal substructure, the twin ingredients that justify a greedy decision. The lesson covers the canonical problems where greedy provably works (activity selection by earliest end time, fractional knapsack by value-to-weight ratio, job scheduling with deadlines, the jump game, Huffman encoding) and walks through the exchange-argument style of correctness proof. It also shows where greedy fails (0/1 knapsack, coin change with arbitrary denominations) so you know when to reach for DP instead. In **Sorting (Elementary)**, you saw why sorting often costs `O(n log n)`; almost every greedy algorithm starts with a sort step. **Big-O Notation (Upper Bound)** gave you the language to express that cost. Next, **Dynamic Programming (Intro)** picks up where greedy fails, when the local optimum does not guarantee the global one.

Reversing a singly linked list is a four-line iteration with three pointers (`prev`, `curr`, `next`), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no random access: every operation has to be expressed as careful, ordered pointer rewrites, and one missed assignment loses the rest of the list forever. **Linked List Algorithms** is the lesson where pointer manipulation becomes a reliable skill. You will reverse a list iteratively and recursively, then extend the technique to reverse in groups of `k`. You will use Floyd's fast and slow pointers to detect cycles, find the cycle start, locate the middle element, and check whether a list is a palindrome. You will merge two sorted lists, then merge `k` sorted lists with a min-heap. The lesson also covers removing the nth node from the end, finding the intersection of two lists, deep-copying a list with random pointers, and the dummy-node trick that eliminates head-edge cases entirely. In **Linked Lists (Singly)**, you saw how nodes and `next` pointers form a list and why insertion at a known position is `O(1)`. **Two Pointers (Intro)** introduced fast and slow indices on arrays; this lesson reuses the same idea on pointer-linked nodes. Next, **Tree Algorithms** generalizes pointer-and-recursion thinking to branching structures.

Computing `a^b mod m` for `a = 7`, `b = 10^18`, and `m = 10^9 + 7` looks impossible: even iterating one multiplication per step would take longer than the age of the universe. Binary exponentiation does it in 60 multiplications, by squaring the base while halving the exponent. RSA encryption depends on exactly this trick, and so do most modular-arithmetic problems in competitive programming. **Mathematical Algorithms** assembles the standard toolkit. You will implement the Sieve of Eratosthenes for primes up to `N` in `O(N log log N)`, plus the segmented sieve for large ranges. Binary exponentiation handles `a^b mod m` in `O(log b)`, and the matrix-exponentiation generalization computes Fibonacci or any linear recurrence in `O(log n)`. You will derive the Extended Euclidean algorithm for `ax + by = gcd(a, b)` and use it for modular inverses, walk through the Chinese Remainder Theorem, compute Euler's totient, apply Fermat's Little Theorem to modular inversion, and run the Miller-Rabin probabilistic primality test. In **Number Theory Fundamentals**, you saw GCD, primes, and divisibility. **Modular Arithmetic** introduced congruences and modular inverses. This lesson turns those facts into algorithms that scale to numbers the problem statement actually asks about. Next, **Computational Geometry** turns to algorithmic problems on points, lines, and polygons.

Rotating an `n x n` image 90 degrees clockwise sounds like it needs a second matrix to hold the output. The standard trick is two passes over the same matrix: transpose it (swap rows and columns), then reverse each row, and the rotation appears in place with no extra memory. Almost every matrix interview problem hides a similar two-step decomposition under what looks like a hard spatial puzzle. **Matrix Algorithms** trains those decompositions. You will implement spiral, diagonal, snake, and anti-diagonal traversals by managing the four boundary indices that change as the walk continues. You will rotate by 90, 180, and 270 degrees in place. You will search sorted matrices three ways: per-row binary search, the staircase search that runs in `O(m + n)` on row-and-column-sorted matrices, and a single binary search when the whole matrix is sorted. The lesson finishes with in-place transformations like "set matrix zeroes" and Conway's Game of Life that encode state inside the matrix itself. In **Matrix/Grid Fundamentals**, you learned how 2D arrays are laid out and indexed. **Iteration Patterns on Arrays/Strings** taught you single and nested loops in 1D; matrix algorithms layer those patterns across rows and columns with careful boundary management. From here, **Dynamic Programming (Advanced)** revisits 2D structures, this time as DP tables.

Two seemingly different problems, the maximum amount of water you can push from a source to a sink through a network of capacitated pipes, and the minimum total capacity you must remove to disconnect the sink from the source, turn out to have the same answer for every graph. The max-flow min-cut theorem ties them together, and once you accept it a surprising number of optimization problems (image segmentation, project selection, bipartite matching) collapse into max-flow instances. **Advanced Graph Algorithms (Network Flow)** introduces the algorithms that compute that maximum flow. You will work through the Ford-Fulkerson method built on augmenting paths and the residual graph, the BFS-based Edmonds-Karp variant with its `O(V * E^2)` guarantee, and Dinic's algorithm which uses level graphs and blocking flows to reach `O(V^2 * E)`. The lesson then turns to maximum bipartite matching (Hungarian and Hopcroft-Karp), applications like airline scheduling and image segmentation, and a first look at minimum-cost flow. In **Graph Algorithms (Advanced)**, you handled MST, all-pairs shortest paths, and SCCs on edge-weighted graphs. Network flow keeps the weighted-edge model but flips the question from "shortest" to "highest throughput." Next, **String Algorithms** turns to pattern matching, the implicit automaton of a regular expression.

Boyer-Moore is the algorithm `grep` actually uses, and it has a counterintuitive property: longer patterns make it _faster_, not slower, because the bad-character rule lets it skip whole chunks of the text without inspecting them. The best case is `O(n / m)`, sublinear in the text length. The same insight (start from the right, jump aggressively on mismatch) defines a different family of pattern-matching algorithms from the linear-scan family of KMP and Z. **Pattern Matching Algorithms** rounds out the string-search toolkit. You will implement Boyer-Moore with both the bad-character rule and the good-suffix rule, build a deterministic finite automaton (DFA) from a pattern and use the resulting state-transition table for `O(n)` matching after `O(m * |alphabet|)` preprocessing, and extend pattern search into two dimensions row by row. The lesson closes with a head-to-head comparison of every string-matching algorithm you have seen so far (KMP, Z, Rabin-Karp, Manacher, Aho-Corasick, Boyer-Moore, DFA), so you can pick the right tool for any matching task: long patterns, multi-pattern, streaming, or 2D. In **String Algorithms**, you mastered the failure-function family of linear-time matchers. This lesson adds the right-to-left family and the automaton-construction family. From here, **Advanced Greedy & Data Structures** turns to monotonic stacks.

Plain quick sort with a fixed pivot is `O(n log n)` on random input but `O(n^2)` on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes `O(n log n)` _expected_ on every input, because the adversary no longer knows where the algorithm will partition. Randomization is not a hack here; it is a principled way to break the dependency between input and runtime. **Randomized Algorithms** trains that style of thinking. You will distinguish Las Vegas algorithms (always correct, randomized running time) from Monte Carlo algorithms (bounded running time, possibly wrong) and reason about expected-value guarantees. You will analyze Randomized Quick Sort to see why expected `O(n log n)` is robust against adversarial input, implement Quick Select for `O(n)` expected-time kth-element selection plus the deterministic median-of-medians variant, and walk through Reservoir Sampling Algorithm R for uniformly sampling `k` elements from a stream of unknown length, including the proof of uniformity. The lesson also revisits skip lists and treaps from the data-structures track as randomized alternatives to balanced BSTs. In **Sorting (Elementary)**, you saw worst-case-sensitive sorting. **Recursion Fundamentals** gave you the call-stack model behind quick sort and quick select. This lesson injects controlled randomness into those frameworks. Next, **Approximation Algorithms** trades exactness for polynomial time on NP-hard inputs.

When you call `arr.sort()` in Python or JavaScript, you are running Timsort, an industrial-strength hybrid that switches between merge sort for long runs and insertion sort for short ones. Sorting a billion elements in seconds is possible only because someone, decades ago, broke the `O(n^2)` ceiling that bubble sort, selection sort, and insertion sort all sit beneath. This lesson is where you learn how. **Sorting (Advanced)** covers the comparison-based `O(n log n)` algorithms (merge sort, quick sort, heap sort) and the non-comparison sorts (counting sort, radix sort, bucket sort) that beat that bound under structural assumptions about the data. For each you will trace the divide, sort, combine pattern (or its non-recursive equivalent), analyze best, average, and worst case, examine pivot strategies and partitioning schemes for quick sort, and see why heap sort runs in place. The lesson closes with the `O(n log n)` lower bound for comparison sorting and a quick tour of how built-in sorts (Timsort, V8) blend these techniques. In **Sorting (Elementary)**, you mastered the vocabulary of passes, swaps, invariants, and stability on `O(n^2)` algorithms. **Recursion Fundamentals** gave you the call-stack model that explains the `O(log n)` factor in merge and quick sort. Next, **Binary Search Templates** capitalize on sorted output to solve an entire class of medium-difficulty interview problems.

Naive substring search compares the pattern against every position in the text, restarting from scratch on each mismatch, for `O(n * m)` worst-case time. KMP, by precomputing where to resume after a mismatch, never restarts. The text pointer moves forward strictly monotonically, the pattern pointer is corrected by a failure function, and the whole search runs in `O(n + m)`. That single insight defines a family of linear-time string algorithms that power editors, search engines, and bioinformatics pipelines. **String Algorithms** covers that family. KMP teaches you to build the failure function (prefix function) and use it to skip redundant comparisons. The Z algorithm offers an alternative `O(n)` framework based on the Z-array. Rabin-Karp introduces rolling hashes for multi-pattern search and is the backbone of plagiarism detection. Manacher's algorithm finds the longest palindromic substring in linear time using a clever transform with separators. Aho-Corasick generalizes KMP to multiple patterns simultaneously by adding failure links to a trie, producing a finite automaton that scans the text once. In **Arrays & Strings**, you treated strings as arrays of characters with `O(1)` indexed access. **Hash Map (Dictionary) Basics** gave you the `O(1)` lookup used by Rabin-Karp. This lesson layers algorithmic structure on top of those primitives. Next, **Pattern Matching Algorithms** extends the toolkit with Boyer-Moore, DFA-based matching, and 2D pattern search.

An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a particular kind of thinking: the answer for a node is almost always a function of the answers for its left and right subtrees, computed recursively, combined at the parent. **Tree Algorithms** trains that decomposition habit across a wide range of problems. You will implement BST insert, search, delete, validation, and the kth-smallest in-order trick. You will compute lowest common ancestor in both a generic binary tree and a BST. You will measure height, diameter, and width, and walk through path-sum problems, root-to-leaf enumeration, and the deceptively tricky maximum-path-sum-between-any-two-nodes. Structural operations include invert, mirror check, flatten to linked list, and serialize and deserialize. The lesson finishes with reconstructing a tree from inorder plus preorder or inorder plus postorder. In **Trees: Binary Tree Fundamentals**, you learned how nodes, children, and the four traversal orders work. **Recursion Fundamentals** gave you the call-stack mental model that every tree algorithm here relies on; tree recursion is essentially recursion with two recursive calls per frame. Next, **Graph Algorithms (Core)** removes the tree assumption (no cycles, no shared nodes) and tackles the more general traversal problems that result.