# Data Structures Algorithms
All Data Structures Algorithms notes →Practice Patterns — Full Source Catalogue 1
The complete pattern-printing drill corpus behind the Pattern Practice & Loops chapter — every triangle, pyramid, rhombus, letter-art, and name-banner function as runnable Python, grouped by shape family.
Practice Patterns — Full Source Catalogue 2
The complete pattern-printing drill corpus behind the Pattern Practice & Loops chapter — every triangle, pyramid, rhombus, letter-art, and name-banner function as runnable Python, grouped by shape family.
Practice: Math & Random
The raw practice snippets behind the Math & Random chapter — a run-and-print tour of the math module (roots, logs, trig, gcd/lcm/factorial) and the random module (uniform draws, sampling, shuffling, seeding).
Practice: itertools & functools
The raw itertools and functools practice script behind the itertools & functools chapter — one function walks permutations, combinations, product, chain, cycle/count/repeat, accumulate, compress, dropwhile/takewhile, and groupby; the other covers lru_cache memoization, reduce, partial, and wraps.
Practice: Python Algorithm Idioms
The raw sort, search, count, group, and filter-map-reduce practice functions behind the Python Algorithm Idioms chapter — five standalone drills demonstrating each pattern before the chapter contrasts hand-rolled versions against their idiomatic standard-library equivalents.
Practice: Control Flow
The runnable practice source behind the Control Flow chapter — if/elif/else and nested if, the ternary expression, match/case structural pattern matching, for and while loops with enumerate/zip/dict iteration, break/continue/pass, the loop's else clause, and nested-loop early exit.
Practice: Functions
The raw practice source behind the Functions chapter — runnable demonstrations of default/positional-only/keyword-only arguments, *args and **kwargs, lambdas, closures, decorators, and first-class function patterns, including the classic mutable-default-argument trap.
Practice: Classes & OOP
The raw practice corpus behind the Classes & OOP chapter — runnable Python covering instance vs. class attributes, classmethods/staticmethods, inheritance, super(), dunder methods, properties, dataclasses, and multiple inheritance/MRO.
Practice: Error Handling
The raw practice corpus behind the Error Handling chapter — runnable functions covering try/except basics, multiple except clauses, else/finally, raise and re-raise, custom exception hierarchies, and exception chaining.
Practice: Comprehensions
Runnable source behind the Comprehensions chapter — list, nested, dict, set, and generator-expression drills, plus the walrus operator's use inside a comprehension's filter clause.
Practice: Generators
The raw practice source behind the Generators chapter — iterator protocol, yield basics, infinite generators via itertools.islice, yield from delegation, two-way communication with send(), lazy pipelines, and a generator-vs-list memory comparison.
Practice: Built-in Functions
The raw practice snippets behind the Built-in Functions chapter — sorted()/key=, aggregate reflexes, enumerate/reversed/range/zip, map()/filter(), and the numeric/identity/type-conversion builtins — each demoed with printed output for quick reference.
Practice: Strings
The two-function practice script behind the Strings chapter — a quick-reference tour of str's built-in methods (case, search, split/join, format, slicing) and the string module's character-set constants, including the str.maketrans/translate pattern for bulk punctuation removal.
Practice: Lists
The raw practice source behind the Lists chapter — creating, accessing, growing, shrinking, iterating, counting, sorting, slicing, copying, and unpacking a Python list, as the original runnable functions grouped by operation.
Practice: Tuples
The raw practice source behind the Tuples chapter — tuple immutability, basic operations (concatenation, membership, aggregates), reversing/sorting, shallow vs. deep cloning, and packing/unpacking for multi-value returns, as runnable Python functions.
Practice: Dictionaries
The raw practice corpus behind the Dictionaries chapter — creating, reading, updating, removing, sorting, aggregating over values, iterating, copying, and unpacking dicts as keyword arguments, as runnable Python grouped by topic.
Practice Sets — Full Source Catalogue
The complete set-operations practice corpus behind the Sets chapter — creating, mutating, and iterating sets, subset/superset/disjoint checks, the full union/intersection/difference algebra, and frozensets, as runnable Python grouped by topic.
Practice: Collections Module
The raw practice source behind the Collections Module chapter — runnable demos of defaultdict, Counter, deque, and namedtuple covering initialization, grouping, counting, multiset arithmetic, queue/stack patterns, and named-field records.
Core Data Structures Practice — Full Source Catalogue
The raw practice corpus behind six Part 00 chapters — list, dict, set, tuple, the collections module (deque, Counter, defaultdict, OrderedDict, namedtuple), and heapq/bisect — as runnable Python, grouped by data-structure family instead of write order.
1 — Pattern Practice & Loops
Why 'print a pyramid of stars' is really row-to-bound translation practice — the same instinct a DP table, a matrix traversal, or any 2D grid problem later in this book needs without ever calling it out by name.
10 — Math & Random
Python's math module trades general-purpose float arithmetic for a handful of exact, integer-safe helpers, while random trades true unpredictability for a deterministic, seedable stream that only looks random. This chapter is what each module actually guarantees, where those guarantees quietly break, and the worked examples — a perfect-square check, reservoir sampling, Fisher–Yates — that lean on them.
11 — itertools & functools
How two small standard-library modules replace hand-rolled nested loops and memoization boilerplate with composable, lazy building blocks — and where reaching for the library instead of writing the loop yourself stops being free.
12 — Python Algorithm Idioms
The sort, search, count, group-by, and filter-map-reduce patterns covered elsewhere in this book, restated as a question of expression, not algorithm: given that you already know which pattern a problem wants, what's the Python-idiomatic way to write it, and which hand-rolled version is quietly hiding a bug the standard library already closed.
13 — Control Flow
Python hands you six different ways to branch or repeat — if/elif, the ternary, match/case, for, while, and the loop's own often-forgotten else clause — and none of them crash when you pick the wrong one, they just quietly hide what the code is actually deciding.
14 — Functions
How Python binds arguments, remembers enclosing scope through closures, and treats every function as a plain object — the mechanics underneath default/keyword arguments, *args/**kwargs, decorators, and the mutable-default trap that catches almost everyone once.
15 — Classes & OOP
A Python class bundles state and behavior behind one name and a small set of dunder-method hooks that make instances look and act like built-ins — this chapter is what those hooks buy you, and the two places (a mutable class attribute, an __eq__ without a matching __hash__) where the bundling quietly breaks under you.
16 — Error Handling
Exceptions are Python's mechanism for splitting 'the code that notices a failure' from 'the code that decides what to do about it' — this chapter is what that split actually guarantees, the precise rules `except`, `else`, and `finally` run under, and where a custom exception hierarchy and explicit chaining beat a bare `except:` and a silently swallowed traceback.
17 — Comprehensions
How a comprehension collapses a loop-and-append into a single expression, the exact point — nesting depth, side effects, an unreadable one-liner — where that collapse stops paying off, and the memory trade a generator expression makes to never build the whole collection at all.
18 — Generators
How yield turns a function into a resumable object that produces one value at a time instead of building the whole sequence up front, why that swap is O(1) auxiliary memory instead of O(n), and the narrow set of situations — large or infinite sequences, streaming pipelines — where that actually matters.
2 — Built-in Functions
Which built-ins earn a place as pure reflex — sorted with key=, enumerate, zip — versus the situational-but-decisive ones like ord/chr and modular pow, and why an interviewer can tell the difference from across the table.
3 — Strings
Python's str ships with a wide method surface — case folding, search, split/join, formatting, slicing — that looks like ordinary array manipulation but hands back a brand-new object every single call, and the string module's character-set constants quietly back half the input-validation code you'll ever write.
4 — Lists
How Python's list works as a dynamic array wearing friendly syntax, why an alias is not a copy and a shallow copy is not always deep enough, and the handful of methods that turn 'store some values' into the workhorse structure behind almost every problem in this book.
5 — Tuples
Why Python's tuple looks like a read-only list but is really the language's native mechanism for multi-value returns and dict/set keys, where that immutability guarantee quietly stops — the first element that's itself a list — and why 'copying' a tuple by slicing is frequently not a copy at all.
6 — Dictionaries
Python's dict is the hash table from the neighboring chapter with a full public API wrapped around it — this is a tour of that surface: creation, safe access, mutation, removal, sorting, aggregation, iteration, copying, and its second job as **kwargs.
7 — Sets
Python's set trades away order and duplicates for O(1) average membership and a small algebra of whole-collection operations — union, intersection, difference — that turns 'compare two collections' from a nested loop into one line.
8 — Collections Module
Four small, purpose-built fixes for the frictions plain dict and list leave behind: an auto-vivifying dict, a dict specialized for counting, a double-ended queue's API surface, and an immutable tuple with named fields.
9 — heapq & bisect
How heapq turns 'always know the current smallest (or largest) item' into O(log n) calls over a plain list, how negation borrows that for max-heap behavior, and how bisect turns 'where does this belong in sorted order' into O(log n) search — plus the one place insort quietly costs more than its name suggests.
10 — Bitmask DP
DP whose state is a bitmask over which of n items are already accounted for — worked through the Traveling Salesman Problem and the Assignment Problem — plus the harder skill of recognizing when a subset, not an index or a range, is the axis a problem actually needs.
11 — Tree DP
DP where the state is anchored to a tree node instead of an index, the recurrence combines children's answers in a single postorder pass, and the tree's own shape — not an explicit table — supplies the fill order, worked through diameter of a binary tree and maximum independent set on a tree, both O(n), with re-rooting named as the harder next step.
12 — Interval DP
The matrix-chain-multiplication template — range state, increasing-length fill order, every split point tried — generalized to palindrome partitioning's nested interval DP and burst balloons' burst-last reframing, closing on the O(n³) ceiling that sets this family apart from cheaper 1D DP shapes.
8 — Matrix Chain Multiplication
Matrix chain multiplication's split-point recurrence derived from a hand-computed cost blowup across three parenthesizations of the same product, dp[i][j] defined over a RANGE for the first time in this book, the fill-by-increasing-interval-length rule a row-major sweep can't satisfy, and the O(n³) table traced end to end as the template this book's interval DP chapter generalizes.
9 — Digit DP
Counting integers in a range by their digit sum, forbidden digits, or repeats without enumerating them one at a time — building N's digits left to right under a tight/bound flag that is the one genuinely new state dimension this technique adds, worked top-down with a hand trace and a complexity argument for why the cost depends on N's digit count, not N itself.
1 — Greedy Strategy
The greedy-choice property proven by exchange argument instead of assumed on faith, optimal substructure named as the property greedy shares with DP but resolves differently, a canonical coin system proven correct and an adversarial one shown to break the same proof, and 0/1 knapsack as the case where greedy must yield to DP.
2 — Interval Scheduling
Three concrete interval problems — removal, merging, and room counting — built on one recurring decision: which sort key, start, end, or duration, the greedy choice actually needs.
3 — Huffman Coding
Building a provably optimal prefix-free code by repeatedly merging the two least-frequent symbols off a min-heap — the exchange argument behind it, and where this exact construction runs inside gzip, JPEG, and MP3 today.
4 — Activity Selection
Maximizing the count of non-overlapping activities on one resource by sorting on finish time, proved optimal with the book's most rigorous exchange argument.
5 — Fractional Knapsack
Sorting items by value-to-weight ratio and greedily taking the highest-ratio items first, proven optimal by an exchange argument that only holds because items can be split into arbitrary fractions, and a concrete capacity-50 counter-example where that identical ratio-greedy strategy provably loses to 0/1 knapsack's DP the instant items become indivisible.
1 — Bitwise Operations
AND, OR, XOR, NOT, and shifts as the primitive operations every bit trick composes from — plus the Python-specific gotcha (arbitrary-precision ints) that catches people coming from C.
2 — Bit Tricks
A toolkit of small, composable bit-level idioms — power-of-two checks, isolating and clearing the lowest set bit, Kernighan's popcount, single-bit get/set/clear/toggle, and the XOR swap — each derived from two's-complement first principles, not memorized as a formula.
3 — XOR Problems
Three algebraic properties of XOR — self-inverse, identity, commutative/associative — that turn a handful of hashing-shaped problems into O(n) time, O(1) space one-liners.
4 — Bitmasking
Representing a subset as bits in a single integer — the trick that turns small-universe subset enumeration and subset-indexed DP into plain integer arithmetic, and stops working the moment the universe passes about 25 elements.
5 — Gray Code
A permutation of 0..2^n-1 where every consecutive pair — including the wrap from the last value back to the first — differs in exactly one bit, generated in O(1) per value by a single XOR, and the reason physical rotary encoders needed that guarantee before it became an interview trick.
1 — Binary Search
The iterative implementation worth having cold, the three classic bugs (overflow, boundary-convention mixing, non-shrinking updates), the leftmost/rightmost/rotated-array variants, and why Python's bisect module usually beats hand-rolling it.
10 — Selection Algorithms
Quickselect finds the k-th smallest element in expected O(n) by reusing quicksort's Lomuto partition and discarding, rather than recursing into, the side that can't contain the answer — plus median-of-medians, k-th-largest and top-k-as-a-set variants, and the heap-based streaming alternative.
2 — Binary Search on Answer
Binary searching over a monotonic answer space instead of an array — the generalization that unlocks a large class of optimization problems.
3 — Sorting Fundamentals
The four axes every sort gets judged on — stability, in-place vs. auxiliary space, adaptive vs. not, comparison-based vs. not — the Ω(n log n) comparison-sort lower bound proved by the decision-tree argument, Python's Timsort, and a trade-off preview of every algorithm the rest of this Part covers.
4 — Quick Sort
Lomuto partitioning traced step by step, a precise derivation of the O(n log n) average case and the O(n²) worst case, randomized and median-of-three pivot mitigations, and why quicksort is in-place but not stable.
5 — Merge Sort
Divide-and-conquer sort with guaranteed O(n log n) and stability, at the cost of O(n) auxiliary space.
6 — Heap Sort
In-place heap sort derived from the heap chapter's heapify and sift-down — a guaranteed O(n log n) worst case with O(1) auxiliary space, and why giving up stability and cache locality is the price of both.
7 — Counting Sort
Non-comparison sort that counts occurrences directly by value, its stable prefix-sum construction, and the O(n + k) trade-off that only pays off when the key range doesn't dwarf the input.
8 — Radix Sort
LSD radix sort processes multi-digit integers by running the previous chapter's stable counting sort once per digit, achieving O(d(n+k)) time by indexing on digits instead of comparing whole values.
9 — Bucket Sort
Non-comparison sort for real-valued, roughly uniformly distributed input — O(n + k) average case derived from expected per-bucket occupancy, an O(n²) worst case with no floor beneath it, and a stability property that depends on the whole pipeline, not the bucketing step alone.
1 — DP Fundamentals
Overlapping subproblems and optimal substructure defined precisely and shown to be independent properties, naive Fibonacci's recursion tree counted exactly with a call-counter to make the states-versus-total-calls gap numeric rather than asserted, why state definition — not the recurrence — is the actual design decision, and memoization vs. tabulation named as the two standard ways to implement any DP recurrence.
2 — Memoization
Top-down dynamic programming: caching each recursive call's answer to turn Fibonacci's O(2^n) blowup into O(n), deriving the cache's time/space cost and its recursion-depth limit, learning to define a state and its transition from scratch via Climbing Stairs, previewing tuple-keyed multi-dimensional caches, and weighing memoization against tabulation.
3 — Tabulation
Bottom-up tabulation on Fibonacci and 2D Unique Paths, the dependency-order rule that makes a fill loop valid, the rolling-array space optimization it enables, and where it beats memoization.
4 — Knapsack Problems
0/1 knapsack's two-dimensional state and transition, derived and traced on a worked table with item reconstruction, the 1D rolling-array collapse where iteration direction over capacity is the entire difference between 0/1 and unbounded knapsack, and the subset-sum / partition-equal-subset-sum problems that specialize the same transition.
5 — Longest Increasing Subsequence
The O(n²) DP with full state/transition derivation and predecessor-based reconstruction, the O(n log n) patience-sorting reformulation built directly on bisect_left, a proof sketch for why the tails array stays sorted, and when the quadratic version's easy reconstruction is worth trading away for the logarithmic version's speed.
6 — Longest Common Subsequence
Longest Common Subsequence's two-string 2D state and transition, traced on a full table for a worked example (ABCBDAB / BDCABA, LCS length 4) with backward reconstruction of the actual subsequence, the rolling-array space optimization's tension with reconstruction (Hirschberg's algorithm named, not derived), and the family of alignment problems — edit distance, longest common substring, shortest common supersequence — this same 2D shape generalizes to.
7 — Edit Distance
Edit distance's three-way insert/delete/replace transition derived directly from LCS's two-way match/skip transition, traced on a full 2D table and backward-reconstructed into an actual operation sequence, then set side by side with LCS to show precisely why replace has no LCS equivalent.
1 — What is an Algorithm?
What separates an algorithm from a program — finiteness, definiteness, effectiveness — and why interviewers are grading the precision of your procedure, not just whether your code runs.
2 — Asymptotic Analysis
Why Big-O is really shorthand for Big-Theta, how worst/average/best case turns 'what's the complexity' into three different questions, and the feasibility ladder that tells you whether a brute-force idea will even finish running.
3 — Recursion
How recursion actually executes on the call stack, why Python has no tail-call optimization, when to convert recursion to iteration, and a worked factorial-digit-sum example.
4 — Mathematical Foundations
Combinatorics, modular arithmetic, GCD/LCM, and prime sieves — the discrete-math toolkit that counting, DP, and number-theory interview problems quietly depend on.
5 — Algorithm Design Principles
A field guide to recognizing which of the five recurring design paradigms — brute force, divide and conquer, greedy, dynamic programming, backtracking — a new problem is calling for, before you write a line of implementation.
1 — Arrays
Static vs. dynamic arrays, why contiguous memory buys O(1) random access, row-major layout for multi-dimensional arrays, the complexity of every core operation, and where list, array, and numpy diverge.
2 — Array Algorithms
In-place rotation via the reversal trick, Kadane's maximum subarray, Dutch National Flag partitioning, merging sorted arrays in place, and the sum/XOR tricks for a missing or duplicate number.
3 — Two Pointers
Opposite-direction and same-direction pointer techniques for sorted arrays — Two Sum II, Container With Most Water, 3Sum, and in-place duplicate removal — plus how to tell the pattern apart from sliding window.
4 — Sliding Window
Fixed vs. variable window, when to grow or shrink, and the substring/subarray problems this technique solves in linear time.
5 — Prefix Sum & Difference Arrays
Precomputed running sums and difference arrays for O(1) range-sum queries and range-update problems.
6 — Hashing
How Python's dict/set turn an O(n) or O(n²) scan into O(1) average-case lookups, when that average case breaks down, and where hashing trades away information — order — that a problem still needs.
7 — Strings
Why treating a Python string as 'just an array of characters' is only half true — immutability turns naive concatenation quietly quadratic, and that one property shapes every string algorithm that follows.
8 — String Algorithms
Palindrome checks via two pointers and expand-around-center, anagram detection by counting vs. sorting, the naive O(n·m) substring search baseline, and why Python's string immutability turns 'reverse in place' into a trick question.
1 — Singly Linked List
Node-and-pointer structure, why there's no O(1) random access without contiguous memory, the head/tail/mid-list complexity trade-offs, and the reverse-a-list and find-the-middle worked examples every interview loop opens with.
2 — Doubly Linked List
Doubly linked list node structure, O(1) deletion given a node reference, the four-pointer relink for insert/delete, and why deque/OrderedDict are built on this.
3 — Circular Linked List
Circular linked list structure — the tail-to-head wraparound, detecting 'the end' without a None sentinel, round-robin scheduling and circular buffers, the Josephus problem, and telling deliberate circularity apart from an accidental cycle bug.
4 — Skip Lists
Probabilistic multi-level linked structure giving expected O(log n) search, insert, and delete without tree rebalancing.
5 — LRU Cache Design
Combining a hash map and a sentinel-based doubly linked list to get O(1) get/put with least-recently-used eviction — LeetCode 146, and the same shape found in real production caching layers, plus the OrderedDict version you'd actually ship.
1 — Stack
LIFO fundamentals: push/pop/peek in O(1), why list.append()/list.pop() are the right end and list.pop(0) isn't, the call stack as a literal stack, and worked bracket-matching and iterative-DFS examples.
2 — Queue
FIFO fundamentals: enqueue/dequeue, why list.pop(0) is a silent O(n) trap, collections.deque as the fix, the two-stack amortized-O(1) implementation, and BFS as the queue's signature use case.
3 — Circular Queue
Fixed-capacity ring-buffer queue that reuses freed slots without shifting elements — modulo-arithmetic wraparound over a plain array, and the full-vs-empty ambiguity every implementation has to resolve.
4 — Deque
Deque as the shared generalization behind stack and queue: O(1) push/pop at both ends via collections.deque's fixed-size-block internals (not a list, not a per-element linked list), worked rotate/maxlen/extendleft examples, and the O(n) random-access trade-off a list doesn't have to make.
5 — Monotonic Stack
A stack that enforces increasing or decreasing order at push time, solving next-greater-element, daily-temperatures, and largest-rectangle-style problems in O(n).
6 — Monotonic Queue
Sliding window maximum in O(n): a deque of indices kept decreasing by value, trimmed from the back for domination and from the front for window expiry — the second eviction rule a monotonic stack structurally can't support.
7 — Expression Evaluation
Infix vs. postfix vs. prefix notation, evaluating postfix/RPN with a single stack, the two-stack method for direct infix evaluation with operator precedence and parentheses, a full Basic-Calculator implementation, and shunting-yard as an alternative infix-to-postfix conversion strategy.
1 — Tree Fundamentals
Root, parent, child, leaf, depth vs. height, and the recursively-defined structure — general vs. binary trees, the four traversal orders, and pointer- vs. array-based representation — that every later tree chapter assumes without re-explaining.
10 — Suffix Trie
Suffix-indexed trie variant for substring and pattern-matching queries.
11 — Heap
Binary heap structure (array-backed complete tree) and the sift-up/sift-down operations behind heapify — the weaker parent-children invariant that makes find-min cheap, why completeness makes array representation waste nothing, and heapq's push/pop/heapify/heappushpop/heapreplace in practice.
12 — Priority Queue
Priority queue as an abstract interface — insert with a priority, extract the highest-priority item — and why a binary heap, not a sorted list or a balanced BST, is usually the implementation of choice; includes full top-K and k-way merge worked examples.
2 — Binary Trees
Binary tree node structure and traversal: preorder, inorder, and postorder — each recursive and iterative (postorder's two-stack trick for the trickiest case) — plus level-order BFS via a queue, recursive height/depth, and when each traversal order actually matters in practice.
3 — Binary Search Trees
The BST ordering invariant and its duplicates-go-right convention, why search/insert/delete are O(h) rather than unconditionally O(log n), why inorder traversal always yields sorted order, the three delete cases including the inorder-successor splice, why sorted-input insertion degenerates a BST into a linked list, and the range-bound fix for the classic buggy Validate BST check.
4 — AVL Trees
Height-balanced BST with rotation-based rebalancing that guarantees O(log n) operations.
5 — Red-Black Trees
Color-based self-balancing BST used by most production ordered-map implementations, and how it trades stricter balance for cheaper rebalancing.
6 — Segment Trees
Binary tree over array ranges trading prefix sum's O(1) query for O(log n) — in exchange for O(log n) point updates with no rebuild, ever.
7 — Fenwick Trees (BIT)
Binary Indexed Tree for O(log n) prefix-sum queries and point updates with a much smaller constant than a segment tree.
8 — Interval Trees
Augmented BST ordered by interval low-endpoint, storing each subtree's max high-endpoint (max_end) to prune subtrees that provably can't overlap a query — cutting overlap search from O(n) brute force to O(log n + k), and why max_end is the one field that makes the pruning possible.
9 — Trie
Prefix tree structure that makes 'does any word start with this' as cheap as exact-match lookup — insert/search/startsWith in O(L), autocomplete via DFS, and the memory trade-off against a plain hash set.
1 — Graph Representation
Adjacency matrix, adjacency list, and edge list — what a graph adds back once trees drop the acyclic, single-parent, single-root constraints, and why every graph algorithm in this Part needs a visited set that tree traversal never did.
10 — Network Flow
Ford-Fulkerson, the residual graph's backward edges, and Edmonds-Karp's BFS-driven augmenting paths for computing maximum flow through a capacitated graph — plus the max-flow min-cut theorem and why greedy augmentation needs a way to undo itself.
2 — Graph Traversal
DFS and BFS generalized from trees to graphs via one addition — a visited set — plus recursive and iterative DFS, BFS's third appearance of the same queue skeleton, connected components, and multi-source BFS as single-source BFS from an imaginary super-source.
3 — Topological Sorting
Ordering a DAG's nodes so every edge points forward — via DFS post-order or Kahn's BFS-based algorithm.
4 — Shortest Path
Shortest path is four different problems wearing one name: BFS already solves the unweighted case, Dijkstra's min-heap relaxation handles non-negative weights, Bellman-Ford and its negative-cycle check handle any sign, and Floyd-Warshall answers all-pairs — plus an honestly-scoped worked example showing exactly what Dijkstra does and doesn't solve for a k-cheapest-routes problem.
5 — Minimum Spanning Tree
Kruskal's and Prim's algorithms for the minimum-weight edge set connecting every node — why MST is a fundamentally different problem from shortest path, and how the same greedy framing from Part 01 produces two structurally different, equally correct algorithms.
6 — Union Find (Disjoint Set)
Path compression and union by rank turn find and union into O(α(n)) amortized operations — the inverse Ackermann bound stated precisely, dynamic connectivity as edges arrive one at a time, and cycle detection as a direct byproduct of union itself.
7 — Strongly Connected Components
Kosaraju's two-pass DFS algorithm for finding maximal strongly connected components in a directed graph, the finish-time argument for why it works, and Tarjan's single-pass low-link alternative.
8 — Bridges & Articulation Points
Deriving DFS discovery time and low-link values from scratch to find, in one O(V + E) pass, every edge and every vertex whose removal would disconnect an undirected graph.
9 — Eulerian & Hamiltonian Paths
Why an Eulerian path (every edge once) is checkable in O(V) by counting degrees while a Hamiltonian path (every vertex once) is NP-complete with no known shortcut — Hierholzer's algorithm, backtracking search, and why identical phrasing hides opposite tractability.
1 — Backtracking
The choose-explore-unchoose template and pruning strategies that make exhaustive search tractable.
2 — N Queens
Placing N non-attacking queens via backtracking with row/column/diagonal constraint tracking.
3 — Sudoku Solver
Constraint-propagation backtracking over a 9×9 grid with row/column/box validity checks.
4 — Permutations
Generating all orderings of a set via backtracking, including the handling of duplicate elements.
5 — Combinations
Generating all fixed-size subsets via backtracking, and its relation to subset/power-set generation.
6 — Branch & Bound
Backtracking augmented with a bounding function to prune branches that can't beat the best solution found so far.
1 — Sparse Table
O(1) range-minimum/maximum queries on a static array via O(n log n) precomputation.
2 — Treap
Randomized BST combining heap priorities with BST ordering for expected O(log n) balance without explicit rotation logic.
3 — Rope
Binary-tree-of-string-chunks structure for O(log n) concatenation/insertion on very large strings.
4 — B-Tree
Multi-way balanced tree minimizing disk reads, the structure behind most database indexes.
5 — B+ Tree
B-tree variant that pushes all values to leaf nodes with a linked list across them, optimized for range scans.
6 — Bloom Filter
Probabilistic set-membership structure with no false negatives and a tunable false-positive rate, trading certainty for O(1) space-efficient lookups.
7 — Count-Min Sketch
Probabilistic frequency-counting structure for approximate counts over massive streams in sublinear space.
8 — HyperLogLog
Probabilistic cardinality-estimation structure for counting distinct elements in a stream using near-constant space.
1 — Divide & Conquer Optimization
Speeding up a DP transition using divide-and-conquer or monotonic-decision-boundary tricks (e.g. the DC optimization, Knuth's optimization).
2 — Convex Hull
Finding the smallest convex polygon enclosing a set of points, via Graham scan or the gift-wrapping algorithm.
3 — Sweep Line
Sweeping a conceptual line across sorted events to solve interval-overlap and geometric intersection problems in O(n log n).
4 — Computational Geometry
Core geometric primitives — orientation, line intersection, point-in-polygon — that geometry problems build on.
5 — String Matching Advanced
Suffix arrays and suffix automata as the next level past KMP/Z-algorithm for heavy string-matching workloads.
6 — FFT
Fast Fourier Transform for O(n log n) polynomial multiplication, the classic application in competitive/advanced algorithm problems.
7 — Matrix Exponentiation
Representing a linear recurrence as matrix multiplication to compute the n-th term in O(log n).
8 — Fast Exponentiation
Binary exponentiation for computing a^n (or a^n mod m) in O(log n) instead of O(n).
9 — Randomized Algorithms
Algorithms that use randomness for expected-case guarantees — randomized QuickSelect, Monte Carlo vs. Las Vegas framing.
1 — Two Pointers Pattern
Recognizing when a problem's brute-force nested loop collapses to a single pass with two coordinated pointers.
10 — BFS Pattern
Recognizing shortest-path/level-order/minimum-step problems that breadth-first search solves optimally on unweighted graphs.
11 — Tree DFS Pattern
Recognizing tree problems that reduce to a DFS template carrying a small amount of state root-to-leaf.
12 — Graph Pattern
Recognizing problems phrased as text/grid/relationship data that are actually graph traversal or connectivity in disguise.
13 — Dynamic Programming Pattern
Recognizing optimal-substructure-plus-overlapping-subproblems phrasing that signals memoization or tabulation over brute force.
14 — Monotonic Stack Pattern
Recognizing next-greater/next-smaller-style problems that a monotonic stack solves in O(n).
15 — Union Find Pattern
Recognizing dynamic-connectivity and grouping problems that Union-Find solves faster than repeated traversal.
16 — Prefix Sum Pattern
Recognizing range-sum-query problems that precomputed prefix sums answer in O(1) per query.
17 — Heap Pattern
Recognizing 'k-th'/'top-k'/'median-of-stream' problems that a heap (or two heaps) solves without full sorting.
18 — Trie Pattern
Recognizing prefix-matching and autocomplete-style string problems that a trie solves faster than repeated string comparison.
2 — Sliding Window Pattern
Recognizing when a problem is secretly asking for a variable- or fixed-size window over a sequence.
3 — Fast & Slow Pointer
Recognizing cycle-detection and middle-of-sequence problems that Floyd's fast/slow pointer solves in O(1) space.
4 — Binary Search Pattern
Recognizing when a search space is monotonic enough to binary search over, even when there's no literal sorted array.
5 — Merge Intervals
Recognizing interval-overlap problems that reduce to sort-by-start-time plus a linear merge pass.
6 — Cyclic Sort
Recognizing array problems where values are bounded 1..n and can be placed at their own index in-place.
7 — Top K Elements
Recognizing 'k largest/smallest/most frequent' problems that a fixed-size heap solves in O(n log k).
8 — K-way Merge
Recognizing problems over k sorted sequences that a heap-based merge solves in O(n log k) instead of a full sort.
9 — DFS Pattern
Recognizing when exhaustive path/combination exploration is really depth-first search with backtracking.
1 — Complexity Analysis in Interviews
Stating brute-force and optimized complexity out loud, in the form interviewers actually expect to hear it.
10 — Revision Strategy & Cheat Sheets
Spaced-repetition strategy and one-page cheat sheets for keeping all 130 chapters' patterns fresh in the weeks before an interview.
2 — Choosing the Right Data Structure
A decision framework for picking the right structure from constraints alone — before writing a line of code.
3 — Whiteboard Communication
Narrating your reasoning while coding: what to say, when to pause, and how to signal thinking without going silent.
4 — Problem-Solving Framework
Clarify constraints, brute force first, identify the pattern, optimize, code, test edge cases — the repeatable loop for an unseen prompt.
5 — Optimization Techniques
Turning a working brute-force solution into an optimized one: the standard moves (memoize, precompute, change data structure) applied systematically.
6 — Handling Follow-up Questions
Anticipating and handling 'what if the input is huge/streaming/concurrent' follow-ups after the base solution is accepted.
7 — Recognizing Hidden Patterns
Cross-referencing this book's pattern list (Part XIV) against an unfamiliar prompt's phrasing to find the hidden signal fast.
8 — Mock Interview Walkthroughs
Full worked mock interviews end-to-end, showing the clarify → brute force → optimize → code → test loop in real time.
9 — Top 200 MAANG Problems Roadmap
A prioritized roadmap through the highest-frequency MAANG problems, sequenced against this book's chapter order.
Data Structures & Algorithms
A book-shaped table of contents for MAANG-interview DSA prep: Python language foundations, mathematical and algorithmic foundations, arrays/strings, linked structures, stacks/queues, trees, graphs, sorting/searching, dynamic programming, greedy algorithms, backtracking, bit manipulation, advanced data structures, advanced algorithms, interview problem patterns, and MAANG interview mastery — a book-length progression from fundamentals to Google/Meta/Amazon/Apple/Netflix/Microsoft (L4–L6) interview readiness.