Algorithms

You already know how to write code that works. But here is a question most beginners never ask: *does it matter how you solve it?* If two programs both give the correct answer, are they equally good? The answer, it turns out, is a decisive no -- and understanding why is the foundation of everything in this course. **Algorithms and Efficiency** is the opening lesson of the DSA Foundations track. Rather than jumping straight into notation or formulas, it starts with a simple, concrete idea: different solutions to the same problem can do very different amounts of work, and that gap in effort becomes enormous once your input is large. You will see two approaches to finding the maximum number in a list, watch the operation counts diverge as the list grows, and come away with a clear intuition for what "efficiency" means in practice. No O() notation yet -- just the honest, visual realization that some code does way more work than it needs to. This lesson bridges everything you already know about writing code to the new skill of *reasoning about* code. You can write loops, call functions, and store values in variables -- that is all you need. By the end, you will have a concrete sense of what engineers mean when they say one algorithm is "better" than another, and you will understand exactly why input size is the key variable in that judgment. Next up is **Counting Operations** (lesson 2), where you will formalize the intuition you build here by learning to count steps precisely as a function of the input size `n`. From there, the track moves into Asymptotic Analysis and Big-O Notation -- the symbolic language the entire industry uses to express these ideas.

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.

Listing every subset of a 20-element set produces over a million results, and there is no shortcut: you have to enumerate them. The trick is to do it without writing 20 nested loops. Backtracking solves the entire family of "generate all configurations" problems with a single recursive template that walks an implicit decision tree. **Backtracking (Intro)** introduces that template as the "choose, explore, unchoose" pattern. You will see how each recursive frame picks an option, recurses into the resulting state, and then undoes the choice on the way back up so the next branch starts from a clean slate. Classic problems include generating all subsets and permutations, the N-Queens placement puzzle, and a first look at Sudoku. The lesson also introduces pruning, where invalid partial solutions are cut off early so the algorithm explores far less than the full `O(2^n)` or `O(n!)` worst case. In **Recursion Fundamentals**, you learned to define a problem in terms of smaller subproblems. Backtracking adds one more idea: state mutated during recursion has to be restored before returning, so siblings in the call tree see the same starting state. From here, **BFS & DFS (Intro)** generalizes the same tree-of-states view to actual graphs.

Swap a queue for a stack inside a graph traversal and you flip from breadth-first to depth-first behavior. The visited-vertex tracking is identical, the neighbor expansion is identical, and yet one explores level by level while the other dives down the longest path first. That single data-structure swap is the entire difference between the two most-used graph algorithms in the field. **BFS & DFS (Intro)** walks through both. For BFS you will implement queue-based level-by-level exploration and use it to find shortest paths in unweighted graphs. For DFS you will see both the recursive form (which uses the call stack implicitly) and the iterative form with an explicit stack, and apply them to connectivity checks, path finding, and cycle detection. The lesson also covers the visited set that prevents infinite loops on cyclic graphs and contrasts graph traversal with tree traversal as a special case. This lesson assumes you are comfortable with three structures from the data-structures track: **Stack (LIFO)** powers iterative DFS, **Queue & Deque** powers BFS, and **Graphs: Representation Basics** gives you the adjacency list or matrix that both algorithms read from. Next, **Hashing Techniques** turns to a different building block, the hash map, which underpins many of the lookup-heavy patterns you will combine with traversal in later lessons.

Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior, separated only by the assumption that the array is sorted. **Binary Search (Intro)** explains how to get that speedup and how to write the algorithm without the off-by-one errors and infinite loops that trip up almost everyone the first time. You will implement the canonical two-pointer template with `left` and `right` indices, learn why `mid = left + (right - left) / 2` matters for avoiding integer overflow, and trace the algorithm step by step on small inputs to see the search space halve each iteration. The lesson also surveys built-in support across languages (`Array.indexOf` is _not_ a binary search; Python's `bisect` is) and the most common pitfalls. In **Arrays & Strings**, you saw why indexed access on an array is `O(1)`; binary search is the first algorithm that uses that property to skip past whole regions instead of walking through them. **Big-O Notation (Upper Bound)** gave you the language `O(log n)` and the reasoning that explains why halving leads to logarithmic growth. From here you will move into **Two Pointers (Intro)**, which generalizes the same coordinated-index idea beyond exact-match searching.

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.

Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value `x` ask whether `target - x` is already in the map. The same shape, single-pass plus complement lookup, solves "first duplicate," "contains nearby duplicate," "longest substring without repeats," and an entire family of trade-space-for-time problems. **Hashing Techniques** catalogs those patterns. You will work through frequency counting (most/least frequent element, group anagrams via sorted-key trick), the two-sum complement template and its three-sum / four-sum extensions, existence checking and duplicate detection, index mapping where you store positions alongside values, and a first conceptual look at rolling hashes that prepare you for Rabin-Karp later. The lesson also discusses when a hash map is overkill versus when it is the obviously correct tool. In **Hash Map (Dictionary) Basics**, you saw how hashing achieves expected `O(1)` insertion and lookup. This lesson is where that constant-time primitive turns into algorithmic leverage: brute-force `O(n^2)` scans collapse into a single pass that uses the map as an oracle. From here you move into the paid track with **Sorting (Advanced)**, which trades hash-map lookups for divide-and-conquer to break the `O(n^2)` sorting barrier.

Two recipes can both bake the same cake, yet one calls for thirty minutes and the other for three hours. The same is true of code: a problem like sorting a list or finding the largest number in an array has many valid solutions, and the choice between them is exactly what an algorithm captures. This lesson defines what an algorithm actually is, naming the five characteristics every algorithm shares (input, output, definiteness, finiteness, effectiveness). It separates the abstract steps of a method from the concrete code that implements it, and walks through how to judge whether a procedure is _correct_ before worrying about whether it is fast. You will also build a first informal sense of efficiency, the way work grows as inputs get bigger, without any formal notation yet. In **How to Read Code (JS & Python)**, you practiced tracing variables, loops, and function calls in two languages. **Introduction to Algorithms** zooms out from individual lines to the recipe as a whole, treating those traces as evidence that a method does what it claims. From here you will move into **Iteration Patterns on Arrays/Strings**, where these abstract ideas about correctness and efficiency get applied to concrete traversal templates.

Look at almost any solved interview problem and you will see the same six or seven shapes of `for` loop reappearing: a single sweep that finds a max, a nested pair that compares every element to every other, a single sweep that fills a frequency table. Before you can recognize when two pointers or sliding window will help, you have to recognize these primitive shapes on sight. **Iteration Patterns on Arrays/Strings** catalogs those shapes. You will work through single-pass templates (running sum, find max/min, counting), nested-loop templates that consider all pairs in `O(n^2)` time, frequency counting with a hash map, early termination with `break`, sentinel values, and the choice between in-place modification and building a new array. Classic transformations like reverse, rotate, and partition appear as named patterns rather than puzzles solved from scratch each time. In **Arrays & Strings**, you saw that arrays give you constant-time indexed access and contiguous memory. This lesson turns that storage model into actual movement: how an index walks across an array, what it costs, and when one walk is enough. Next you will use these patterns directly in **Prefix Sum & Difference Array**, where a single preprocessing pass replaces many later range-sum loops.

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.

Imagine an array of a million numbers and a thousand questions of the form "what is the sum of elements between index `l` and `r`?". The naive answer loops through each query, doing roughly a billion additions in total. Prefix sums turn the same workload into a million additions plus a thousand subtractions, with answers in constant time per query. **Prefix Sum & Difference Array** covers the technique in three layers. You will build 1D prefix sums where `prefix[i] = prefix[i-1] + arr[i]` and answer any range sum in `O(1)`. You will then learn the inverse, the difference array, which turns repeated `O(n)` range updates into `O(1)` updates that you reconstruct in a single final pass. The lesson finishes with 2D prefix sums and the inclusion-exclusion trick for answering submatrix sum queries, plus quick variants like prefix XOR and prefix product. In **Arrays & Strings**, you saw why arrays support `O(1)` random access; that property is exactly what makes prefix lookup possible. **Iteration Patterns on Arrays/Strings** trained you to think in terms of single passes, and the prefix sum is the first pattern where one preprocessing pass replaces an entire family of later loops. From here you will move into **Sorting (Elementary)**, where rearranging the array unlocks an entirely different class of techniques.

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.

The mathematical definition `factorial(n) = n * factorial(n - 1)` defines a function in terms of itself, with `factorial(0) = 1` as the stopping point. That two-line definition is also a complete program if your language lets a function call itself. Recursion is what turns self-referential definitions into runnable code, and many problems (tree traversal, graph search, divide and conquer, dynamic programming) describe themselves most naturally that way. **Recursion Fundamentals** breaks down how that machinery actually works. You will learn to identify a base case (when the recursion stops) and a recursive case (how the problem reduces to a smaller instance), trace the call stack as frames are pushed and popped, and reason about return values flowing back up the chain. Examples run through factorial, naive Fibonacci, sum of an array, and integer power, plus a first look at recursion-tree intuition, tail recursion, stack overflow, and the `O(depth)` space cost of deep recursion. In **How to Read Code (JS & Python)**, you saw functions call other functions. **Debugging by Tracing** taught you to follow those calls step by step. Recursion is the case where the function on the call stack is the same function, again and again, with smaller inputs each time. Next, **Backtracking (Intro)** extends recursion with an explicit undo step to systematically explore combinatorial search spaces.

If your phone's contact list is unsorted and you are looking for Sam, the only option is to read names top to bottom until you find a match or hit the end. That brute-force scan is linear search, and it is the right algorithm in a surprising number of situations: small arrays, unsorted data, linked lists, and any case where sorting first would cost more than the search itself. **Searching (Basics)** covers linear search and its small family of variations. You will implement the standard `O(n)` scan in JavaScript and Python, learn the sentinel trick that removes a per-iteration boundary check, and adapt the same template to find the first occurrence, the last occurrence, or the first element matching a condition. The lesson also walks through linear search on linked lists, where you cannot skip ahead by index. In **Arrays & Strings**, you saw why arrays support `O(1)` random access. Searching turns that primitive into a question: how many of those accesses do you need to find a value, and can you do better than reading every one? That question motivates **Binary Search (Intro)** next, which exploits sorted order to bring the cost down to `O(log n)`.

To find the longest substring of `s` with no repeated characters, the brute-force approach checks every substring in `O(n^3)` time. The sliding-window solution touches each character at most twice and runs in `O(n)`: extend a right pointer until a duplicate appears, then advance a left pointer until the duplicate is gone, repeating until the right pointer falls off the end. **Sliding Window (Intro)** turns that idea into two reusable templates. The fixed-size window slides a range of length `k` across the array and updates the running sum or count by adding the new right element and removing the old left element, never recomputing from scratch. The variable-size window expands the right edge while a condition holds and shrinks the left edge to restore that condition, tracking the window's contents with a hash map or counter. You will apply both to maximum-sum subarray of size `k`, longest substring without repeating characters, minimum window substring, and longest substring with at most `k` distinct characters. In **Two Pointers (Intro)**, you used coordinated indices to walk an array linearly. **Hash Map (Dictionary) Basics** gave you the `O(1)` lookup and update that lets a window track its own contents efficiently. Sliding window combines both: two indices and one hash map. From here you turn to **Recursion Fundamentals**, which trades sequential index movement for self-similar subproblems.

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.

Insertion sort is `O(n^2)` and quick sort is `O(n log n)`, yet V8 actually runs insertion sort on arrays shorter than ten elements because the constant factors are smaller. The takeaway is that elementary sorts are not just historical curiosities; they are the algorithms that real engines drop down to once an array is small enough. **Sorting (Elementary)** walks through bubble sort, selection sort, and insertion sort in detail. For each, you will trace the pass-by-pass behavior on a small input, count comparisons and swaps, and analyze worst, best, and average time complexity. Along the way the lesson introduces the vocabulary that every later sorting topic relies on: passes, the growing sorted region, the loop invariant that proves correctness, in-place vs. extra-space sorts, and stability (whether equal keys keep their original relative order). In **Arrays & Strings**, you learned how arrays store and index data; sorting is the first time you will rearrange that storage in place. **Iteration Patterns on Arrays/Strings** trained you in nested loops and swaps, and these three sorts are essentially structured nested loops with a clear invariant. Up next, **Searching (Basics)** establishes the linear-search baseline whose `O(n)` cost is exactly what binary search will later cut down once your data is sorted.

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.

Given a sorted array and a target sum, the brute-force "check every pair" approach is `O(n^2)`. With two indices walking inward from opposite ends, the same problem drops to `O(n)`: if the current pair sums too low, move the left pointer right; if it sums too high, move the right pointer left. **Two Pointers (Intro)** turns that insight into a reusable pattern with two main shapes. The opposite-direction variant has pointers converge from both ends and powers problems like pair sum, palindrome check, reverse in place, and container with most water. The same-direction (fast and slow) variant has both pointers walk forward at different speeds and powers in-place filtering problems like remove duplicates from a sorted array, move zeros to the end, and the linked-list cycle detection you will revisit later. In **Arrays & Strings**, you learned how a single index walks across an array. This lesson coordinates two indices in a way that exploits sorted order or a structural invariant to skip work an inner loop would otherwise repeat. Next, **Sliding Window (Intro)** generalizes the same-direction pointer pair into an expanding and shrinking range that solves contiguous-subarray problems.