Data Structures & Algorithms

Beginner · Roadmap · 72 lessons · 18 groups

Complete on its own: the core data structures and algorithms from the ground up (complexity, arrays/lists/stacks/queues, hash tables, trees and heaps, graphs, sorting, searching, recursion, greedy, backtracking, dynamic programming), then everything computer-science doesn't cover — advanced trees and range-query structures, disjoint sets and graph-structure algorithms, shortest-path algorithms that handle negative weights and heuristics, non-comparison sorting, the design techniques behind divide-and-conquer and randomization, advanced string matching, and the full interview pattern catalog: two pointers, sliding window, merge intervals, cyclic sort, top-k/two-heaps, subsets and permutations, classic DP, and the rest of what LeetCode-style problems are actually built from.

0%

Not started

Nothing saved yet. Progress is kept in this browser until you sign in.

Start the path

Complexity & math foundations · 3

Core data structures · 5

Sorting, searching & recursion · 2

Graph algorithms · 4

Algorithm design paradigms · 3

Advanced linear structures · 4

Priority structures & range queries · 4

Union-find & graph structure · 4

Advanced graph algorithms · 3

Advanced sorting & selection · 2

Algorithm design techniques · 4

Advanced string algorithms · 4

Problem-solving patterns · 5

More interview patterns · 10

Number theory for algorithms · 3

More graph algorithms · 4

More advanced structures · 3

More patterns & tricks · 5

01Asymptotic Notation: Big-O, Big-Theta, and Big-OmegaHow Big-O, Big-Theta, and Big-Omega describe an algorithm's growth rate, and how to work out which one applies to your own code.Beginner · 14 min02Complexity Classes: P, NP, and NP-CompleteWhat it means for a problem to be in P or NP, what NP-complete and NP-hard add on top, and what the P=NP question actually asks.Intermediate · 16 min03Probability and Combinatorics for AlgorithmsHow expected value, linearity of expectation, and counting arguments explain why randomized quicksort is fast on average, no matter the input.Intermediate · 80 min01Arrays, Linked Lists, Stacks, and QueuesThe four linear data structures every other structure builds on, and the time-complexity tradeoffs that decide which one to reach for.Beginner · 7 min02Hash Tables and TriesHow hash tables turn a key into near-instant lookup, how collisions get resolved, and when a trie beats a hash table for strings.Beginner · 9 min03Trees, BSTs, and HeapsBinary trees, the binary search tree property, the three traversal orders, and how a heap keeps the smallest or largest element one step away.Beginner · 8 min04Balanced Search TreesWhy an unbalanced BST can degrade to a linked list, and how AVL trees, red-black trees, and B-trees stay fast through rotations.Intermediate · 13 min05Graph RepresentationDirected vs undirected graphs, adjacency lists vs adjacency matrices, and what a spanning tree is.Beginner · 8 min01Comparison-Based Sorting: Six Algorithms, Two ShapesBubble, selection, insertion, merge, quick, and heap sort compared on time complexity, space, stability, and when each one actually wins.Beginner · 42 min02Linear Search, Binary Search, and RecursionWhy binary search needs sorted data, how recursion replaces a loop with a call stack, and what makes a recursive call "tail" or not.Beginner · 43 min01Graph Traversal: BFS and DFSBreadth-first and depth-first search explore a graph in opposite orders — what each visits first, and when that difference matters.Beginner · 10 min02Shortest Paths: Dijkstra, Bellman-Ford, A*Three ways to find the cheapest path through a weighted graph, and why you can't always reach for the simplest one.Intermediate · 10 min03Minimum Spanning Trees: Prim's and Kruskal'sConnecting every node in a weighted graph as cheaply as possible, two different ways — grow a tree, or sort the edges.Intermediate · 15 min04Network Flow: Max-Flow and Ford-FulkersonHow much can move from a source to a sink through a capacity-limited network, and the augmenting-path method that finds out.Advanced · 15 min01Greedy AlgorithmsMaking the locally best choice at every step, why that provably works for some problems, and why it quietly fails for others.Intermediate · 15 min02BacktrackingBuilding a solution one piece at a time and abandoning a branch the moment it can't work, worked through the N-Queens problem.Intermediate · 15 min03Dynamic Programming & NP-Hard ProblemsSolving overlapping subproblems exactly once with memoization and tabulation, applied to knapsack and the traveling salesman problem.Advanced · 28 min01Dynamic Arrays and Amortized AnalysisHow doubling-based growth turns an occasional O(n) resize into O(1) amortized append, and why shrinking too eagerly destroys that guarantee.Intermediate · 13 min02Skip ListsA probabilistic layered linked list that gets expected O(log n) search, insert, and delete without any tree-rebalancing logic.Intermediate · 14 min03Monotonic Stacks and QueuesA stack or deque kept strictly increasing or decreasing turns O(n²) "find the next bigger/smaller element" scans into a single O(n) pass.Intermediate · 8 min04Deques and Circular BuffersHow a double-ended queue is implemented as a ring buffer over a fixed array, and why wraparound indices make that fast.Intermediate · 11 min01D-ary Heaps and Indexed Priority QueuesGiving a heap more than two children per node trades comparisons for height — and an "indexed" heap adds the one operation Dijkstra actually needs.Intermediate · 22 min02Segment TreesA binary tree over an array that answers any range sum/min/max query in O(log n) and, with lazy propagation, applies range updates just as fast.Intermediate · 28 min03Fenwick Trees (Binary Indexed Trees)A single bit trick, i & -i, turns a plain array into a structure that does prefix sums and point updates in O(log n) with a fraction of a segment tree's code.Intermediate · 14 min04Interval Trees and Range QueriesAugment a BST with one extra field — the max endpoint in its subtree — and it can report every interval overlapping a query in O(log n + k).Intermediate · 7 min01Union-Find & Disjoint SetsTwo small optimizations turn a tree-of-sets data structure into one of the fastest tools in algorithms — near-constant-time union and find.Intermediate · 6 min02Topological SortingOrdering a DAG so every dependency comes before what depends on it — two different algorithms reach the same ordering from opposite directions.Intermediate · 14 min03Strongly Connected ComponentsFinding the maximal clusters of a directed graph where every node can reach every other — and collapsing them into a clean DAG.Intermediate · 18 min04Bipartite Graphs & MatchingTesting whether a graph splits into two independent sides, then pairing up nodes across that split as efficiently as possible.Intermediate · 7 min01Bellman-Ford & Negative WeightsWhy Dijkstra's greedy finalization breaks with negative edges, and how repeated edge relaxation finds shortest paths anyway — and detects negative cycles.Intermediate · 15 min02Floyd-Warshall & All-Pairs Shortest PathsThe O(V^3) DP recurrence that computes shortest paths between every pair of vertices at once, by considering each vertex in turn as a possible waypoint.Intermediate · 16 min03A* SearchDijkstra plus a goal-directed heuristic — how f = g + h skips exploring every direction, and the admissibility/consistency conditions that keep it optimal.Intermediate · 14 min01Non-Comparison Sorts: Counting, Radix, and Bucket SortHow counting, radix, and bucket sort break the Ω(n log n) barrier by never comparing elements, and when that trick applies.Intermediate · 20 min02Order Statistics & QuickselectFinding the kth smallest element without fully sorting, via Quickselect's partition-and-recurse trick, and why median-of-medians guarantees O(n).Intermediate · 19 min01Divide & Conquer and the Master TheoremGeneralizing divide/conquer beyond mergesort and binary search, and using the Master Theorem to read off a recurrence's runtime by inspection.Intermediate · 17 min02Amortized Analysis: Aggregate, Accounting & PotentialThe three formal techniques for proving an amortized bound — aggregate, accounting, and potential — worked through a binary counter and a multipop stack.Intermediate · 76 min03Randomized Algorithms: Las Vegas vs Monte CarloHow randomness turns adversarial worst cases into expected-case guarantees, splitting algorithms into always-correct Las Vegas and bounded-time Monte Carlo.Intermediate · 82 min04Branch and BoundPruning a search tree with an optimality bound instead of a feasibility check, applied to 0/1 knapsack and the traveling salesman problem.Intermediate · 11 min01String Matching: Brute Force to Rabin-KarpFour ways to find a pattern inside a text — brute force, KMP, Boyer-Moore, and Rabin-Karp — plus suffix arrays for repeated queries.Intermediate · 15 min02The Z-Array and Manacher's Algorithm: Two More Linear-Time String TricksTwo independent O(n) ideas — the Z-array for pattern matching without a failure function, and Manacher's algorithm for the longest palindromic substring.Intermediate · 24 min03Suffix Trees: Ukkonen's Algorithm and the Longest Common SubstringSuffix trees as a distinct structure from suffix arrays — Ukkonen's construction, conceptually, and generalized trees for cross-string matching.Intermediate · 76 min04Aho-Corasick: Matching Thousands of Patterns in One PassA trie with failure links generalizes KMP to search for many patterns against a text simultaneously, in one linear-time scan.Intermediate · 14 min01Two pointers & fast/slow pointersTwo coordinated index variables turn O(n^2) array problems into O(n), and the same trick at different speeds detects a linked list cycle with no extra memory.Intermediate · 11 min02Sliding window techniqueA window that only expands and shrinks at its edges, instead of re-scanning substrings from scratch, turns an O(n^2) brute force into a single O(n) pass.Intermediate · 7 min03Binary search on the answerWhen "does X work?" is monotonic in X, you can binary-search the space of possible answers directly, instead of binary-searching a sorted array.Intermediate · 15 min04Meet in the middleSplitting a 2^n search space into two independent 2^(n/2) halves and combining the results turns an exponential brute force into something fast for n up to ~40.Intermediate · 80 min05Bitmask dynamic programmingPacking a subset of up to ~20 elements into one integer as DP state solves problems like the traveling salesman problem exactly, in better-than-factorial time.Intermediate · 20 min01Prefix sums and difference arraysPrecomputing running totals turns range-sum queries into O(1) lookups, and its mirror image, a difference array, turns range updates into O(1) edits.Intermediate · 21 min02Merge intervals patternSorting intervals by start time turns overlapping ranges into a single left-to-right sweep that merges, inserts, or counts overlaps.Intermediate · 10 min03Cyclic sort patternPlacing each value at its "home" index in one O(n) pass exposes missing or duplicate numbers in an array with no extra space.Intermediate · 96 min04In-place linked list reversalRewiring next pointers with a prev/curr/next triple reverses a singly linked list, or any sub-range of one, in O(n) time and O(1) space.Intermediate · 11 min05Subsets, Permutations, and CombinationsOne backtracking template generates every subset, permutation, and k-combination — plus the sort-and-skip trick for duplicate elements.Intermediate · 9 min06Top-K Elements and the Two Heaps PatternTracking the k largest items with a fixed-size min-heap in O(n log k), and the max-heap/min-heap split that maintains a running median in a stream.Intermediate · 24 min07Matrix Traversal PatternsThree recurring 2D-grid techniques — spiral traversal, in-place rotation, and flood-fill over connected regions — and how each handles boundaries.Intermediate · 11 min08Bitwise XOR Tricks for InterviewsThe XOR self-cancellation trick behind single-number problems, plus using a small bitmask as a stand-in for small-set membership.Intermediate · 7 min09Greedy interval schedulingSorting activities by end time and greedily taking the next compatible one provably maximizes non-overlapping intervals; sorting by start time does not.Intermediate · 13 min10Classic Dynamic Programming Patterns: LCS, LIS, and Interval DPThe DP table shapes beyond knapsack — LCS and LIS table-filling, and interval DP over ranges — and how to spot which shape a problem needs.Intermediate · 18 min01Sieve of Eratosthenes and Primality TestingFind every prime up to n in O(n log log n) with the sieve, and test a single number for primality in O(sqrt n) with trial division.Intermediate · 18 min02GCD and Modular ArithmeticThe Euclidean algorithm finds GCD in O(log) steps via gcd(a,b) = gcd(b, a mod b), the foundation for modular arithmetic and inverses.Intermediate · 10 min03Fast ExponentiationCompute a^b mod m in O(log b) time with repeated squaring instead of O(b) naive multiplication, worked through a numeric example.Intermediate · 13 min01Eulerian Paths & CircuitsVisiting every edge of a graph exactly once, the odd-degree-vertex test for when it's possible, and Hierholzer's algorithm for building one.Intermediate · 16 min02Articulation Points & BridgesFinding the single vertices and edges whose removal disconnects a graph, using one DFS pass that tracks discovery time and low-link values.Intermediate · 23 min03Graph ColoringAssigning colors to vertices so no edge joins two same-colored ones, why greedy coloring is fast but not optimal, and its use in compiler register allocation.Intermediate · 9 min04Lowest Common Ancestor TechniquesFinding the deepest shared ancestor of two tree nodes fast, via binary lifting's O(n log n) preprocessing and O(log n) queries.Intermediate · 15 min01Tries and AutocompleteBuild a full autocomplete system on a trie with word-end markers and prefix word counts, and weigh the tradeoffs against a hash set.Intermediate · 20 min02LRU Cache Design and ImplementationImplement an LRU cache with O(1) get and put by pairing a hash map for lookup with a doubly linked list for eviction order.Intermediate · 18 min03Sparse Tables and Static Range QueriesAnswer range-minimum queries in O(1) on a never-updated array using a sparse table built in O(n log n) from overlapping power-of-two ranges.Intermediate · 23 min01Kadane's algorithm and maximum subarrayFinding the maximum-sum contiguous subarray in O(n) by framing each position as a tiny 1D dynamic-programming decision.Intermediate · 8 min02Dutch national flag and three-way partitioningPartitioning an array into three groups in one O(n) pass with three pointers, and how it generalizes quicksort's partition step.Intermediate · 16 min03Boyer-Moore voting algorithmFinding the element that appears more than n/2 times in O(n) time and O(1) space via candidate-and-counter cancellation.Intermediate · 15 min04Reservoir samplingSelecting a uniform random sample of size k from a stream of unknown length in one pass and O(k) space.Intermediate · 13 min05Rolling hash and string hashingUpdating a sliding-window string hash in O(1) per shift, and how it powers Rabin-Karp-style pattern matching.Intermediate · 24 min

Complexity & math foundations

3 lessons

  1. 01 / 03Asymptotic Notation: Big-O, Big-Theta, and Big-OmegaHow Big-O, Big-Theta, and Big-Omega describe an algorithm's growth rate, and how to work out which one applies to your own code.14 min
  2. 02 / 03Complexity Classes: P, NP, and NP-CompleteWhat it means for a problem to be in P or NP, what NP-complete and NP-hard add on top, and what the P=NP question actually asks.16 min
  3. 03 / 03Probability and Combinatorics for AlgorithmsHow expected value, linearity of expectation, and counting arguments explain why randomized quicksort is fast on average, no matter the input.80 min

Core data structures

5 lessons

  1. 01 / 05Arrays, Linked Lists, Stacks, and QueuesThe four linear data structures every other structure builds on, and the time-complexity tradeoffs that decide which one to reach for.7 min
  2. 02 / 05Hash Tables and TriesHow hash tables turn a key into near-instant lookup, how collisions get resolved, and when a trie beats a hash table for strings.9 min
  3. 03 / 05Trees, BSTs, and HeapsBinary trees, the binary search tree property, the three traversal orders, and how a heap keeps the smallest or largest element one step away.8 min
  4. 04 / 05Balanced Search TreesWhy an unbalanced BST can degrade to a linked list, and how AVL trees, red-black trees, and B-trees stay fast through rotations.13 min
  5. 05 / 05Graph RepresentationDirected vs undirected graphs, adjacency lists vs adjacency matrices, and what a spanning tree is.8 min

Sorting, searching & recursion

2 lessons

  1. 01 / 02Comparison-Based Sorting: Six Algorithms, Two ShapesBubble, selection, insertion, merge, quick, and heap sort compared on time complexity, space, stability, and when each one actually wins.42 min
  2. 02 / 02Linear Search, Binary Search, and RecursionWhy binary search needs sorted data, how recursion replaces a loop with a call stack, and what makes a recursive call "tail" or not.43 min

Graph algorithms

4 lessons

  1. 01 / 04Graph Traversal: BFS and DFSBreadth-first and depth-first search explore a graph in opposite orders — what each visits first, and when that difference matters.10 min
  2. 02 / 04Shortest Paths: Dijkstra, Bellman-Ford, A*Three ways to find the cheapest path through a weighted graph, and why you can't always reach for the simplest one.10 min
  3. 03 / 04Minimum Spanning Trees: Prim's and Kruskal'sConnecting every node in a weighted graph as cheaply as possible, two different ways — grow a tree, or sort the edges.15 min
  4. 04 / 04Network Flow: Max-Flow and Ford-FulkersonHow much can move from a source to a sink through a capacity-limited network, and the augmenting-path method that finds out.15 min

Algorithm design paradigms

3 lessons

  1. 01 / 03Greedy AlgorithmsMaking the locally best choice at every step, why that provably works for some problems, and why it quietly fails for others.15 min
  2. 02 / 03BacktrackingBuilding a solution one piece at a time and abandoning a branch the moment it can't work, worked through the N-Queens problem.15 min
  3. 03 / 03Dynamic Programming & NP-Hard ProblemsSolving overlapping subproblems exactly once with memoization and tabulation, applied to knapsack and the traveling salesman problem.28 min

Advanced linear structures

4 lessons

  1. 01 / 04Dynamic Arrays and Amortized AnalysisHow doubling-based growth turns an occasional O(n) resize into O(1) amortized append, and why shrinking too eagerly destroys that guarantee.13 min
  2. 02 / 04Skip ListsA probabilistic layered linked list that gets expected O(log n) search, insert, and delete without any tree-rebalancing logic.14 min
  3. 03 / 04Monotonic Stacks and QueuesA stack or deque kept strictly increasing or decreasing turns O(n²) "find the next bigger/smaller element" scans into a single O(n) pass.8 min
  4. 04 / 04Deques and Circular BuffersHow a double-ended queue is implemented as a ring buffer over a fixed array, and why wraparound indices make that fast.11 min

Priority structures & range queries

4 lessons

  1. 01 / 04D-ary Heaps and Indexed Priority QueuesGiving a heap more than two children per node trades comparisons for height — and an "indexed" heap adds the one operation Dijkstra actually needs.22 min
  2. 02 / 04Segment TreesA binary tree over an array that answers any range sum/min/max query in O(log n) and, with lazy propagation, applies range updates just as fast.28 min
  3. 03 / 04Fenwick Trees (Binary Indexed Trees)A single bit trick, i & -i, turns a plain array into a structure that does prefix sums and point updates in O(log n) with a fraction of a segment tree's code.14 min
  4. 04 / 04Interval Trees and Range QueriesAugment a BST with one extra field — the max endpoint in its subtree — and it can report every interval overlapping a query in O(log n + k).7 min

Union-find & graph structure

4 lessons

  1. 01 / 04Union-Find & Disjoint SetsTwo small optimizations turn a tree-of-sets data structure into one of the fastest tools in algorithms — near-constant-time union and find.6 min
  2. 02 / 04Topological SortingOrdering a DAG so every dependency comes before what depends on it — two different algorithms reach the same ordering from opposite directions.14 min
  3. 03 / 04Strongly Connected ComponentsFinding the maximal clusters of a directed graph where every node can reach every other — and collapsing them into a clean DAG.18 min
  4. 04 / 04Bipartite Graphs & MatchingTesting whether a graph splits into two independent sides, then pairing up nodes across that split as efficiently as possible.7 min

Advanced graph algorithms

3 lessons

  1. 01 / 03Bellman-Ford & Negative WeightsWhy Dijkstra's greedy finalization breaks with negative edges, and how repeated edge relaxation finds shortest paths anyway — and detects negative cycles.15 min
  2. 02 / 03Floyd-Warshall & All-Pairs Shortest PathsThe O(V^3) DP recurrence that computes shortest paths between every pair of vertices at once, by considering each vertex in turn as a possible waypoint.16 min
  3. 03 / 03A* SearchDijkstra plus a goal-directed heuristic — how f = g + h skips exploring every direction, and the admissibility/consistency conditions that keep it optimal.14 min

Advanced sorting & selection

2 lessons

  1. 01 / 02Non-Comparison Sorts: Counting, Radix, and Bucket SortHow counting, radix, and bucket sort break the Ω(n log n) barrier by never comparing elements, and when that trick applies.20 min
  2. 02 / 02Order Statistics & QuickselectFinding the kth smallest element without fully sorting, via Quickselect's partition-and-recurse trick, and why median-of-medians guarantees O(n).19 min

Algorithm design techniques

4 lessons

  1. 01 / 04Divide & Conquer and the Master TheoremGeneralizing divide/conquer beyond mergesort and binary search, and using the Master Theorem to read off a recurrence's runtime by inspection.17 min
  2. 02 / 04Amortized Analysis: Aggregate, Accounting & PotentialThe three formal techniques for proving an amortized bound — aggregate, accounting, and potential — worked through a binary counter and a multipop stack.76 min
  3. 03 / 04Randomized Algorithms: Las Vegas vs Monte CarloHow randomness turns adversarial worst cases into expected-case guarantees, splitting algorithms into always-correct Las Vegas and bounded-time Monte Carlo.82 min
  4. 04 / 04Branch and BoundPruning a search tree with an optimality bound instead of a feasibility check, applied to 0/1 knapsack and the traveling salesman problem.11 min

Advanced string algorithms

4 lessons

  1. 01 / 04String Matching: Brute Force to Rabin-KarpFour ways to find a pattern inside a text — brute force, KMP, Boyer-Moore, and Rabin-Karp — plus suffix arrays for repeated queries.15 min
  2. 02 / 04The Z-Array and Manacher's Algorithm: Two More Linear-Time String TricksTwo independent O(n) ideas — the Z-array for pattern matching without a failure function, and Manacher's algorithm for the longest palindromic substring.24 min
  3. 03 / 04Suffix Trees: Ukkonen's Algorithm and the Longest Common SubstringSuffix trees as a distinct structure from suffix arrays — Ukkonen's construction, conceptually, and generalized trees for cross-string matching.76 min
  4. 04 / 04Aho-Corasick: Matching Thousands of Patterns in One PassA trie with failure links generalizes KMP to search for many patterns against a text simultaneously, in one linear-time scan.14 min

Problem-solving patterns

5 lessons

  1. 01 / 05Two pointers & fast/slow pointersTwo coordinated index variables turn O(n^2) array problems into O(n), and the same trick at different speeds detects a linked list cycle with no extra memory.11 min
  2. 02 / 05Sliding window techniqueA window that only expands and shrinks at its edges, instead of re-scanning substrings from scratch, turns an O(n^2) brute force into a single O(n) pass.7 min
  3. 03 / 05Binary search on the answerWhen "does X work?" is monotonic in X, you can binary-search the space of possible answers directly, instead of binary-searching a sorted array.15 min
  4. 04 / 05Meet in the middleSplitting a 2^n search space into two independent 2^(n/2) halves and combining the results turns an exponential brute force into something fast for n up to ~40.80 min
  5. 05 / 05Bitmask dynamic programmingPacking a subset of up to ~20 elements into one integer as DP state solves problems like the traveling salesman problem exactly, in better-than-factorial time.20 min

More interview patterns

10 lessons

  1. 01 / 10Prefix sums and difference arraysPrecomputing running totals turns range-sum queries into O(1) lookups, and its mirror image, a difference array, turns range updates into O(1) edits.21 min
  2. 02 / 10Merge intervals patternSorting intervals by start time turns overlapping ranges into a single left-to-right sweep that merges, inserts, or counts overlaps.10 min
  3. 03 / 10Cyclic sort patternPlacing each value at its "home" index in one O(n) pass exposes missing or duplicate numbers in an array with no extra space.96 min
  4. 04 / 10In-place linked list reversalRewiring next pointers with a prev/curr/next triple reverses a singly linked list, or any sub-range of one, in O(n) time and O(1) space.11 min
  5. 05 / 10Subsets, Permutations, and CombinationsOne backtracking template generates every subset, permutation, and k-combination — plus the sort-and-skip trick for duplicate elements.9 min
  6. 06 / 10Top-K Elements and the Two Heaps PatternTracking the k largest items with a fixed-size min-heap in O(n log k), and the max-heap/min-heap split that maintains a running median in a stream.24 min
  7. 07 / 10Matrix Traversal PatternsThree recurring 2D-grid techniques — spiral traversal, in-place rotation, and flood-fill over connected regions — and how each handles boundaries.11 min
  8. 08 / 10Bitwise XOR Tricks for InterviewsThe XOR self-cancellation trick behind single-number problems, plus using a small bitmask as a stand-in for small-set membership.7 min
  9. 09 / 10Greedy interval schedulingSorting activities by end time and greedily taking the next compatible one provably maximizes non-overlapping intervals; sorting by start time does not.13 min
  10. 10 / 10Classic Dynamic Programming Patterns: LCS, LIS, and Interval DPThe DP table shapes beyond knapsack — LCS and LIS table-filling, and interval DP over ranges — and how to spot which shape a problem needs.18 min

Number theory for algorithms

3 lessons

  1. 01 / 03Sieve of Eratosthenes and Primality TestingFind every prime up to n in O(n log log n) with the sieve, and test a single number for primality in O(sqrt n) with trial division.18 min
  2. 02 / 03GCD and Modular ArithmeticThe Euclidean algorithm finds GCD in O(log) steps via gcd(a,b) = gcd(b, a mod b), the foundation for modular arithmetic and inverses.10 min
  3. 03 / 03Fast ExponentiationCompute a^b mod m in O(log b) time with repeated squaring instead of O(b) naive multiplication, worked through a numeric example.13 min

More graph algorithms

4 lessons

  1. 01 / 04Eulerian Paths & CircuitsVisiting every edge of a graph exactly once, the odd-degree-vertex test for when it's possible, and Hierholzer's algorithm for building one.16 min
  2. 02 / 04Articulation Points & BridgesFinding the single vertices and edges whose removal disconnects a graph, using one DFS pass that tracks discovery time and low-link values.23 min
  3. 03 / 04Graph ColoringAssigning colors to vertices so no edge joins two same-colored ones, why greedy coloring is fast but not optimal, and its use in compiler register allocation.9 min
  4. 04 / 04Lowest Common Ancestor TechniquesFinding the deepest shared ancestor of two tree nodes fast, via binary lifting's O(n log n) preprocessing and O(log n) queries.15 min

More advanced structures

3 lessons

  1. 01 / 03Tries and AutocompleteBuild a full autocomplete system on a trie with word-end markers and prefix word counts, and weigh the tradeoffs against a hash set.20 min
  2. 02 / 03LRU Cache Design and ImplementationImplement an LRU cache with O(1) get and put by pairing a hash map for lookup with a doubly linked list for eviction order.18 min
  3. 03 / 03Sparse Tables and Static Range QueriesAnswer range-minimum queries in O(1) on a never-updated array using a sparse table built in O(n log n) from overlapping power-of-two ranges.23 min

More patterns & tricks

5 lessons

  1. 01 / 05Kadane's algorithm and maximum subarrayFinding the maximum-sum contiguous subarray in O(n) by framing each position as a tiny 1D dynamic-programming decision.8 min
  2. 02 / 05Dutch national flag and three-way partitioningPartitioning an array into three groups in one O(n) pass with three pointers, and how it generalizes quicksort's partition step.16 min
  3. 03 / 05Boyer-Moore voting algorithmFinding the element that appears more than n/2 times in O(n) time and O(1) space via candidate-and-counter cancellation.15 min
  4. 04 / 05Reservoir samplingSelecting a uniform random sample of size k from a stream of unknown length in one pass and O(k) space.13 min
  5. 05 / 05Rolling hash and string hashingUpdating a sliding-window string hash in O(1) per shift, and how it powers Rabin-Karp-style pattern matching.24 min
Esc
↑↓ navigate↵ open? shortcuts

Keyboard shortcuts

Press Esc to close

Anywhere

⌘K
Search and commands
/
Search
?
This sheet
Esc
Close

Reading a lesson

J
Next lesson
K
Previous lesson
B
Bookmark