brain

WebAssembly, often shortened to Wasm, is a portable binary instruction format. It lets you compile code once and run it inside different hosts, such as web browsers, servers,...

Many Item Pointers

A many item pointer is a pointer that can move across several values of the same type.

Multidimensional Arrays

A multidimensional array is an array whose elements are also arrays.

Default Field Values

A struct field can have a default value.

Understanding Stage2

When people talk about Zig compiler internals, they often mention stage2.

Nullable Pointers

A pointer stores the address of a value in memory.

Inline Branching

Inline branching means Zig chooses a branch during compilation, not during runtime.

`@sizeOf`

@sizeOf asks the Zig compiler how many bytes a type needs in memory.

Table-Driven Tests

A table-driven test checks many input cases with one test loop.

Why StringHashMap Exists

A StringHashMap is a hash map where the key is a string.

Arena Allocator

An arena allocator is an allocator that frees many allocations at once.

Calling C Functions

Calling a C function from Zig has three parts.

Working with the OS

Systems programming means working directly with the operating system.

The Basic Idea

Modern CPUs are fast, but memory is much slower.

Plugin Architectures

A plugin architecture lets a program be extended without rewriting the whole program.

Atomics

An atomic operation is a small operation that can safely happen while several threads are running.

Writing Files

Writing a file means sending bytes from your program to the operating system so they can be stored on disk.

macOS Support

macOS is one of Zig’s main desktop targets. You can use Zig on macOS to write command-line tools, development utilities, servers, libraries, and cross-platform applications.

Adding Dependencies

A Zig project can depend on other Zig packages.

Build a Static File Server

A static file server is a program that reads files from a directory and sends them to a browser over HTTP.

Single Item Pointers

A pointer is a value that stores the address of another value.

Array Literals

An array literal is the syntax you use to write array values directly in source code.

Struct Methods

A struct method is a function that belongs to a struct.

Appendix A. Zig 0.16 New Features

Zig 0.16.0 was released on April 14, 2026. The release contains 8 months of work, with changes from 244 contributors across 1,183 commits. The largest themes are the new I/O...

Optional Unwrapping

Optional unwrapping means taking the value out of an optional.

Compile-Time Variables

In the previous section, you learned that Zig can execute code during compilation.

`@import`

One of the first Zig builtins you will learn is @import.

General Purpose Allocator

The general purpose allocator is Zig’s standard allocator for ordinary heap allocation.

The Basic Idea

A HashMap is a data structure for storing values by key.

Writing Unit Tests

A unit test checks one small piece of code in isolation.

Reading Files

Reading a file means asking the operating system for bytes stored on disk.

`@cImport`

@cImport is Zig’s built-in way to import C declarations from header files.

System Calls

A system call is a request from your program to the operating system.

Why Profiling Matters

When a program feels slow, your first job is not optimization.

Reflection Systems

Reflection means a program can inspect information about types while the program is being compiled or running.

Linux Support

Linux is one of the most natural platforms for Zig. Many Zig programs are built, tested, and deployed on Linux because Linux is common in servers, containers, embedded...

Zig Source Tree

When you first open the Zig source code repository, it can feel overwhelming.

Build a JSON Parser

A JSON parser reads JSON text and turns it into data your program can use.

What Is Zig

Zig is a programming language for writing fast, small, reliable programs.

What Is Zig

Zig is a programming language for writing fast, small, reliable programs.

Variables and Constants

A program stores values so it can use them later. In Zig, you store values with two main keywords:

Why Zig Has No Exceptions

Most programming languages need a way to handle failure.

Memory Model Basics

Memory is where a program keeps its data while it runs.

Fixed Arrays

An array is a group of values stored next to each other.

Struct Definitions

A struct is a type that groups several values together.

Optional Types

An optional type is a type that can hold either a value or no value.

Understanding `@` Builtins

Zig has special built-in functions whose names start with @.

Why Zig Uses Allocators

Memory is one of the most important ideas in Zig.

Importing ArrayList

An ArrayList is one of the most important data structures in Zig.

Zig Test Framework

Zig has a built-in test system. You do not need a separate testing library to start writing tests.

Why Zig Works Well with C

Zig works unusually well with C because it treats C as a first-class part of systems programming.

Threads in Zig

A thread is a separate path of execution inside one program.

Memory Mapped Files

A memory mapped file is a file that the operating system places into your program's address space.

What Actually Makes Programs Slow?

Performance is one of the main reasons people choose Zig.

Custom Formatting

Zig has a formatting system built into the standard library. You have already used it many times through std.debug.print.

Windows Support

Windows is one of Zig’s main supported platforms. You can write Zig programs on Windows, build Windows executables, call Windows system APIs, link with C libraries, and...

Build a CLI Calculator

In this project, we will build a small command-line calculator.

Zig Compiler Architecture

The Zig compiler is not only a compiler for the Zig language. It is also the center of the Zig toolchain.

Reserved Keywords

A keyword is a word that has special meaning in Zig.

Reading Zig Error Messages

Sooner or later, every Zig beginner meets the compiler.

Zig Generics Use `comptime`

A generic function is a function that works with many types instead of only one type.

Editors, LSP, and Debuggers

You can write Zig code in any text editor.

Comments and Documentation

Comments are notes for humans who read the code.

Compile Errors as Safety Checks

A compile error means Zig refused to build your program.

What “Exported” Means

An exported function is a function made visible outside the current Zig program.

Project Structure

So far, we have used single-file programs.

Unreachable Code

Some parts of a program should never run.

A Mental Model

A calling convention defines how functions communicate at the machine level.

Custom Error Types

Most Zig programs start with small error sets:

Zig Compiler as a Toolchain

When beginners hear the word “compiler,” they often think of one job:

Zero Values and Initialization

Initialization means giving a value to something when it is created.

Defer and Cleanup

Many programs need to clean something up after using it.

A Simple Function

An inline function is a function where the compiler may place the function’s code directly at the call site instead of performing a normal function call.

Designing Error APIs

An error API is the part of your function signature that tells callers how failure works.

Understanding `zig build-exe`

In the previous section, we used this command:

Undefined Values

In Zig, undefined means “this value has not been initialized.”

Inline Loops

Zig has normal loops that run when the program runs.

What Anonymous Functions Usually Mean

An anonymous function is a function without a permanent name.

Propagating Errors

Propagating an error means passing it to the caller instead of handling it immediately.

Your First Zig Program

Now we will write and run a complete Zig program.

Type Inference

Type inference means Zig can figure out a type from the value you write.

`break` and `continue`

Loops repeat code. But sometimes you do not want a loop to finish in the normal way.

Zig Release Channels and Versioning

Before writing larger Zig programs, you need to understand an important fact:

Booleans and Comparisons

A boolean is a value that can be only one of two things:

A First Example

Recursion is a technique where a function calls itself.

`catch`

catch handles an error at the place where it happens.

Installing Zig

Before we write more Zig code, we need the Zig compiler.

Floating Point Numbers

Floating point numbers are numbers with fractional parts.

`for` Loops

A while loop repeats while a condition is true.

Returning a Struct

Many functions need to produce more than one piece of information.

`try`

try is the most common way to handle errors in Zig.

Why Zig Exists

Zig exists because low-level programming is still important, but the old tools have painful tradeoffs.

The `return` Keyword

Functions often need to produce results.

What Is Zig

Zig is a programming language for writing programs that are fast, clear, and close to the machine.

Primitive Types

Every value in a Zig program has a type.

`switch`

An if statement is good for general conditions:

Parameter Syntax

Function parameters are the inputs of a function.

Error Sets

An error set is a group of possible error names.

Euler Products

Euler products are one of the central ideas of analytic number theory. They express infinite sums over integers as infinite products over primes.

Dirichlet Series

An arithmetic function $fn$ can be encoded into an infinite series of the form

Average Orders of Arithmetic Functions

Arithmetic functions often fluctuate strongly from one integer to the next.

Möbius Inversion

Many arithmetic functions are defined through sums over divisors. For example,

Dirichlet Convolution

Arithmetic functions can be added and multiplied pointwise, but number theory has another product that is better adapted to divisibility.

Completely Multiplicative Functions

An arithmetic function is a function defined on the positive integers. Such a function

Frobenius Automorphisms

One of the deepest ideas in algebraic number theory is that prime numbers possess hidden symmetry inside field extensions.

Parity Problem

Sieve methods are extremely effective for estimating how many integers avoid small prime factors. They have produced major results about:

Appendix A.1 Sets and Functions

A set is a collection of objects called elements.

Liouville Function

The Liouville function is an arithmetic function denoted by

Decomposition and Inertia Groups

Let

Chen's Theorem

The Twin Prime Conjecture states that infinitely many primes satisfy

Euler Totient Function

Euler's totient function is an arithmetic function denoted by

Ramification of Primes

In the ordinary integers, every nonzero integer factors uniquely into prime numbers.

Bombieri-Vinogradov Theorem

The Prime Number Theorem for arithmetic progressions states that for

The Langlands Program

The Langlands program is one of the largest and most influential research programs in modern mathematics.

Möbius Function

The Möbius function is an arithmetic function denoted by

Local Fields

Classical number theory studies arithmetic globally over fields such as

Brun-Titchmarsh Theorem

One of the central problems of analytic number theory is understanding how primes distribute among residue classes.

The Birch and Swinnerton-Dyer Conjecture

An elliptic curve over $\mathbb{Q}$ may be written in Weierstrass form

Divisor Functions

Divisor functions measure the positive divisors of an integer. They are among the first examples of arithmetic functions, because their values depend directly on the prime...

$p$-Adic Numbers

The real numbers arise by completing the rational numbers using the ordinary absolute value. The $p$-adic numbers arise by completing the rational numbers using the $p$-adic...

Large Sieve

Classical sieve methods estimate how many integers survive congruence restrictions. The large sieve approaches these problems from a different direction.

The Riemann Hypothesis

The Riemann zeta function is one of the central objects in mathematics.

Applications to Computation

Modular arithmetic is not only a theoretical language for divisibility. It is also one of the main tools of computation with integers.

Valuations and Absolute Values

In ordinary analysis, the absolute value

Selberg Sieve

Brun's sieve introduced the idea of estimating sifted sets through truncated inclusion-exclusion. However, Brun's method often produced bounds that were technically difficult...

Fermat's Last Theorem

Fermat's Last Theorem states that there are no positive integers

Fast Modular Exponentiation

Modular arithmetic often requires computing powers such as

Dedekind Domains

Ordinary integers satisfy several remarkable properties simultaneously:

Brun Sieve

Sieve methods are techniques for counting integers that remain after removing residue classes modulo primes.

Geometric Langlands Theory

The classical Langlands program relates:

Open Problems in Number Theory

Number theory contains some of the oldest and deepest unsolved problems in mathematics.

Chinese Remainder Theorem

The Chinese remainder theorem describes when several congruence conditions can be combined into one congruence. Its cleanest form occurs when the moduli are pairwise coprime.

Principal Ideals

Let $R$ be a commutative ring. An ideal $I\subseteq R$ is called principal if there exists an element $\alpha\in R$ such that

Schnirelmann Density

In additive number theory, ordinary asymptotic density is often too weak to control additive behavior.

Shimura Varieties

Modular curves parameterize elliptic curves and connect modular forms with arithmetic geometry.

Arithmetic Statistics

Arithmetic statistics studies the distribution of arithmetic objects inside large families.

Systems of Congruences

A system of congruences asks for an integer satisfying several congruence conditions simultaneously.

Discriminants

The discriminant is one of the most important invariants of a number field. It measures how the arithmetic of the field differs from ordinary rational arithmetic.

Additive Bases

A central question in additive number theory asks whether every integer can be represented as a sum of elements from a fixed set.

Trace Formulas

Fourier analysis decomposes functions into harmonic frequencies.

Probabilistic Models for Primes

Prime numbers are deterministic objects, but many aspects of their distribution resemble random behavior.

Modular Inverses

In ordinary arithmetic, division by a nonzero number means multiplication by its reciprocal. Modular arithmetic is more delicate. A residue class may or may not have a...

Units and Dirichlet Unit Theorem

Let $K$ be a number field and let

Exponential Sums

Exponential sums are among the central tools of analytic number theory.

Random Matrices and Zeta Zeros

The Riemann zeta function is defined for $\operatorname{Re}s>1$ by

Linear Congruences

A linear congruence is a congruence of the form

Class Groups

In ordinary integers, every ideal is generated by a single element:

Circle Method

Many problems in additive number theory ask whether an integer can be represented in the form

Functoriality

The Langlands program predicts that many different arithmetic objects are connected by systematic transfers.

Probabilistic Algorithms

A probabilistic algorithm uses random choices during its execution. In number theory, this is often a practical advantage rather than a weakness.

Arithmetic Modulo $n$

Arithmetic modulo $n$ is arithmetic performed on residue classes modulo $n$. Instead of distinguishing all integers separately, we identify integers that have the same...

Ideals and Prime Ideals

In ordinary integers, every number factors uniquely into primes. In many rings of algebraic integers, this property fails.

Waring's Problem

Waring's problem asks whether every sufficiently large positive integer can be written as a sum of a bounded number of fixed powers.

Galois Representations

Galois groups encode the symmetries of algebraic equations and field extensions.

Probabilistic Primality

A primality test determines whether an integer is prime.

Residue Classes

Congruence modulo $n$ groups integers according to their remainders after division by $n$. If two integers have the same remainder, they are congruent modulo $n$.

Unique Factorization Failure

One of the central properties of the ordinary integers is unique factorization.

Goldbach Problems

Goldbach-type problems ask whether integers can be represented as sums of primes. They are among the oldest and most famous problems in additive number theory.

The Langlands Program

The Langlands program is one of the most ambitious and influential theories in modern mathematics.

Smooth Numbers

A positive integer is called $y$-smooth if all of its prime factors are at most $y$.

Congruence Relations

Ordinary equality compares integers exactly. In many arithmetic problems, however, only the remainder after division matters.

Sumsets

Additive number theory studies arithmetic structure through addition of integers and subsets of integers.

Automorphic Representations

Classical modular form theory begins with analytic functions satisfying symmetry conditions.

Random Integers

Number theory often studies exact statements about individual integers. For example, one may ask whether a given integer is prime, squarefree, smooth, or representable as a...

Distribution Heuristics of Primes

The infinitude of primes guarantees that primes continue indefinitely, but it says nothing about how frequently primes occur.

Generalized Riemann Hypothesis

The classical Riemann Hypothesis concerns the zeros of the Riemann zeta function

Automorphic Forms

Modular forms are functions on the upper half-plane satisfying symmetry conditions under the modular group

Zero-Knowledge Proofs

A zero-knowledge proof allows one party to convince another that a statement is true without revealing why it is true.

Euler's Proof

Euclid proved that there are infinitely many primes by contradiction. Euler discovered a very different proof based on infinite series and products.

Number Fields

A number field is a finite extension of the rational numbers. Concretely, it is a field $K$ satisfying

Nonvanishing Results

A central theme in analytic number theory is determining when an $L$-function is nonzero at a particular point.

The Modularity Theorem

For centuries, elliptic curves and modular forms were studied as separate objects.

Post-Quantum Cryptography

Modern public-key cryptography relies heavily on two computational assumptions:

Euclid's Proof

Euclid's proof of the infinitude of primes is one of the earliest examples of a general argument in number theory. It does not depend on computation, experimentation, or...

Minimal Polynomials

An algebraic number is a complex number that satisfies some nonzero polynomial equation with rational coefficients. Thus $\alpha\in\mathbb{C}$ is algebraic if there exists a...

Primes in Arithmetic Progressions

An arithmetic progression is a sequence of the form

Elliptic Curves and Modularity

An elliptic curve is simultaneously:

Lattice Cryptography

Lattice cryptography is a family of cryptographic systems based on the presumed hardness of computational problems on high-dimensional lattices.

Infinitude of Primes

Prime numbers are the building blocks of the positive integers. Once unique prime factorization is known, a natural question arises: are there only finitely many primes, or do...

Modular Curves

The modular group acts on the upper half-plane by fractional linear transformations:

Pairing-Based Cryptography

Pairing-based cryptography uses special maps defined on elliptic curve groups. A pairing is a function

Arithmetic Functions from Factorization

An arithmetic function is a function whose domain is the positive integers. It assigns a value to each integer

Diophantine Approximation

Diophantine approximation studies how closely real numbers can be approximated by rational numbers.

Orthogonality Relations

Dirichlet characters behave analogously to exponential functions in Fourier analysis. Just as complex exponentials separate frequencies, characters separate residue classes...

Hecke Operators

Modular forms already possess symmetry under the modular group. Yet a deeper arithmetic structure emerges through another family of operators: the Hecke operators.

Elliptic Curve Cryptography

Elliptic curve cryptography is a public-key cryptographic framework based on the arithmetic of elliptic curves over finite fields.

Canonical Prime Decomposition

Unique prime factorization says that every integer $n>1$ can be written as a product of primes. The canonical prime decomposition is the ordered and exponentiated version of...

Pell Equations via Continued Fractions

Recall that a Pell equation has the form

Dirichlet Characters

The Riemann zeta function studies prime numbers globally, without distinguishing congruence classes. However, many arithmetic questions concern primes satisfying conditions such as

Cusp Forms

Modular forms satisfy strong symmetry conditions under the modular group. Among them, cusp forms form the deepest and most arithmetic subclass.

Diffie-Hellman Key Exchange

Secure communication requires two parties to share secret information. In classical symmetric cryptography, both parties must already possess the same secret key before...

Unique Prime Factorization

The fundamental theorem of arithmetic states that every integer $n>1$ can be written as a product of prime numbers, and that this product is unique up to the order of the factors.

Convergents

The convergents of a continued fraction are the rational numbers obtained by truncating the expansion at finite stages.

Connections with Prime Distribution

The Riemann zeta function was introduced through the series

Eisenstein Series

Among all modular forms, Eisenstein series are the most explicit and computationally accessible.

RSA Cryptosystem

Classical cryptography uses a shared secret key. Both sender and receiver must know the same secret information in advance.

Coprime Integers

Two integers $a$ and $b$, not both zero, are called coprime if their greatest common divisor is $1$:

Explicit Formulae

One of the deepest ideas in analytic number theory is that the zeros of the zeta function determine the distribution of prime numbers.

Modular Forms

Modular forms are among the central objects of modern number theory.

Symbolic and Numeric Computation

Modern number theory relies heavily on computation. Two broad computational paradigms dominate the subject:

Bezout Identities

Let $a$ and $b$ be integers. An integer of the form

Infinite Continued Fractions

Finite continued fractions correspond exactly to rational numbers. When the Euclidean algorithm never terminates, the continued fraction becomes infinite.

Riemann Hypothesis

The Riemann zeta function has nontrivial zeros inside the critical strip

Modular Functions

The modular group acts on the upper half-plane by fractional linear transformations:

Algorithms for Elliptic Curves

Elliptic curves occupy a central position in modern number theory, arithmetic geometry, and cryptography.

Extended Euclidean Algorithm

The Euclidean algorithm computes the greatest common divisor of two integers. The extended Euclidean algorithm does more. It also expresses the gcd as an integer linear...

Finite Continued Fractions

A finite continued fraction is an expression of the form

Zeros of the Zeta Function

The zeros of the Riemann zeta function are the complex numbers $s$ satisfying

Modular Groups

Modular forms begin with the action of certain matrix groups on the complex upper half-plane.

Algorithms for Modular Forms

Modular forms are highly structured analytic functions with deep arithmetic properties. Although their definitions involve complex analysis and group actions, modular forms...

Euclidean Algorithm

The greatest common divisor of two integers can be found by listing divisors, but this method becomes inefficient for large numbers. For example, finding

Euclidean Algorithm Revisited

The Euclidean algorithm is one of the oldest and most important algorithms in mathematics. It computes the greatest common divisor of two integers using repeated division.

Functional Equation

The defining series of the zeta function,

Global Class Field Theory

One of the central goals of algebraic number theory is to classify field extensions of a number field

Lattice Reduction

A lattice is a discrete additive subgroup of Euclidean space. More concretely, let

Suggested Projects and Explorations

Study empirical properties of prime numbers through computation.

Least Common Multiples

Let $a$ and $b$ be nonzero integers. An integer $m$ is called a common multiple of $a$ and $b$ if

Computational Aspects

Quadratic residue theory is not only a theoretical subject. It also plays a major role in computational number theory, cryptography, primality testing, and algorithm design.

Analytic Continuation

The defining series of the Riemann zeta function is

Local Class Field Theory

Global class field theory studies finite abelian extensions of number fields such as

Integer Factorization

Integer factorization asks for the prime decomposition of a positive integer. Given

Problem Sets

1. Prove that the sum of two even integers is even.

Greatest Common Divisors

Let $a$ and $b$ be integers, not both zero. An integer $d$ is called a common divisor of $a$ and $b$ if

Higher Reciprocity Laws

Quadratic reciprocity describes when one prime is a square modulo another prime. A natural question is whether similar laws exist for higher powers.

Euler Product Formula

The defining series of the Riemann zeta function is

Hilbert Class Fields

One of the central discoveries of algebraic number theory is that unique factorization may fail in rings of algebraic integers.

Primality Testing

A prime number is an integer greater than $1$ whose only positive divisors are

The Division Algorithm

The division algorithm is one of the basic structural facts about the integers. It says that any integer can be divided by a positive integer with a unique quotient and remainder.

Gauss Sums

Gauss sums arise from combining multiplicative and additive structures modulo a prime. They form one of the fundamental tools of analytic and algebraic number theory.

Definition of the Zeta Function

One of the central objects of analytic number theory is the Riemann zeta function. It connects infinite series, prime numbers, complex analysis, and arithmetic structure into...

Reciprocity Maps

One of the oldest themes in number theory is reciprocity: the phenomenon that solvability conditions for one prime are controlled by arithmetic involving another prime.

Fast Integer Arithmetic

Modern computational number theory depends fundamentally on efficient arithmetic with large integers.

Composite Numbers

A positive integer $n>1$ is called composite if it is not prime.

Quadratic Reciprocity

The theory of quadratic residues asks a fundamental question:

Abelian Extensions

A central goal of algebraic number theory is to understand field extensions of a given base field, especially extensions of the rational numbers

Trace Formula

One of the central ideas of modern analysis is that functions may be decomposed spectrally into elementary pieces.

Prime Numbers

Prime numbers are the fundamental building blocks of arithmetic.

Euler Criterion

Euler criterion gives an efficient way to decide whether an integer is a square modulo an odd prime. Let $p$ be an odd prime and let $a$ be an integer not divisible by $p$....

Adeles and Ideles

The rational numbers may be studied through their completions:

Functoriality

Functoriality is the unifying mechanism of the Langlands program. It predicts systematic relationships between automorphic representations attached to different algebraic groups.

Divisibility Relations

Division of integers does not always produce an integer. For example,

Short Intervals

The Prime Number Theorem describes the average distribution of primes up to a large number $x$:

Local-Global Principles

A central problem in number theory is determining whether an equation possesses rational or integral solutions.

Langlands Program

The Langlands program is a broad collection of conjectures connecting number theory, representation theory, harmonic analysis, and algebraic geometry. Its central idea is that...

Historical Development of Number Systems

The idea of number arose long before formal mathematics. Early civilizations used numbers for counting objects, measuring land, recording trade, and tracking time.

Legendre Symbol

Let $p$ be an odd prime and let $a\in\mathbb{Z}$. The Legendre symbol is defined by

Hensel’s Lemma

One of the central ideas of number theory is that congruences modulo powers of a prime often approximate genuine arithmetic solutions.

Adelic Methods

Number theory studies arithmetic simultaneously at two levels:

Appendix J. Historical Notes and Bibliography

Number theory is one of the oldest parts of mathematics, but modern number theory is not a single ancient subject carried forward unchanged. It is a layered discipline....

Growth of Integers

The integers extend infinitely in both directions:

Squares Modulo $n$

A quadratic congruence is a congruence involving a square. The basic form is

Logarithmic Integral

The logarithmic integral is the function

Completion of Fields

The rational numbers form a field rich enough for arithmetic, yet insufficient for many limiting processes.

Automorphic Representations

Classically, number theory studied special analytic functions such as modular forms. These functions satisfy strong symmetry conditions under actions of arithmetic groups.

Appendix I. Computational Tools

Computation has become an essential part of number theory. Classical arithmetic relied mainly on symbolic reasoning and hand calculations. Modern arithmetic combines rigorous...

Recursive Definitions

Many mathematical objects are defined recursively. A recursive definition specifies:

Geometry of Diophantine Problems

A Diophantine equation is first an arithmetic object. It asks for solutions in integers or rational numbers. But every polynomial equation also defines a geometric object.

Prime Number Theorem

The Prime Number Theorem describes the asymptotic distribution of prime numbers. It states that

Appendix H. Category Theory Basics

Category theory studies mathematical structures through objects and maps between them. Instead of looking only at what objects are made of, it studies how they relate to other...

$p$-Adic Numbers

The real numbers arise by completing the rational numbers with respect to the ordinary absolute value. This completion produces a field suited to Euclidean geometry and...

Representation Theory Background

Representation theory studies abstract algebraic objects by expressing them as linear transformations of vector spaces.

Strong Induction

Ordinary induction proves a statement $Pn$ by showing that truth passes from one case to the next:

Rational and Integral Points

A central problem in number theory is to study solutions of polynomial equations whose coordinates belong to a specified number system. Two important cases are:

Appendix G. Linear Algebra Review

A vector space over a field $F$ is a set $V$ equipped with addition and scalar multiplication satisfying the usual algebraic rules.

Absolute Values

The ordinary absolute value on the real numbers measures magnitude:

Weil Conjectures

One of the central problems in arithmetic geometry is understanding the number of solutions of polynomial equations over finite fields.

Mathematical Induction

Many statements in number theory concern all natural numbers. For example, one may wish to prove that

Exponential Diophantine Equations

An exponential Diophantine equation is a Diophantine equation in which one or more unknowns appear as exponents. Typical examples include

Prime Counting Function

One of the oldest questions in number theory asks how prime numbers are distributed among the positive integers. Since primes become less frequent as numbers grow larger,...

Appendix F. Measure and Integration

Measure theory extends the ideas of length, area, volume, and integration to more general settings. In number theory, measure appears in probability, harmonic analysis,...

Ramification

One of the central ideas of algebraic number theory is that prime numbers may behave differently after passing to a larger field.

Étale Cohomology

Classical topology studies geometric spaces using invariants such as homology and cohomology. Over the complex numbers, algebraic varieties can often be viewed as topological...

Absolute Value and Distance

The order relation distinguishes positive and negative integers, but in many situations the sign of a number is less important than its magnitude. For example, the integers

Catalan-Type Equations

A Catalan-type equation is a Diophantine equation involving powers whose values differ by a small amount. The classical example is

Abel Summation

In analytic number theory, one often studies sums of the form

Appendix E. Topology Background

Topology studies continuity, convergence, connectedness, and geometric structure in an abstract setting. In number theory, topology appears naturally in real analysis, complex...

Cyclotomic Fields

One of the most important classes of number fields arises from the solutions of the equation

Arithmetic Surfaces

Arithmetic geometry often studies families of algebraic curves varying over arithmetic bases. The most important base is

Order Relations

The integers are not merely a collection of numbers equipped with arithmetic operations. They also possess an order structure. Given two integers $a$ and $b$, one can...

Sums of Squares

One of the oldest questions in number theory asks which integers can be written as sums of squares. Typical examples are

Convergence Methods

Analytic number theory studies infinite sums, products, and integrals. Before such expressions can be manipulated safely, one must understand the meaning of convergence.

Appendix D. Real and Complex Analysis Review

The real numbers $\mathbb{R}$ extend the rational numbers $\mathbb{Q}$ by filling gaps such as

Curves over Fields

An algebraic curve is a geometric object whose dimension is one. Curves are among the oldest and most important objects in number theory and algebraic geometry.

Arithmetic Operations

An arithmetic operation is a rule that combines numbers to produce another number. The most basic operations on integers are addition, subtraction, multiplication, and division.

Pell Equations

A Pell equation is a Diophantine equation of the form

Euler Products

Euler products arise when an infinite series has coefficients controlled by multiplication. The simplest and most important example is the zeta series

Appendix C. Abstract Algebra Review

Abstract algebra studies sets equipped with operations. In number theory, these structures organize arithmetic behavior.

Galois Groups

A polynomial equation may possess several roots related by hidden algebraic symmetries. Consider

Morphisms and Fibers

Geometry is not only concerned with spaces themselves, but also with maps between spaces. In algebraic geometry and arithmetic geometry, these maps are called morphisms.

The Integers

The natural numbers are sufficient for counting and addition, but they are not sufficient for subtraction. For example,

Appendix B. Proof Techniques

A mathematical proof is a logically complete argument establishing the truth of a statement from accepted assumptions, definitions, and previously proved results.

Pythagorean Triples

A Pythagorean triple is a triple of positive integers

Splitting Fields

A central problem in algebra is to determine where a polynomial factors completely into linear terms. Consider the polynomial

Schemes

Classical algebraic geometry studies varieties defined by polynomial equations. This theory works well over algebraically closed fields, especially over $\mathbb{C}$. However,...

Chapter 1. Foundations of Arithmetic

The natural numbers arise from the basic act of counting. When we count objects in a collection, we assign successive numbers:

Chapter 2. Classical Number Theory

A Diophantine equation is an equation whose solutions are required to be integers. The unknowns are not allowed to range over the real numbers or complex numbers unless...

Chapter 3. Analytic Number Theory

The harmonic series is the infinite series

Chapter 4. Algebraic Number Theory

A field is a number system in which addition, subtraction, multiplication, and division by nonzero elements are always possible. The rational numbers $\mathbb{Q}$, the real...

Chapter 5. Arithmetic Geometry and Modern Directions

Arithmetic geometry studies solutions of polynomial equations by combining algebra, geometry, and number theory. Its basic objects are spaces defined by polynomial equations....

Appendix

A set is a collection of objects, called its elements. If $x$ is an element of a set $A$, we write $x \in A$. If $x$ is not an element of $A$, we write $x \notin A$.

Future Directions in Number Theory

Modern number theory continues to evolve rapidly.

LeetCode 925: Long Pressed Name

A clear explanation of the Long Pressed Name problem using a two-pointer scan.

LeetCode 975: Odd Even Jump

A clear explanation of counting good starting indices using next-jump preprocessing and dynamic programming.

LeetCode 974: Subarray Sums Divisible by K

A clear explanation of counting subarrays whose sum is divisible by k using prefix sums and remainder frequencies.

LeetCode 973: K Closest Points to Origin

A clear explanation of returning the k closest points to the origin using squared distance and sorting.

LeetCode 972: Equal Rational Numbers

A clear explanation of comparing rational numbers written as decimal strings with optional repeating parts.

LeetCode 971: Flip Binary Tree To Match Preorder Traversal

A clear explanation of matching a binary tree preorder traversal by greedily flipping nodes.

LeetCode 970: Powerful Integers

A clear explanation of generating all powerful integers using bounded powers and a set.

LeetCode 969: Pancake Sorting

A clear explanation of sorting an array using prefix reversals by repeatedly placing the largest remaining value.

LeetCode 968: Binary Tree Cameras

A clear explanation of placing the minimum number of cameras in a binary tree using postorder DFS.

LeetCode 967: Numbers With Same Consecutive Differences

A clear explanation of generating all n-digit numbers whose adjacent digits differ by k.

LeetCode 966: Vowel Spellchecker

A clear explanation of implementing a spellchecker with exact, case-insensitive, and vowel-error matching.

LeetCode 965: Univalued Binary Tree

A clear explanation of checking whether every node in a binary tree has the same value.

LeetCode 964: Least Operators to Express Number

A clear explanation of expressing a target using the fewest operators with repeated uses of x.

LeetCode 963: Minimum Area Rectangle II

A clear explanation of finding the minimum-area rectangle from points when the rectangle may be rotated.

LeetCode 962: Maximum Width Ramp

A clear explanation of finding the maximum width ramp using a monotonic decreasing stack.

LeetCode 961: N-Repeated Element in Size 2N Array

A clear explanation of finding the element repeated N times using a hash set.

LeetCode 960: Delete Columns to Make Sorted III

A clear explanation of deleting the minimum number of columns so every remaining row is individually sorted.

LeetCode 959: Regions Cut By Slashes

A clear explanation of counting regions formed by slashes using union find over four triangles per cell.

LeetCode 958: Check Completeness of a Binary Tree

A clear explanation of checking whether a binary tree is complete using level-order traversal.

LeetCode 957: Prison Cells After N Days

A clear explanation of simulating prison cell transitions efficiently using cycle detection.

LeetCode 956: Tallest Billboard

A clear explanation of solving Tallest Billboard using dynamic programming over height differences.

LeetCode 955: Delete Columns to Make Sorted II

A clear explanation of deleting the minimum number of columns so rows become lexicographically sorted.

LeetCode 954: Array of Doubled Pairs

A clear explanation of checking whether an array can be reordered into pairs where one number is double the other.

LeetCode 953: Verifying an Alien Dictionary

A clear explanation of checking whether words are sorted according to a custom alien alphabet order.

LeetCode 952: Largest Component Size by Common Factor

A clear explanation of solving Largest Component Size by Common Factor using prime factorization and union find.

LeetCode 951: Flip Equivalent Binary Trees

A clear explanation of checking whether two binary trees are equivalent after swapping left and right children at any number of nodes.

LeetCode 850: Rectangle Area II

A clear explanation of the Rectangle Area II problem using sweep line and merged active y-intervals.

LeetCode 849: Maximize Distance to Closest Person

A clear explanation of the Maximize Distance to Closest Person problem using gaps between occupied seats.

LeetCode 848: Shifting Letters

A clear explanation of the Shifting Letters problem using suffix sums and modulo arithmetic.

LeetCode 847: Shortest Path Visiting All Nodes

A clear explanation of the Shortest Path Visiting All Nodes problem using multi-source BFS and bitmask state compression.

LeetCode 846: Hand of Straights

A clear explanation of the Hand of Straights problem using sorting, frequency counting, and greedy grouping.

LeetCode 845: Longest Mountain in Array

A clear explanation of the Longest Mountain in Array problem using peak detection and two-pointer expansion.

LeetCode 844: Backspace String Compare

A clear explanation of the Backspace String Compare problem using stack simulation and an O(1) space two-pointer scan.

LeetCode 843: Guess the Word

A clear explanation of the Guess the Word interactive problem using candidate filtering and minimax-style guessing.

LeetCode 842: Split Array into Fibonacci Sequence

A clear explanation of the Split Array into Fibonacci Sequence problem using backtracking, leading-zero checks, and 32-bit integer limits.

LeetCode 841: Keys and Rooms

A clear explanation of the Keys and Rooms problem using graph traversal from room 0.

LeetCode 840: Magic Squares In Grid

A clear explanation of the Magic Squares In Grid problem using fixed-size subgrid validation.

LeetCode 839: Similar String Groups

A clear explanation of the Similar String Groups problem using graph connectivity and union-find.

LeetCode 838: Push Dominoes

A clear explanation of the Push Dominoes problem using force propagation and a two-pass scan.

LeetCode 837: New 21 Game

A clear explanation of the New 21 Game problem using probability dynamic programming and a sliding window sum.

LeetCode 836: Rectangle Overlap

A clear explanation of the Rectangle Overlap problem using axis projections and positive intersection area.

LeetCode 835: Image Overlap

A clear explanation of the Image Overlap problem using translation vectors and frequency counting.

LeetCode 834: Sum of Distances in Tree

A clear explanation of the Sum of Distances in Tree problem using tree DP, subtree sizes, and rerooting.

LeetCode 833: Find And Replace in String

A clear explanation of the Find And Replace in String problem using simultaneous replacement, source matching, and a replacement map.

LeetCode 832: Flipping an Image

A clear explanation of the Flipping an Image problem using row reversal, bit inversion, and an in-place two-pointer method.

LeetCode 831: Masking Personal Information

A clear explanation of the Masking Personal Information problem using string parsing and format-specific masking rules.

LeetCode 830: Positions of Large Groups

A clear explanation of the Positions of Large Groups problem using a simple two-pointer scan.

LeetCode 829: Consecutive Numbers Sum

A clear explanation of the Consecutive Numbers Sum problem using arithmetic series formulas and divisibility analysis.

LeetCode 828: Count Unique Characters of All Substrings of a Given String

A clear explanation of Count Unique Characters of All Substrings using contribution counting with previous and next occurrences.

LeetCode 827: Making A Large Island

A clear explanation of the Making A Large Island problem using connected component labeling and island size lookup.

LeetCode 826: Most Profit Assigning Work

A clear explanation of the Most Profit Assigning Work problem using sorting, greedy choice, and two pointers.

LeetCode 924: Minimize Malware Spread

A clear explanation of minimizing malware spread by analyzing connected components with Union Find.

LeetCode 923: 3Sum With Multiplicity

A clear explanation of counting index triplets with duplicate values using frequency counts and combinatorics.

LeetCode 922: Sort Array By Parity II

A clear explanation of placing even numbers at even indices and odd numbers at odd indices using two pointers.

LeetCode 921: Minimum Add to Make Parentheses Valid

A clear explanation of making a parentheses string valid using greedy counting.

LeetCode 920: Number of Music Playlists

A clear explanation of counting valid music playlists using dynamic programming over playlist length and unique songs used.

LeetCode 919: Complete Binary Tree Inserter

A clear explanation of maintaining a complete binary tree inserter using level-order indexing.

LeetCode 918: Maximum Sum Circular Subarray

A clear explanation of finding the maximum circular subarray sum using Kadane's algorithm.

LeetCode 917: Reverse Only Letters

A clear explanation of reversing only English letters while keeping all non-letter characters fixed.

LeetCode 916: Word Subsets

A clear explanation of finding universal words by merging character frequency requirements from words2.

LeetCode 915: Partition Array into Disjoint Intervals

A clear explanation of finding the smallest left partition using prefix maximums and suffix minimums.

LeetCode 914: X of a Kind in a Deck of Cards

A clear explanation of checking whether card counts share a common group size using the greatest common divisor.

LeetCode 913: Cat and Mouse

A clear explanation of Cat and Mouse using game states, reverse BFS, and topological propagation.

LeetCode 912: Sort an Array

A clear explanation of sorting an array without built-in sorting using merge sort.

LeetCode 911: Online Election

A clear explanation of Online Election using preprocessing and binary search over vote times.

LeetCode 910: Smallest Range II

A clear explanation of minimizing the array range after adding either +k or -k to every element.

LeetCode 909: Snakes and Ladders

A clear explanation of Snakes and Ladders using breadth-first search over board squares.

LeetCode 908: Smallest Range I

A clear explanation of minimizing an array score after each value can move by at most k.

LeetCode 907: Sum of Subarray Minimums

A clear explanation of summing subarray minimums using a monotonic stack and contribution counting.

LeetCode 906: Super Palindromes

A clear explanation of counting super-palindromes by generating palindromic roots and checking their squares.

LeetCode 905: Sort Array By Parity

A clear explanation of sorting an array by parity using a two-pointer partition method.

LeetCode 904: Fruit Into Baskets

A clear explanation of Fruit Into Baskets using a sliding window with at most two distinct fruit types.

LeetCode 903: Valid Permutations for DI Sequence

A clear explanation of counting valid DI permutations using dynamic programming and prefix sums.

LeetCode 902: Numbers At Most N Given Digit Set

A clear explanation of counting numbers less than or equal to N using digit-by-digit construction and combinatorics.

LeetCode 901: Online Stock Span

A clear explanation of Online Stock Span using a monotonic decreasing stack with accumulated spans.

LeetCode 900: RLE Iterator

A clear explanation of designing an iterator over a run-length encoded sequence without expanding it.

LeetCode 899: Orderly Queue

A clear explanation of finding the lexicographically smallest string after queue operations using rotation and sorting.

LeetCode 898: Bitwise ORs of Subarrays

A clear explanation of counting distinct bitwise OR results from all non-empty subarrays using rolling sets.

LeetCode 897: Increasing Order Search Tree

A clear explanation of rearranging a binary search tree into an increasing right-only tree using inorder traversal.

LeetCode 896: Monotonic Array

A clear explanation of checking whether an array is monotonic using one pass and direction flags.

LeetCode 895: Maximum Frequency Stack

A clear explanation of designing a stack that pops the most frequent value, breaking ties by most recent insertion.

LeetCode 894: All Possible Full Binary Trees

A clear explanation of generating all full binary trees with n nodes using recursion and memoization.

LeetCode 893: Groups of Special-Equivalent Strings

A clear explanation of counting special-equivalent string groups by building canonical signatures from even and odd positions.

LeetCode 892: Surface Area of 3D Shapes

A clear explanation of computing the exposed surface area of stacked cubes by adding tower area and subtracting shared faces.

LeetCode 891: Sum of Subsequence Widths

A clear explanation of summing subsequence widths by sorting and counting each element as a maximum and minimum.

LeetCode 890: Find and Replace Pattern

A clear explanation of finding words that match a pattern using bijective character mapping.

LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal

A clear explanation of reconstructing a binary tree from preorder and postorder traversals using recursion and index ranges.

LeetCode 888: Fair Candy Swap

A clear explanation of finding one candy box swap that makes Alice and Bob have equal total candies.

LeetCode 887: Super Egg Drop

A clear explanation of finding the minimum worst-case number of moves using dynamic programming over eggs and moves.

LeetCode 886: Possible Bipartition

A clear explanation of checking whether people can be split into two groups using graph coloring and bipartite graph detection.

LeetCode 885: Spiral Matrix III

A clear explanation of generating grid coordinates in an outward clockwise spiral using simulation.

LeetCode 884: Uncommon Words from Two Sentences

A clear explanation of finding uncommon words by counting word frequencies across both sentences.

LeetCode 883: Projection Area of 3D Shapes

A clear explanation of computing the projection areas of stacked cubes from top, front, and side views.

LeetCode 882: Reachable Nodes In Subdivided Graph

A clear explanation of counting reachable original and subdivided nodes using Dijkstra's shortest path algorithm.

LeetCode 881: Boats to Save People

A clear explanation of minimizing rescue boats using sorting, greedy choice, and two pointers.

LeetCode 880: Decoded String at Index

A clear explanation of finding the kth character in a decoded string without building the full decoded string.

LeetCode 879: Profitable Schemes

A clear explanation of counting profitable crime schemes using 0/1 knapsack dynamic programming with members and profit states.

LeetCode 878: Nth Magical Number

A clear explanation of finding the nth magical number using binary search, greatest common divisor, least common multiple, and inclusion-exclusion.

LeetCode 877: Stone Game

A clear explanation of the Stone Game problem using game theory and interval dynamic programming.

LeetCode 876: Middle of the Linked List

A clear explanation of finding the middle node of a singly linked list using slow and fast pointers.

LeetCode 625: Minimum Factorization

A clear explanation of Minimum Factorization using greedy digit factors from 9 down to 2.

LeetCode 624: Maximum Distance in Arrays

A clear explanation of Maximum Distance in Arrays using sorted endpoints and a greedy scan.

LeetCode 623: Add One Row to Tree

A clear explanation of Add One Row to Tree using tree traversal and careful subtree reconnection.

LeetCode 622: Design Circular Queue

A clear explanation of Design Circular Queue using a fixed array, a front pointer, and a size counter.

LeetCode 621: Task Scheduler

A clear explanation of Task Scheduler using frequency counting and the greedy block formula.

LeetCode 250: Count Univalue Subtrees

A clear explanation of counting uni-value subtrees using post-order DFS.

LeetCode 249: Group Shifted Strings

A clear explanation of grouping strings by their shifting sequence using normalized hash keys.

LeetCode 248: Strobogrammatic Number III

A clear explanation of counting strobogrammatic numbers in a string range using recursive generation and range filtering.

LeetCode 247: Strobogrammatic Number II

A clear explanation of generating all strobogrammatic numbers of length n using recursion from the inside out.

LeetCode 246: Strobogrammatic Number

A clear explanation of the Strobogrammatic Number problem using digit rotation rules and two pointers.

LeetCode 245: Shortest Word Distance III

A clear explanation of the Shortest Word Distance III problem, including the special case where both target words are the same.

LeetCode 244: Shortest Word Distance II

A clear explanation of the Shortest Word Distance II problem using preprocessing and two pointers.

LeetCode 243: Shortest Word Distance

A clear explanation of the Shortest Word Distance problem using one pass and the latest seen indices of both words.

LeetCode 1000: Minimum Cost to Merge Stones

A clear explanation of merging consecutive stone piles with minimum cost using interval dynamic programming.

LeetCode 999: Available Captures for Rook

A clear explanation of counting how many pawns a rook can capture by scanning four directions on a chessboard.

LeetCode 998: Maximum Binary Tree II

A clear explanation of inserting a value into a maximum binary tree by following the right spine.

LeetCode 997: Find the Town Judge

A clear explanation of identifying the town judge using trust indegree and outdegree counts.

LeetCode 996: Number of Squareful Arrays

A clear explanation of counting unique permutations where every adjacent pair sums to a perfect square using backtracking.

LeetCode 995: Minimum Number of K Consecutive Bit Flips

A clear explanation of making all bits equal to 1 using greedy left-to-right flips and a sliding window flip parity.

LeetCode 994: Rotting Oranges

A clear explanation of finding the minimum time for all oranges to rot using multi-source BFS.

LeetCode 993: Cousins in Binary Tree

A clear explanation of checking whether two binary tree nodes are cousins using BFS with parent tracking.

LeetCode 992: Subarrays with K Different Integers

A clear explanation of counting subarrays with exactly k distinct integers using the at-most-k sliding window trick.

LeetCode 991: Broken Calculator

A clear explanation of finding the minimum operations by working backward from target to startValue.

LeetCode 990: Satisfiability of Equality Equations

A clear explanation of checking equality and inequality constraints using union-find.

LeetCode 989: Add to Array-Form of Integer

A clear explanation of adding an integer to an array-form number using digit-by-digit simulation.

LeetCode 988: Smallest String Starting From Leaf

A clear explanation of finding the lexicographically smallest leaf-to-root string in a binary tree using DFS.

LeetCode 987: Vertical Order Traversal of a Binary Tree

A clear explanation of vertical tree traversal using coordinates, DFS, sorting, and column grouping.

LeetCode 986: Interval List Intersections

A clear explanation of finding intersections between two sorted disjoint interval lists using two pointers.

LeetCode 985: Sum of Even Numbers After Queries

A clear explanation of maintaining the sum of even numbers after each array update.

LeetCode 984: String Without AAA or BBB

A clear explanation of constructing a string with exact counts of a and b while avoiding three equal consecutive characters.

LeetCode 983: Minimum Cost For Tickets

A clear explanation of finding the cheapest way to cover all travel days using dynamic programming.

LeetCode 982: Triples with Bitwise AND Equal To Zero

A clear explanation of counting ordered triples whose bitwise AND is zero using pairwise AND counts.

LeetCode 981: Time Based Key-Value Store

A clear explanation of designing a time-based key-value store using a hash map and binary search.

LeetCode 980: Unique Paths III

A clear explanation of counting all paths from start to end that visit every non-obstacle square exactly once using backtracking.

LeetCode 979: Distribute Coins in Binary Tree

A clear explanation of balancing coins in a binary tree using postorder DFS and subtree coin balance.

LeetCode 978: Longest Turbulent Subarray

A clear explanation of finding the longest subarray whose adjacent comparisons alternate between greater-than and less-than.

LeetCode 977: Squares of a Sorted Array

A clear explanation of sorting squared values from a sorted array using two pointers.

LeetCode 976: Largest Perimeter Triangle

A clear explanation of finding the largest valid triangle perimeter using sorting and a greedy scan.

LeetCode 875: Koko Eating Bananas

A clear explanation of finding the minimum banana-eating speed using binary search on the answer.

LeetCode 874: Walking Robot Simulation

A clear explanation of simulating robot movement on an infinite grid using direction vectors and obstacle lookup.

LeetCode 873: Length of Longest Fibonacci Subsequence

A clear explanation of finding the longest Fibonacci-like subsequence using dynamic programming and value-to-index lookup.

LeetCode 872: Leaf-Similar Trees

A clear explanation of comparing two binary trees by collecting their leaf value sequences with DFS.

LeetCode 871: Minimum Number of Refueling Stops

A clear explanation of minimizing refueling stops using a greedy max heap over reachable stations.

LeetCode 870: Advantage Shuffle

A clear explanation of maximizing the advantage of one array over another using sorting, greedy matching, and two pointers.

LeetCode 869: Reordered Power of 2

A clear explanation of checking whether the digits of a number can be reordered to form a power of two using digit frequency signatures.

LeetCode 868: Binary Gap

A clear explanation of finding the maximum distance between adjacent set bits in a binary representation.

LeetCode 867: Transpose Matrix

A clear explanation of transposing a matrix by swapping row and column indices.

LeetCode 866: Prime Palindrome

A clear explanation of finding the smallest prime palindrome greater than or equal to n by generating odd-length palindromes and testing primality.

LeetCode 865: Smallest Subtree with all the Deepest Nodes

A clear explanation of finding the smallest subtree that contains all deepest nodes using bottom-up DFS.

LeetCode 864: Shortest Path to Get All Keys

A clear explanation of finding the minimum moves to collect all keys in a grid using BFS with key bitmasks.

LeetCode 863: All Nodes Distance K in Binary Tree

A clear explanation of finding all binary tree nodes at distance k from a target node by treating the tree as an undirected graph.

LeetCode 862: Shortest Subarray with Sum at Least K

A clear explanation of finding the shortest non-empty subarray with sum at least k using prefix sums and a monotonic deque.

LeetCode 861: Score After Flipping Matrix

A clear explanation of maximizing a binary matrix score using greedy row and column flips.

LeetCode 860: Lemonade Change

A clear explanation of Lemonade Change using greedy simulation and bill counting.

LeetCode 859: Buddy Strings

A clear explanation of checking whether one swap in a string can make it equal to another string.

LeetCode 858: Mirror Reflection

A clear explanation of Mirror Reflection using room unfolding, least common multiples, and parity.

LeetCode 857: Minimum Cost to Hire K Workers

A clear explanation of hiring exactly k workers with minimum total cost using wage-to-quality ratios, sorting, and a max heap.

LeetCode 856: Score of Parentheses

A clear explanation of scoring a balanced parentheses string using depth counting.

LeetCode 855: Exam Room

A clear explanation of simulating an exam room by maintaining occupied seats in sorted order.

LeetCode 854: K-Similar Strings

A clear explanation of finding the minimum number of swaps needed to transform one anagram string into another using BFS.

LeetCode 853: Car Fleet

A clear explanation of counting car fleets by sorting cars by position and tracking arrival times.

LeetCode 852: Peak Index in a Mountain Array

A clear explanation of finding the peak index in a mountain array using binary search.

LeetCode 851: Loud and Rich

A clear explanation of Loud and Rich using graph traversal, DFS, and memoization.

LeetCode 950: Reveal Cards In Increasing Order

A clear explanation of solving Reveal Cards In Increasing Order using sorting and queue simulation over indices.

LeetCode 949: Largest Time for Given Digits

A clear explanation of solving Largest Time for Given Digits by checking all permutations of four digits.

LeetCode 948: Bag of Tokens

A clear explanation of solving Bag of Tokens using sorting, greedy choices, and two pointers.

LeetCode 947: Most Stones Removed with Same Row or Column

A clear explanation of solving Most Stones Removed with Same Row or Column using connected components and union-find.

LeetCode 946: Validate Stack Sequences

A clear explanation of solving Validate Stack Sequences by simulating stack push and pop operations.

LeetCode 945: Minimum Increment to Make Array Unique

A clear explanation of solving Minimum Increment to Make Array Unique by sorting and greedily assigning the next available value.

LeetCode 944: Delete Columns to Make Sorted

A clear explanation of solving Delete Columns to Make Sorted by checking each column independently.

LeetCode 943: Find the Shortest Superstring

A clear explanation of solving Find the Shortest Superstring using pairwise overlaps and bitmask dynamic programming.

LeetCode 942: DI String Match

A clear explanation of solving DI String Match using a greedy two-pointer construction.

LeetCode 941: Valid Mountain Array

A clear explanation of solving Valid Mountain Array by walking up the increasing slope and then down the decreasing slope.

LeetCode 940: Distinct Subsequences II

A clear explanation of solving Distinct Subsequences II using dynamic programming and last occurrence tracking.

LeetCode 939: Minimum Area Rectangle

A clear explanation of solving Minimum Area Rectangle using diagonal point pairs and constant-time point lookup.

LeetCode 938: Range Sum of BST

A clear explanation of solving Range Sum of BST using DFS with binary search tree pruning.

LeetCode 937: Reorder Data in Log Files

A clear explanation of solving Reorder Data in Log Files using custom sorting and stable handling of digit logs.

LeetCode 936: Stamping The Sequence

A clear explanation of solving Stamping The Sequence using reverse simulation and BFS-style processing.

LeetCode 935: Knight Dialer

A clear explanation of solving Knight Dialer using dynamic programming over the phone keypad graph.

LeetCode 934: Shortest Bridge

A clear explanation of solving Shortest Bridge using DFS to mark one island and BFS to expand toward the other island.

LeetCode 933: Number of Recent Calls

A clear explanation of solving Number of Recent Calls using a queue as a sliding time window.

LeetCode 932: Beautiful Array

A clear explanation of solving Beautiful Array using divide and conquer with odd and even transformations.

LeetCode 931: Minimum Falling Path Sum

A clear explanation of solving Minimum Falling Path Sum using dynamic programming over matrix rows.

LeetCode 930: Binary Subarrays With Sum

A clear explanation of solving Binary Subarrays With Sum using prefix sums and a frequency map.

LeetCode 929: Unique Email Addresses

A clear explanation of solving Unique Email Addresses using string normalization and a hash set.

LeetCode 928: Minimize Malware Spread II

A clear explanation of solving Minimize Malware Spread II by removing each infected node and simulating the final malware spread.

LeetCode 927: Three Equal Parts

A clear explanation of solving Three Equal Parts by counting ones, locating the three binary patterns, and comparing them in one pass.

LeetCode 926: Flip String to Monotone Increasing

A clear explanation of solving Flip String to Monotone Increasing with a one-pass dynamic programming approach.

LeetCode 825: Friends Of Appropriate Ages

A counting solution for computing how many directed friend requests are allowed by age rules.

LeetCode 824: Goat Latin

A string simulation solution for converting each word in a sentence into Goat Latin.

LeetCode 823: Binary Trees With Factors

A dynamic programming solution for counting binary trees where every non-leaf node is the product of its children.

LeetCode 822: Card Flipping Game

A hash set solution for finding the smallest number that can be hidden from all front-facing cards.

LeetCode 821: Shortest Distance to a Character

A two-pass solution for computing the shortest distance from each index to the nearest occurrence of a target character.

LeetCode 820: Short Encoding of Words

A suffix-removal solution for finding the shortest reference string that can encode every word.

LeetCode 819: Most Common Word

A hash map and string parsing solution for finding the most frequent non-banned word in a paragraph.

LeetCode 818: Race Car

A dynamic programming solution for finding the shortest instruction sequence that drives a race car to the target position.

LeetCode 817: Linked List Components

A hash set and linked list traversal solution for counting consecutive components whose values appear in nums.

LeetCode 816: Ambiguous Coordinates

An enumeration solution for reconstructing all valid coordinate pairs after commas, spaces, and decimal points were removed.

LeetCode 815: Bus Routes

A BFS solution for finding the minimum number of buses needed to travel from a source stop to a target stop.

LeetCode 814: Binary Tree Pruning

A postorder DFS solution for removing every binary tree subtree that does not contain a 1.

LeetCode 813: Largest Sum of Averages

A dynamic programming and prefix sum solution for partitioning an array into adjacent groups with maximum total average.

LeetCode 812: Largest Triangle Area

A geometry solution for finding the largest triangle area by checking every triplet of points with the cross product formula.

LeetCode 811: Subdomain Visit Count

A hash map solution for accumulating visit counts across domains and all of their parent subdomains.

LeetCode 810: Chalkboard XOR Game

A math and bit manipulation solution for deciding whether Alice wins the XOR removal game.

LeetCode 809: Expressive Words

A two-pointer group comparison solution for counting how many words can be stretched to match a target string.

LeetCode 808: Soup Servings

A probability dynamic programming solution for computing whether soup A empties before soup B, with an early return for large input.

LeetCode 807: Max Increase to Keep City Skyline

A greedy solution for increasing building heights as much as possible while preserving every skyline view.

LeetCode 806: Number of Lines To Write String

A simple simulation solution for counting how many 100-pixel lines are needed to write a string.

LeetCode 805: Split Array With Same Average

A dynamic programming solution for deciding whether an array can be split into two non-empty groups with the same average.

LeetCode 804: Unique Morse Code Words

A set-based solution for counting how many different Morse code transformations appear among a list of words.

LeetCode 803: Bricks Falling When Hit

A reverse simulation and union-find solution for counting how many bricks fall after each hit.

LeetCode 802: Find Eventual Safe States

A graph traversal solution for finding all nodes that cannot reach a directed cycle.

LeetCode 801: Minimum Swaps To Make Sequences Increasing

A dynamic programming solution for finding the minimum number of same-index swaps needed to make two arrays strictly increasing.

LeetCode 800: Similar RGB Color

A clear explanation of finding the closest shorthand RGB color by rounding each color channel to the nearest repeated hexadecimal pair.

LeetCode 799: Champagne Tower

A clear explanation of simulating overflow in a champagne glass pyramid using dynamic programming.

LeetCode 798: Smallest Rotation with Highest Score

A clear explanation of finding the smallest rotation with maximum score using a difference array.

LeetCode 797: All Paths From Source to Target

A clear explanation of finding every path from node 0 to node n - 1 in a directed acyclic graph using DFS and backtracking.

LeetCode 796: Rotate String

A clear explanation of checking whether one string can become another by repeated left rotations.

LeetCode 795: Number of Subarrays with Bounded Maximum

A clear explanation of counting contiguous subarrays whose maximum value lies inside a given inclusive range.

LeetCode 794: Valid Tic-Tac-Toe State

A clear explanation of validating whether a Tic-Tac-Toe board can occur in a legal game.

LeetCode 793: Preimage Size of Factorial Zeroes Function

A clear explanation of finding how many integers have exactly k trailing zeroes in their factorial.

LeetCode 792: Number of Matching Subsequences

A clear explanation of counting how many words are subsequences of a string using waiting queues.

LeetCode 791: Custom Sort String

A clear explanation of rearranging a string so that selected characters follow a custom order.

LeetCode 790: Domino and Tromino Tiling

A clear explanation of counting tilings of a 2 x n board using dominoes and L-shaped trominoes with dynamic programming.

LeetCode 789: Escape The Ghosts

A clear explanation of deciding whether escape is possible by comparing Manhattan distances to the target.

LeetCode 788: Rotated Digits

A clear explanation of counting good numbers after rotating every digit by 180 degrees.

LeetCode 787: Cheapest Flights Within K Stops

A clear explanation of finding the cheapest flight route with at most k stops using bounded Bellman-Ford relaxation.

LeetCode 786: K-th Smallest Prime Fraction

A clear explanation of finding the kth smallest fraction from a sorted array using a min-heap.

LeetCode 785: Is Graph Bipartite?

A clear explanation of checking whether an undirected graph can be split into two independent sets using graph coloring.

LeetCode 784: Letter Case Permutation

A clear explanation of generating all strings formed by independently changing each letter to lowercase or uppercase.

LeetCode 783: Minimum Distance Between BST Nodes

A clear explanation of finding the minimum difference between any two nodes in a BST using inorder traversal.

LeetCode 782: Transform to Chessboard

A clear explanation of transforming a binary board into a chessboard using feasibility checks and minimum row and column swaps.

LeetCode 781: Rabbits in Forest

A clear explanation of finding the minimum possible number of rabbits using counting and greedy grouping.

LeetCode 780: Reaching Points

A clear explanation of checking whether one point can reach another by working backward with modulo.

LeetCode 779: K-th Symbol in Grammar

A clear explanation of finding the kth symbol in the grammar sequence using recursion and the parent-child relationship.

LeetCode 778: Swim in Rising Water

A clear explanation of finding the minimum time to reach the bottom-right cell using a priority queue and minimax path reasoning.

LeetCode 777: Swap Adjacent in LR String

A clear explanation of validating string transformation using two pointers and movement constraints.

LeetCode 776: Split BST

A clear explanation of splitting a binary search tree into two BSTs using recursion and pointer rewiring.

LeetCode 775: Global and Local Inversions

A clear explanation of checking whether every global inversion is also a local inversion using distance constraints.

LeetCode 774: Minimize Max Distance to Gas Station

A clear explanation of minimizing the largest adjacent gas-station distance using binary search on the answer.

LeetCode 773: Sliding Puzzle

A clear explanation of solving the 2 x 3 sliding puzzle using breadth-first search over board states.

LeetCode 772: Basic Calculator III

A clear explanation of evaluating arithmetic expressions with parentheses, precedence, and integer division.

LeetCode 771: Jewels and Stones

A clear explanation of counting how many stones are jewels using a hash set for fast membership checks.

LeetCode 770: Basic Calculator IV

A clear explanation of simplifying algebraic expressions by parsing, substituting variables, and combining polynomial terms.

LeetCode 769: Max Chunks To Make Sorted

A clear explanation of splitting a permutation into the maximum number of chunks using prefix maximums.

LeetCode 768: Max Chunks To Make Sorted II

A clear explanation of splitting an array into the maximum number of chunks so sorting each chunk gives the fully sorted array.

LeetCode 767: Reorganize String

A clear explanation of rearranging characters so no two adjacent characters are equal using a greedy max heap.

LeetCode 766: Toeplitz Matrix

A clear explanation of checking whether every top-left to bottom-right diagonal in a matrix has the same value.

LeetCode 765: Couples Holding Hands

A clear explanation of minimizing swaps so every couple sits together using greedy position tracking.

LeetCode 764: Largest Plus Sign

A clear explanation of finding the largest plus sign in a mined grid using four directional dynamic programming scans.

LeetCode 763: Partition Labels

A clear explanation of partitioning a string into the maximum number of parts so each character appears in at most one part.

LeetCode 762: Prime Number of Set Bits in Binary Representation

A clear explanation of counting numbers whose binary representation has a prime number of set bits.

LeetCode 761: Special Binary String

A clear explanation of making a special binary string lexicographically largest using recursive decomposition and sorting.

LeetCode 760: Find Anagram Mappings

A clear explanation of mapping each element in one array to a matching index in its anagram using a hash map.

LeetCode 759: Employee Free Time

A clear explanation of finding common free time by merging all employee busy intervals and returning the gaps.

LeetCode 758: Bold Words in String

A clear explanation of marking matching substrings and merging overlapping bold ranges.

LeetCode 757: Set Intersection Size At Least Two

A clear explanation of solving interval intersection constraints using greedy sorting and minimal point selection.

LeetCode 756: Pyramid Transition Matrix

A clear explanation of solving Pyramid Transition Matrix using backtracking and memoization over pyramid rows.

LeetCode 755: Pour Water

A clear explanation of simulating water droplets over an elevation map by checking left first, then right.

LeetCode 754: Reach a Number

A clear explanation of reaching a target on a number line using cumulative sums and parity.

LeetCode 753: Cracking the Safe

A clear explanation of Cracking the Safe using a de Bruijn sequence and depth-first search over password states.

LeetCode 752: Open the Lock

A clear explanation of solving Open the Lock using breadth-first search over lock states.

LeetCode 751: IP to CIDR

A clear explanation of converting a range of IPv4 addresses into the shortest list of CIDR blocks using greedy bit manipulation.

LeetCode 725: Split Linked List in Parts

A clear explanation of splitting a linked list into k consecutive parts with sizes as equal as possible.

LeetCode 724: Find Pivot Index

A clear explanation of finding the leftmost pivot index using prefix sums and a running left sum.

LeetCode 723: Candy Crush

A clear explanation of restoring a Candy Crush board to a stable state using repeated marking, crushing, and gravity simulation.

LeetCode 722: Remove Comments

A clear explanation of removing line comments and block comments from source code using a state machine.

LeetCode 721: Accounts Merge

A clear explanation of merging accounts that share emails using union find and sorted email groups.

LeetCode 720: Longest Word in Dictionary

A clear explanation of finding the longest buildable word using sorting and a hash set.

LeetCode 719: Find K-th Smallest Pair Distance

A clear explanation of finding the kth smallest pair distance using sorting, binary search on the answer, and a two-pointer count.

LeetCode 718: Maximum Length of Repeated Subarray

A clear explanation of finding the longest common contiguous subarray using dynamic programming.

LeetCode 717: 1-bit and 2-bit Characters

A clear explanation of determining whether the last character must be a one-bit character using greedy parsing.

LeetCode 716: Max Stack

A clear explanation of designing a stack that supports push, pop, top, peekMax, and popMax.

LeetCode 715: Range Module

A clear explanation of designing a range module that can add, query, and remove half-open intervals.

LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee

A clear explanation of maximizing stock trading profit with unlimited transactions and a fixed transaction fee using dynamic programming.

LeetCode 713: Subarray Product Less Than K

A clear explanation of counting contiguous subarrays whose product is less than k using a sliding window.

LeetCode 712: Minimum ASCII Delete Sum for Two Strings

A clear explanation of using dynamic programming to minimize the ASCII cost of deletions needed to make two strings equal.

LeetCode 711: Number of Distinct Islands II

A clear explanation of counting distinct island shapes under rotation and reflection using normalization and geometric transformations.

LeetCode 710: Random Pick with Blacklist

A clear explanation of selecting a uniformly random integer while excluding blacklisted values using remapping and hashing.

LeetCode 709: To Lower Case

A clear explanation of converting uppercase ASCII letters to lowercase by scanning the string once.

LeetCode 708: Insert into a Sorted Circular Linked List

A clear explanation of inserting a value into a sorted circular linked list while preserving the circular sorted order.

LeetCode 707: Design Linked List

A clear explanation of implementing a linked list from scratch using nodes, a dummy head, and a size counter.

LeetCode 706: Design HashMap

A clear explanation of designing a hash map without using built-in hash table libraries.

LeetCode 705: Design HashSet

A clear explanation of designing a hash set without using built-in hash table libraries.

LeetCode 704: Binary Search

A clear explanation of searching for a target in a sorted array using binary search.

LeetCode 703: Kth Largest Element in a Stream

A clear explanation of maintaining the kth largest element in a stream using a fixed-size min heap.

LeetCode 702: Search in a Sorted Array of Unknown Size

A clear explanation of searching in a sorted array when the array length is hidden behind an ArrayReader interface.

LeetCode 701: Insert into a Binary Search Tree

A clear explanation of inserting a value into a binary search tree using recursive and iterative traversal.

LeetCode 750: Number Of Corner Rectangles

Count axis-aligned rectangles whose four corners are 1 using column-pair frequency counting.

LeetCode 749: Contain Virus

Simulate virus containment by repeatedly quarantining the most dangerous infected region and spreading the remaining regions.

LeetCode 748: Shortest Completing Word

Find the shortest word that contains all required license plate letters using frequency counting.

LeetCode 747: Largest Number At Least Twice of Others

Find whether the maximum element is at least twice every other element using a single linear scan.

LeetCode 746: Min Cost Climbing Stairs

Find the minimum cost to reach the top of the staircase using dynamic programming.

LeetCode 745: Prefix and Suffix Search

Support fast prefix and suffix queries by indexing every prefix-suffix combination with the largest word index.

LeetCode 744: Find Smallest Letter Greater Than Target

Use binary search to find the smallest character strictly greater than the target with wraparound handling.

LeetCode 743: Network Delay Time

Find the time needed for a signal to reach all nodes in a directed weighted graph using Dijkstra's algorithm.

LeetCode 742: Closest Leaf in a Binary Tree

Find the nearest leaf to a target node by converting the tree into an undirected graph and running breadth-first search.

LeetCode 741: Cherry Pickup

Maximize cherries collected on a round trip by converting the problem into two simultaneous forward paths and solving with dynamic programming.

LeetCode 740: Delete and Earn

Transform the problem into House Robber dynamic programming by grouping equal values into total points.

LeetCode 739: Daily Temperatures

Find how many days each temperature must wait for a warmer future day using a monotonic stack.

LeetCode 738: Monotone Increasing Digits

Find the largest number less than or equal to n whose digits are monotone increasing using a greedy digit adjustment.

LeetCode 737: Sentence Similarity II

Check sentence similarity with transitive word relationships using union-find.

LeetCode 736: Parse Lisp Expression

Evaluate a Lisp-like expression with integers, variables, let bindings, addition, multiplication, and lexical scope.

LeetCode 735: Asteroid Collision

Simulate asteroid collisions using a stack that keeps the surviving asteroids in order.

LeetCode 734: Sentence Similarity

Check whether two word arrays are sentence-similar using a hash set of symmetric similar word pairs.

LeetCode 733: Flood Fill

Recolor the connected component containing the starting pixel using depth-first search.

LeetCode 732: My Calendar III

Track the maximum number of overlapping calendar events using a sweep line difference map.

LeetCode 731: My Calendar II

Allow double bookings but reject triple bookings using overlap interval tracking.

LeetCode 730: Count Different Palindromic Subsequences

Count distinct non-empty palindromic subsequences using interval dynamic programming and duplicate handling.

LeetCode 729: My Calendar I

Implement a calendar that accepts a booking only when it does not overlap with any existing booking.

LeetCode 728: Self Dividing Numbers

Check each number in a range by extracting its digits and testing whether every digit divides the original number.

LeetCode 727: Minimum Window Subsequence

Find the shortest substring of s1 that contains s2 as a subsequence using dynamic programming.

LeetCode 726: Number of Atoms

Parse a chemical formula with nested parentheses, atom names, and multipliers using recursive descent.

LeetCode 197: Rising Temperature

A clear explanation of the Rising Temperature SQL problem using a self join and date comparison.

LeetCode 196: Delete Duplicate Emails

A clear explanation of the Delete Duplicate Emails SQL problem using DELETE with a self join.

LeetCode 195: Tenth Line

A clear explanation of the Tenth Line shell problem using awk, sed, head, and tail.

LeetCode 194: Transpose File

A clear explanation of the Transpose File shell problem using awk to transform rows into columns.

LeetCode 193: Valid Phone Numbers

A clear explanation of the Valid Phone Numbers shell problem using grep and regular expressions.

LeetCode 192: Word Frequency

A clear explanation of the Word Frequency shell problem using Unix text-processing tools.

LeetCode 699: Falling Squares

Simulate falling squares on a number line and track the maximum stack height after each placement.

LeetCode 698: Partition to K Equal Sum Subsets

Decide whether an array can be divided into k non-empty subsets with equal sums using backtracking and pruning.

LeetCode 697: Degree of an Array

Find the shortest contiguous subarray with the same degree as the whole array using frequency counts and first occurrence indices.

LeetCode 696: Count Binary Substrings

Count substrings with equal consecutive groups of 0s and 1s using run lengths.

LeetCode 695: Max Area of Island

Find the largest connected island area in a binary grid using depth-first search.

LeetCode 694: Number of Distinct Islands

Count unique island shapes in a binary grid using DFS and relative coordinates.

LeetCode 693: Binary Number with Alternating Bits

Check whether every adjacent bit in a positive integer's binary representation is different.

LeetCode 692: Top K Frequent Words

Find the k most frequent words using frequency counting and custom sorting by count and lexicographical order.

LeetCode 691: Stickers to Spell Word

Find the minimum number of stickers needed to form a target string using top-down dynamic programming with memoization.

LeetCode 690: Employee Importance

Compute the total importance of an employee and all direct and indirect subordinates using a hash map and depth-first search.

LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays

Find three non-overlapping subarrays of length k with maximum total sum and return the lexicographically smallest starting indices.

LeetCode 688: Knight Probability in Chessboard

Compute the probability that a knight remains on an n x n chessboard after exactly k random moves using dynamic programming.

LeetCode 686: Repeated String Match

Find the minimum number of times one string must be repeated so another string becomes a substring.

LeetCode 685: Redundant Connection II

Find the directed edge to remove so a graph becomes a rooted tree again, handling both cycles and nodes with two parents.

LeetCode 684: Redundant Connection

Find the extra edge in an undirected graph that creates a cycle using Union-Find.

LeetCode 683: K Empty Slots

Find the earliest day when two turned-on bulbs have exactly k turned-off bulbs between them using a sliding window over bloom days.

LeetCode 682: Baseball Game

Simulate a baseball scoring system using a stack to process operations and compute the final score.

LeetCode 681: Next Closest Time

Find the next valid 24-hour time using only the digits from the current time.

LeetCode 680: Valid Palindrome II

Check whether a string can become a palindrome after deleting at most one character using two pointers.

LeetCode 679: 24 Game

Determine whether four numbers can be combined with arithmetic operations and parentheses to produce 24.

LeetCode 678: Valid Parenthesis String

Check whether a string containing parentheses and wildcard stars can be made valid using a greedy range of possible open counts.

LeetCode 677: Map Sum Pairs

Design a map that supports key-value insertion and prefix-sum queries using a hash map and trie.

LeetCode 676: Implement Magic Dictionary

Design a dictionary that can check whether a word can match a stored word after changing exactly one character.

LeetCode 675: Cut Off Trees for Golf Event

A clear explanation of cutting trees in increasing height order using repeated BFS on a grid.

LeetCode 674: Longest Continuous Increasing Subsequence

A clear explanation of finding the longest strictly increasing contiguous subarray using a single scan.

LeetCode 673: Number of Longest Increasing Subsequence

A clear explanation of counting how many longest strictly increasing subsequences exist using dynamic programming.

LeetCode 672: Bulb Switcher II

A clear explanation of counting possible bulb states after pressing four toggle buttons exactly presses times.

LeetCode 671: Second Minimum Node In a Binary Tree

A clear explanation of finding the second minimum value in a special binary tree using DFS.

LeetCode 670: Maximum Swap

A clear explanation of maximizing an integer by swapping at most two digits once.

LeetCode 669: Trim a Binary Search Tree

A clear explanation of trimming a BST so that all remaining node values lie inside a given inclusive range.

LeetCode 668: Kth Smallest Number in Multiplication Table

A clear explanation of finding the kth smallest value in an m by n multiplication table using binary search on answer.

LeetCode 667: Beautiful Arrangement II

A clear explanation of constructing an array with exactly k distinct adjacent differences using a greedy pattern.

LeetCode 666: Path Sum IV

A clear explanation of computing all root-to-leaf path sums from a compact three-digit binary tree encoding.

LeetCode 665: Non-decreasing Array

A clear explanation of checking whether an array can become non-decreasing by modifying at most one element.

LeetCode 664: Strange Printer

A clear explanation of minimizing printer turns using interval dynamic programming.

LeetCode 663: Equal Tree Partition

A clear explanation of checking whether a binary tree can be split into two equal-sum trees by removing one edge.

LeetCode 662: Maximum Width of Binary Tree

A clear explanation of computing the maximum width of a binary tree using level-order traversal and complete-tree indices.

LeetCode 661: Image Smoother

A clear explanation of averaging neighboring pixels in a matrix using direct simulation.

LeetCode 659: Split Array into Consecutive Subsequences

A clear explanation of deciding whether a sorted array can be split into consecutive subsequences of length at least three.

LeetCode 658: Find K Closest Elements

A clear explanation of finding the k closest elements to a target using binary search and a sliding window.

LeetCode 657: Robot Return to Origin

A clear explanation of determining whether a robot returns to the origin after executing movement instructions.

LeetCode 656: Coin Path

A clear explanation of finding the minimum-cost path with bounded jumps, blocked cells, and lexicographic tie-breaking.

LeetCode 655: Print Binary Tree

A clear explanation of formatting a binary tree into a 2D string matrix using tree height and recursive placement.

LeetCode 654: Maximum Binary Tree

A clear explanation of constructing a maximum binary tree recursively using divide and conquer.

LeetCode 653: Two Sum IV - Input is a BST

A clear explanation of finding whether two different nodes in a binary search tree sum to a target value.

LeetCode 652: Find Duplicate Subtrees

A clear explanation of finding duplicate binary tree subtrees using postorder traversal, serialization, and a hash map.

LeetCode 651: 4 Keys Keyboard

A dynamic programming solution for maximizing the number of A characters printed with a limited number of keyboard operations.

LeetCode 650: 2 Keys Keyboard

A dynamic programming and prime factorization solution for finding the minimum operations needed to produce n characters.

LeetCode 649: Dota2 Senate

A queue-based simulation for predicting which party wins after senators ban opponents in turn order.

LeetCode 648: Replace Words

A trie-based solution for replacing each derivative word with the shortest matching root.

LeetCode 647: Palindromic Substrings

A center expansion solution for counting every palindromic substring in a string.

LeetCode 646: Maximum Length of Pair Chain

A greedy interval scheduling solution for finding the longest chain of valid pairs.

LeetCode 645: Set Mismatch

A counting and math solution for finding the duplicated number and the missing number in a corrupted set.

LeetCode 644: Maximum Average Subarray II

A binary search solution for finding the maximum average of any contiguous subarray with length at least k.

LeetCode 643: Maximum Average Subarray I

A sliding window solution for finding the maximum average among all contiguous subarrays of fixed length k.

LeetCode 642: Design Search Autocomplete System

A trie-based design for returning the top three historical sentences for a typed prefix.

LeetCode 641: Design Circular Deque

An array-based circular buffer solution for implementing a fixed-size double-ended queue.

LeetCode 640: Solve the Equation

A string parsing solution for reducing a linear equation into coefficient and constant terms.

LeetCode 639: Decode Ways II

A dynamic programming solution for counting decodings of a digit string with wildcard characters.

LeetCode 638: Shopping Offers

A DFS and memoization solution for finding the minimum cost to satisfy item needs using individual prices and reusable special offers.

LeetCode 637: Average of Levels in Binary Tree

A breadth-first search solution for computing the average value of nodes at each level of a binary tree.

LeetCode 636: Exclusive Time of Functions

A stack-based solution for computing exclusive execution time from nested start and end logs.

LeetCode 635: Design Log Storage System

A design solution for storing timestamped logs and retrieving IDs by inclusive time range at a chosen granularity.

LeetCode 634: Find the Derangement of An Array

A dynamic programming and combinatorics solution for counting permutations with no fixed positions.

LeetCode 633: Sum of Square Numbers

A two-pointer and number theory solution for checking whether an integer can be written as the sum of two square numbers.

LeetCode 632: Smallest Range Covering Elements from K Lists

A heap-based solution for finding the smallest range that contains at least one number from each sorted list.

LeetCode 631: Design Excel Sum Formula

A design solution for a small Excel-like spreadsheet that supports set, get, and dynamic sum formulas.

LeetCode 630: Course Schedule III

A greedy heap solution for taking the maximum number of courses before their deadlines.

LeetCode 629: K Inverse Pairs Array

A dynamic programming solution for counting permutations of 1 to n with exactly k inverse pairs.

LeetCode 628: Maximum Product of Three Numbers

A clear explanation of finding the largest product of three numbers using sorting or constant-space tracking.

LeetCode 617: Merge Two Binary Trees

A recursive tree traversal guide for merging two binary trees node by node.

LeetCode 616: Add Bold Tag in String

A string-marking guide for adding bold tags around all matched words while merging overlapping and adjacent bold regions.

LeetCode 611: Valid Triangle Number

A two-pointer guide for counting triplets that can form valid triangles after sorting the side lengths.

LeetCode 609: Find Duplicate File in System

A hash map guide for grouping file paths by identical file content and returning only duplicate groups.

LeetCode 606: Construct String from Binary Tree

A recursive guide for converting a binary tree into a preorder parenthesized string while preserving the one-to-one mapping between the tree and the string.

LeetCode 605: Can Place Flowers

A greedy guide for determining whether a given number of flowers can be planted without violating the no-adjacent-flowers rule.

LeetCode 604: Design Compressed String Iterator

A guide to implementing a lazy iterator over a run-length encoded string without fully decompressing it.

LeetCode 242: Valid Anagram

A clear explanation of checking whether two strings are anagrams using character frequency counting.

LeetCode 241: Different Ways to Add Parentheses

A clear explanation of generating all possible results from different parenthesizations using divide and conquer recursion.

LeetCode 240: Search a 2D Matrix II

A clear explanation of searching a row-sorted and column-sorted matrix using the top-right corner elimination method.

LeetCode 239: Sliding Window Maximum

A clear explanation of finding the maximum value in every sliding window using a monotonic deque.

LeetCode 238: Product of Array Except Self

A clear explanation of computing each product except self using prefix and suffix products without division.

LeetCode 237: Delete Node in a Linked List

A clear explanation of deleting a node from a singly linked list when only that node is given.

LeetCode 236: Lowest Common Ancestor of a Binary Tree

A clear explanation of finding the lowest common ancestor in a normal binary tree using recursive depth-first search.

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

A clear explanation of finding the lowest common ancestor in a binary search tree using BST ordering properties.

LeetCode 234: Palindrome Linked List

A clear explanation of checking whether a singly linked list is a palindrome using fast and slow pointers plus in-place reversal.

LeetCode 233: Number of Digit One

A detailed explanation of counting how many times digit one appears from 0 to n using positional digit analysis.

LeetCode 232: Implement Queue using Stacks

A detailed explanation of implementing a FIFO queue using two LIFO stacks with amortized constant time operations.

LeetCode 231: Power of Two

A clear explanation of determining whether an integer is a power of two using binary properties and bit manipulation.

LeetCode 230: Kth Smallest Element in a BST

A clear explanation of finding the kth smallest value in a binary search tree using inorder traversal.

LeetCode 229: Majority Element II

A clear explanation of finding all elements that appear more than n/3 times using the extended Boyer-Moore voting algorithm.

LeetCode 228: Summary Ranges

A clear explanation of summarizing a sorted unique integer array into compact consecutive ranges.

LeetCode 227: Basic Calculator II

A detailed explanation of evaluating arithmetic expressions with stack-based parsing and operator precedence.

LeetCode 226: Invert Binary Tree

A clear explanation of inverting a binary tree using recursive depth-first traversal.

LeetCode 175: Combine Two Tables

A clear SQL guide for solving Combine Two Tables using LEFT JOIN.

LeetCode 50: Pow(x, n)

A clear explanation of Pow(x, n) using binary exponentiation to compute powers in logarithmic time.

LeetCode 49: Group Anagrams

A clear explanation of Group Anagrams using a hash map keyed by each word's sorted character signature.

LeetCode 48: Rotate Image

A clear explanation of Rotate Image using in-place matrix transpose and row reversal.

LeetCode 47: Permutations II

A clear explanation of Permutations II using sorting, depth-first search, and duplicate-skipping backtracking.

LeetCode 46: Permutations

A clear explanation of Permutations using depth-first search and backtracking.

LeetCode 45: Jump Game II

A clear explanation of Jump Game II using a greedy range expansion approach to find the minimum number of jumps.

LeetCode 44: Wildcard Matching

A clear explanation of Wildcard Matching using dynamic programming over string and pattern prefixes.

LeetCode 43: Multiply Strings

A clear explanation of Multiply Strings using grade-school multiplication with digit arrays.

LeetCode 42: Trapping Rain Water

A clear explanation of the Trapping Rain Water problem using left and right boundaries, then an optimized two-pointer solution.

LeetCode 41: First Missing Positive

A clear explanation of the First Missing Positive problem using in-place index placement to achieve O(n) time and O(1) extra space.

LeetCode 700: Search in a Binary Search Tree

Search for a target value in a binary search tree and return the subtree rooted at the matching node.

LeetCode 687: Longest Univalue Path

Find the longest path in a binary tree where every node on the path has the same value using depth-first search.

LeetCode 627: Swap Salary

A SQL update solution for swapping all m and f values in the Salary table using a single statement.

LeetCode 626: Exchange Seats

A SQL solution for swapping every pair of adjacent student seats while leaving the final seat unchanged when the row count is odd.

LeetCode 660: Remove 9

A clear explanation of finding the nth positive integer that does not contain the digit 9 using base-9 conversion.

LeetCode 620: Not Boring Movies

A SQL guide for filtering movies with odd IDs and non-boring descriptions, then sorting by rating.

LeetCode 619: Biggest Single Number

A SQL guide for finding the largest number that appears exactly once in a table.

LeetCode 618: Students Report By Geography

A SQL guide for pivoting rows into columns using ranking and conditional aggregation.

LeetCode 615: Average Salary: Departments VS Company

A SQL guide for comparing each department's monthly average salary against the company's monthly average salary.

LeetCode 614: Second Degree Follower

A SQL guide for finding users who both follow someone and have followers, then counting how many followers they have.

LeetCode 613: Shortest Distance in a Line

A SQL guide for finding the minimum distance between any two unique points on the X-axis.

LeetCode 612: Shortest Distance in a Plane

A SQL guide for finding the minimum Euclidean distance between any two points in a 2D plane.

LeetCode 610: Triangle Judgement

A SQL guide for checking whether three side lengths can form a valid triangle using the triangle inequality.

LeetCode 608: Tree Node

A SQL guide for classifying binary tree nodes as Root, Inner, or Leaf based on parent-child relationships.

LeetCode 607: Sales Person

A SQL guide for finding salespeople who never had an order related to the company named RED.

LeetCode 603: Consecutive Available Seats

A SQL guide for finding all cinema seats that are free and adjacent to at least one other free seat.

LeetCode 602: Friend Requests II: Who Has the Most Friends

A SQL guide for counting friendships from both requester and accepter sides, then returning the user with the most friends.

LeetCode 601: Human Traffic of Stadium

A SQL guide for finding stadium records that belong to runs of at least three consecutive ids where each row has at least 100 people.

LeetCode 600: Non-negative Integers without Consecutive Ones

A clear digit dynamic programming solution for counting numbers whose binary representation does not contain consecutive ones.

LeetCode 599: Minimum Index Sum of Two Lists

A clear hash map solution for finding common strings with the smallest index sum.

LeetCode 598: Range Addition II

A clear math solution for counting the maximum values after repeated top-left matrix increment operations.

LeetCode 594: Longest Harmonious Subsequence

A clear hash map solution for finding the longest subsequence whose maximum and minimum differ by exactly one.

LeetCode 593: Valid Square

A clear geometry solution for checking whether four unordered points form a valid square.

LeetCode 592: Fraction Addition and Subtraction

A clear parsing and math solution for evaluating fraction addition and subtraction expressions.

LeetCode 591: Tag Validator

A clear stack-based parser for validating nested XML-like tags with CDATA sections.

LeetCode 590: N-ary Tree Postorder Traversal

A clear DFS solution for returning the postorder traversal of an N-ary tree.

LeetCode 589: N-ary Tree Preorder Traversal

A clear DFS solution for returning the preorder traversal of an N-ary tree.

LeetCode 588: Design In-Memory File System

A clear design guide for implementing an in-memory file system with directory listing, directory creation, file append, and file read operations.

LeetCode 587: Erect the Fence

A clear convex hull solution for returning all trees that lie on the fence boundary.

LeetCode 583: Delete Operation for Two Strings

A clear dynamic programming solution for finding the minimum deletions needed to make two strings equal.

LeetCode 582: Kill Process

A clear graph traversal solution for finding all processes terminated when killing a target process.

LeetCode 581: Shortest Unsorted Continuous Subarray

A clear linear-time solution for finding the shortest subarray that must be sorted to make the whole array sorted.

LeetCode 576: Out of Boundary Paths

A clear dynamic programming solution for counting paths that move a ball out of a grid boundary.

LeetCode 575: Distribute Candies

A clear explanation of Distribute Candies using a set to count candy types and a simple limit argument.

LeetCode 573: Squirrel Simulation

A clear explanation of Squirrel Simulation using Manhattan distance and the special first trip.

LeetCode 572: Subtree of Another Tree

A clear explanation of Subtree of Another Tree using recursive tree matching and DFS.

LeetCode 568: Maximum Vacation Days

A clear explanation of Maximum Vacation Days using dynamic programming over weeks and cities.

LeetCode 567: Permutation in String

A clear explanation of Permutation in String using a fixed-size sliding window and character frequency counts.

LeetCode 566: Reshape the Matrix

A clear explanation of Reshape the Matrix using index mapping from the original matrix to the reshaped matrix.

LeetCode 565: Array Nesting

A clear explanation of Array Nesting using cycle detection over a permutation.

LeetCode 564: Find the Closest Palindrome

A clear explanation of Find the Closest Palindrome using prefix mirroring and a small candidate set.

LeetCode 563: Binary Tree Tilt

A clear explanation of Binary Tree Tilt using postorder DFS to compute subtree sums and accumulate tilt.

LeetCode 562: Longest Line of Consecutive One in Matrix

A clear explanation of Longest Line of Consecutive One in Matrix using dynamic programming over four directions.

LeetCode 561: Array Partition

A clear explanation of Array Partition using sorting and adjacent pairing to maximize the sum of pair minimums.

LeetCode 560: Subarray Sum Equals K

A clear explanation of Subarray Sum Equals K using prefix sums and a hash map to count matching subarrays in linear time.

LeetCode 559: Maximum Depth of N-ary Tree

A clear explanation of Maximum Depth of N-ary Tree using recursive depth-first search.

LeetCode 557: Reverse Words in a String III

A clear explanation of Reverse Words in a String III using two-pointer scanning and string reversal.

LeetCode 556: Next Greater Element III

A clear explanation of Next Greater Element III using the next permutation algorithm on the digits of an integer.

LeetCode 555: Split Concatenated Strings

A clear explanation of Split Concatenated Strings using string reversal choices and enumeration of every possible cut point.

LeetCode 554: Brick Wall

A clear explanation of Brick Wall using prefix sums and a hash map to find the best vertical cut position.

LeetCode 553: Optimal Division

A clear explanation of Optimal Division using the structure of division expressions to build the maximum-value expression.

LeetCode 552: Student Attendance Record II

A clear explanation of Student Attendance Record II using dynamic programming over absence count and late streak.

LeetCode 551: Student Attendance Record I

A clear explanation of Student Attendance Record I using simple string checks and a one-pass counter solution.

LeetCode 549: Binary Tree Longest Consecutive Sequence II

A clear explanation of finding the longest increasing or decreasing consecutive path in a binary tree using DFS.

LeetCode 548: Split Array with Equal Sum

A clear explanation of splitting an array into four equal-sum parts using prefix sums and set-based search.

LeetCode 547: Number of Provinces

A clear explanation of counting connected components in an undirected graph represented by an adjacency matrix.

LeetCode 546: Remove Boxes

A clear explanation of maximizing remove-box scores using interval dynamic programming with memoization.

LeetCode 545: Boundary of Binary Tree

A clear explanation of collecting the boundary of a binary tree using separate left boundary, leaves, and right boundary traversals.

LeetCode 544: Output Contest Matches

A clear explanation of building the final tournament bracket by repeatedly pairing strongest and weakest teams.

LeetCode 543: Diameter of Binary Tree

A clear explanation of finding the longest path between any two nodes in a binary tree using DFS height computation.

LeetCode 542: 01 Matrix

A clear explanation of computing the distance to the nearest zero in a binary matrix using multi-source BFS.

LeetCode 541: Reverse String II

A clear explanation of reversing the first k characters in every 2k block of a string.

LeetCode 540: Single Element in a Sorted Array

A clear explanation of finding the only non-duplicate element in a sorted array using binary search.

LeetCode 539: Minimum Time Difference

A clear explanation of finding the minimum difference between 24-hour clock times using minute conversion and sorting.

LeetCode 538: Convert BST to Greater Tree

A clear explanation of converting a BST into a greater tree using reverse inorder traversal and a running sum.

LeetCode 537: Complex Number Multiplication

A clear explanation of multiplying complex numbers represented as strings using algebraic expansion.

LeetCode 536: Construct Binary Tree from String

A clear explanation of parsing a parenthesized string recursively to construct a binary tree.

LeetCode 535: Encode and Decode TinyURL

A clear explanation of designing a simple URL encoder and decoder using a hash map and generated keys.

LeetCode 533: Lonely Pixel II

A clear explanation of counting black lonely pixels using row counts, column counts, and duplicate row patterns.

LeetCode 532: K-diff Pairs in an Array

A clear explanation of counting unique pairs whose absolute difference is k using frequency counting.

LeetCode 531: Lonely Pixel I

A clear explanation of counting black pixels that are alone in both their row and column.

LeetCode 530: Minimum Absolute Difference in BST

A clear explanation of finding the minimum difference between two BST node values using inorder traversal.

LeetCode 529: Minesweeper

A clear explanation of updating a Minesweeper board using DFS flood fill and adjacent mine counting.

LeetCode 528: Random Pick with Weight

A clear explanation of weighted random sampling using prefix sums and binary search.

LeetCode 527: Word Abbreviation

A clear explanation of generating minimal unique word abbreviations using grouping and trie prefixes.

LeetCode 526: Beautiful Arrangement

A clear explanation of counting beautiful arrangements using backtracking and divisibility pruning.

LeetCode 525: Contiguous Array

A clear explanation of finding the longest contiguous subarray with equal numbers of 0 and 1 using prefix sums and a hash map.

LeetCode 524: Longest Word in Dictionary through Deleting

A clear explanation of finding the longest dictionary word obtainable as a subsequence using two pointers and sorting rules.

LeetCode 523: Continuous Subarray Sum

A clear explanation of detecting a subarray whose sum is a multiple of k using prefix sums and modular arithmetic.

LeetCode 522: Longest Uncommon Subsequence II

A clear explanation of finding the longest uncommon subsequence among many strings using subsequence checks.

LeetCode 519: Random Flip Matrix

A clear explanation of randomly flipping zero cells in a matrix without repetition using hash mapping and virtual swapping.

LeetCode 518: Coin Change II

A clear explanation of counting coin-change combinations using dynamic programming.

LeetCode 517: Super Washing Machines

A clear explanation of balancing dresses across washing machines using greedy prefix flow.

LeetCode 515: Find Largest Value in Each Tree Row

A clear explanation of finding the maximum value at every depth of a binary tree using level-order traversal.

LeetCode 514: Freedom Trail

A clear explanation of finding the minimum steps to spell a key on a circular ring using dynamic programming and memoized DFS.

LeetCode 513: Find Bottom Left Tree Value

A clear explanation of finding the leftmost value in the deepest row of a binary tree using level-order traversal.

LeetCode 510: Inorder Successor in BST II

A clear explanation of finding the inorder successor in a binary search tree when nodes contain parent pointers.

LeetCode 508: Most Frequent Subtree Sum

A clear explanation of finding the most frequent subtree sum in a binary tree using postorder DFS and a frequency map.

LeetCode 506: Relative Ranks

A clear explanation of assigning athlete ranks from scores using sorting while preserving original indices.

LeetCode 505: The Maze II

A clear explanation of finding the shortest rolling distance in a maze using Dijkstra’s algorithm.

LeetCode 503: Next Greater Element II

A clear explanation of finding the next greater element in a circular array using a monotonic stack.

LeetCode 502: IPO

A clear explanation of maximizing capital by selecting at most k projects using sorting and a max heap.

LeetCode 501: Find Mode in Binary Search Tree

A clear explanation of finding the most frequent value or values in a binary search tree using inorder traversal.

LeetCode 521: Longest Uncommon Subsequence I

A clear explanation of finding the longest uncommon subsequence between two strings using simple case analysis.

LeetCode 520: Detect Capital

A clear explanation of checking whether a word uses capital letters correctly by counting uppercase letters.

LeetCode 516: Longest Palindromic Subsequence

A clear explanation of finding the length of the longest palindromic subsequence using interval dynamic programming.

LeetCode 512: Game Play Analysis II

A clear explanation of finding the first device used by each player using SQL aggregation and a join.

LeetCode 511: Game Play Analysis I

A clear explanation of finding each player's first login date using SQL aggregation.

LeetCode 509: Fibonacci Number

A clear explanation of computing Fibonacci numbers using dynamic programming and iterative state transitions.

LeetCode 507: Perfect Number

A clear explanation of checking whether a number equals the sum of its positive divisors excluding itself.

LeetCode 504: Base 7

A clear explanation of converting an integer into its base 7 string representation using repeated division.

LeetCode 597: Friend Requests I: Overall Acceptance Rate

A clear SQL guide for computing the overall friend request acceptance rate with duplicate pairs counted once.

LeetCode 596: Classes With at Least 5 Students

A clear SQL guide for finding classes that have at least five students.

LeetCode 595: Big Countries

A clear SQL guide for finding countries with either large area or large population.

LeetCode 586: Customer Placing the Largest Number of Orders

A clear SQL guide for finding the customer who placed the most orders.

LeetCode 585: Investments in 2016

A clear SQL guide for summing 2016 investments for policies with repeated 2015 investment values and unique locations.

LeetCode 584: Find Customer Referee

A clear SQL guide for selecting customers who were not referred by customer 2, including customers with no referee.

LeetCode 580: Count Student Number in Departments

A clear SQL guide for counting students in every department, including departments with zero students.

LeetCode 579: Find Cumulative Salary of an Employee

A clear SQL guide for computing each employee's 3-month cumulative salary while excluding their most recent month.

LeetCode 578: Get Highest Answer Rate Question

A clear SQL guide for finding the question with the highest answer rate from survey logs.

LeetCode 577: Employee Bonus

A clear SQL guide for finding employees whose bonus is less than 1000 or missing.

LeetCode 574: Winning Candidate

A clear explanation of Winning Candidate using SQL aggregation to count votes and return the candidate with the most votes.

LeetCode 571: Find Median Given Frequency of Numbers

A clear explanation of Find Median Given Frequency of Numbers using cumulative frequency and SQL window functions.

LeetCode 570: Managers with at Least 5 Direct Reports

A clear explanation of Managers with at Least 5 Direct Reports using grouping and a self join.

LeetCode 569: Median Employee Salary

A clear explanation of Median Employee Salary using SQL window functions to rank employees inside each company.

LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees

A clear explanation of merging two quad-trees using recursive logical OR operations.

LeetCode 550: Game Play Analysis IV

A clear explanation of calculating the fraction of players who logged in again the day after their first login.

LeetCode 534: Game Play Analysis III

A clear explanation of computing cumulative games played per player and date using SQL window functions.

Tangent Propagation

Forward mode automatic differentiation computes derivatives by propagating tangent values alongside ordinary values. The ordinary value is called the primal. The derivative...

Case Studies

This section studies reverse mode automatic differentiation through concrete examples. Each case has the same structure:

Effect Systems and Mutation

Automatic differentiation is easiest to define for pure functions. A pure function behaves like a mathematical mapping: it consumes inputs, produces outputs, and has no...

Physics-Informed Models

Physics-informed models combine data fitting with equations from physics or applied mathematics. The model is trained not only to match observed samples, but also to satisfy...

Unified Differentiable Infrastructure

Automatic differentiation began as a numerical technique for computing gradients of scalar functions.

Production Deployment

A minimal automatic differentiation engine can compute correct gradients on small programs. A production system must survive long-running workloads, large tensors, distributed...

Differentiation of Large Stateful Systems

Automatic differentiation works naturally on pure mathematical functions:

Differentiation of Large Stateful Systems

Automatic differentiation works naturally on pure mathematical functions:

Summary and Synthesis

Automatic differentiation is a method for computing derivatives by transforming programs into derivative-propagating computations. It does not approximate derivatives...

Case Studies

Forward mode automatic differentiation appears in many numerical systems where directional derivatives, local sensitivities, or small parameter sets are important. This...

Reverse Mode in Deep Learning

Reverse mode automatic differentiation is the mathematical and systems basis of backpropagation. In deep learning, the objective is usually a scalar loss depending on many...

Differential Lambda Calculus

Automatic differentiation is deeply connected to functional programming and lambda calculus. Programs can be viewed as mathematical functions, and differentiation can be...

Complexity of Higher Orders

Higher-order automatic differentiation faces a fundamental problem: derivative structure grows combinatorially with order.

GPU Tensor Kernels

Modern automatic differentiation systems are fundamentally tensor compiler systems. Their performance depends less on mathematical differentiation rules than on how...

Type Systems for Differentiation

Automatic differentiation interacts deeply with type systems because differentiation changes the structure of computation. A derivative operator maps one function into another...

Reinforcement Learning

Reinforcement learning studies learning systems that act in an environment. Unlike supervised learning, the training signal is not a target label for each input. The model...

Probabilistic Programming

Probabilistic programming represents uncertainty using executable probabilistic models. A probabilistic program defines a distribution rather than only a deterministic computation.

Summary

Differentiable systems architecture extends automatic differentiation beyond isolated functions and neural network layers. The central idea is to treat larger systems as...

Distributed Gradient Computation

Distributed gradient computation appears when a differentiable program no longer fits comfortably on one device or one machine. The reason may be model size, data volume,...

Verified Differentiation

Automatic differentiation systems are usually trusted because they implement mathematically established rules such as the chain rule, product rule, and linearization of...

Differentiation as Functorial Transformation

The preceding sections described automatic differentiation through algebraic, categorical, logical, and denotational models. These viewpoints converge on one central idea:

Testing Derivatives

An automatic differentiation engine is only useful if its derivatives are correct. A small mistake in a backward rule can silently corrupt optimization, training, or...

Comparative Architecture Analysis

The systems in this chapter show that automatic differentiation is not one implementation technique. It is a family of program transformations. Each system chooses a different...

Comparative Architecture Analysis

The systems in this chapter show that automatic differentiation is not one implementation technique. It is a family of program transformations. Each system chooses a different...

Differentiable Subprograms

A differentiable subprogram is a program fragment that can participate in derivative propagation as a coherent unit. Instead of differentiating an entire application...

AD as Program Transformation

Automatic differentiation can be understood as a transformation from one program into another program.

Sparse Forward Methods

Many real-world Jacobians are sparse. Most derivative entries are zero because outputs depend only on small subsets of inputs.

Checkpointing

Checkpointing is a technique for reducing the memory cost of reverse mode automatic differentiation by selectively storing intermediate states and recomputing missing values...

Differential Lambda Calculus

Automatic differentiation is deeply connected to functional programming and lambda calculus. Programs can be viewed as mathematical functions, and differentiation can be...

Perturbation Confusion

Perturbation confusion is a correctness bug that appears in nested automatic differentiation, especially nested forward mode. It happens when two derivative computations...

Exception Handling and Undefined Regions

Programs do not only branch between valid computations. They also fail, stop early, raise exceptions, return sentinel values, or enter undefined numerical regions. These...

Sparse Tensor Derivatives

Most real computational problems are sparse. Large matrices and tensors often contain mostly zeros, structured blocks, or local interactions. Sparse representations reduce...

AD in Swift

Swift became an important experiment in language-integrated automatic differentiation because it attempted to make differentiation a core compiler feature rather than a...

Meta-Learning

Meta-learning studies systems that improve how they learn. Instead of only optimizing model parameters for one task, a meta-learning method optimizes some part of the learning...

Robotics and Control

Robotics and control systems interact with the physical world through sensing, estimation, planning, and actuation. Automatic differentiation is important because modern...

Hybrid Symbolic-Numeric Systems

A hybrid symbolic-numeric system combines discrete symbolic reasoning with continuous numerical computation. In the context of automatic differentiation, it means a pipeline...

GPU and TPU Execution

Modern automatic differentiation systems are built around accelerator hardware. GPUs and TPUs provide enormous throughput for tensor operations, making large-scale...

Differentiable Programming Languages

Automatic differentiation began as a transformation applied to numerical programs. A differentiable programming language instead treats differentiation as a native semantic...

Denotational Models

Operational semantics explains how automatic differentiation executes. Denotational semantics explains what differentiable programs mean.

Performance Benchmarking

Performance benchmarking measures whether an automatic differentiation engine is fast, memory-efficient, and scalable under realistic workloads. It also protects the engine...

Tinygrad

Tinygrad is a small deep learning framework centered around a minimal reverse-mode automatic differentiation engine. It was created by entity"people","George...

Tinygrad

Tinygrad is a small deep learning framework centered around a minimal reverse-mode automatic differentiation engine. It was created by entity"people","George...

Taylor Expansions

Differentiation describes how a function changes locally. A Taylor expansion extends this idea by approximating a function with a polynomial around a point.

Applications Across Science and Engineering

Automatic differentiation became important because derivatives are required everywhere numerical models are optimized, controlled, calibrated, or analyzed. Once a system can...

Dual Spaces and Pushforwards

Forward mode and reverse mode propagate different kinds of objects.

Purity and Side Effects

A pure computation is easier to differentiate because every output is determined only by its explicit inputs. There is no hidden state, no external mutation, and no dependence...

Numerical Exactness up to Floating Point

Automatic differentiation computes derivatives exactly with respect to the executed floating point program. This distinguishes AD from numerical differentiation, which...

Efficient Seeding Strategies

Forward mode automatic differentiation computes Jacobian-vector products:

Memory-Time Tradeoffs

Reverse mode automatic differentiation is computationally efficient for scalar-output functions, but it has a major systems cost: it needs information from the forward pass...

Category-Theoretic View

Automatic differentiation can be described operationally through dual numbers and computational graphs. It can also be described abstractly using category theory.

Efficient Higher-Order Methods

Higher-order derivatives contain rich geometric information, but naïve computation quickly becomes impractical.

Differentiating Stateful Systems

A stateful system is a program whose output depends not only on its explicit inputs, but also on stored state. The state may live in variables, objects, arrays, files, random...

Singular Value Decomposition

The singular value decomposition SVD is one of the most important matrix factorizations in numerical linear algebra. It appears in dimensionality reduction, least squares,...

AD in Julia

Julia was designed for high-performance technical computing. It combines interactive syntax with a compiler capable of specializing code aggressively based on types. This...

Implicit Layers

An implicit layer defines its output as the solution of an equation, not as a fixed sequence of explicit operations. Instead of computing

Signal Processing

Signal processing studies how information is represented, transformed, filtered, compressed, reconstructed, and estimated from signals. A signal may be a time series, an...

Differentiable Operating Systems

A differentiable operating system is an execution environment whose resource-management decisions can be optimized using gradients or gradient-like feedback. Instead of...

Parallelism

Automatic differentiation is usually described as a transformation of programs or computational graphs. In real systems, it is also a parallel execution problem. Large...

Quantum Differentiation

Quantum computation introduces a computational model fundamentally different from classical programs.

Formal Verification

Automatic differentiation systems are trusted infrastructure. Scientific computing, machine learning, optimization, simulation, and control systems depend on gradients being...

Custom Gradients

A custom gradient gives the user direct control over the backward rule of an operation. The forward computation still produces an ordinary value, but the derivative no longer...

Enzyme

Enzyme is a compiler-based automatic differentiation system for LLVM and MLIR. Instead of differentiating source code directly, or recording tensor operations at runtime,...

Enzyme

Enzyme is a compiler-based automatic differentiation system for LLVM and MLIR. Instead of differentiating source code directly, or recording tensor operations at runtime,...

Historical Development

Automatic differentiation developed from a simple observation: a numerical computation already contains the structure needed to compute its derivative. The program evaluates...

Linearization

Linearization is the operation of replacing a nonlinear function by its best local linear approximation at a chosen point. Automatic differentiation can be understood as a...

Memory and State

Automatic differentiation operates on computations, but computations execute inside a memory model. Variables occupy storage locations, arrays are mutated, buffers are reused,...

Computational Complexity

Automatic differentiation is fundamentally a computational technique. Its practical importance comes from the fact that derivatives can often be computed with asymptotic cost...

Higher-Dimensional Tangent Spaces

So far, forward mode has propagated a single tangent direction:

Wengert Lists

A Wengert list is a linear representation of a computation in which every intermediate result is assigned to a unique variable. It is one of the earliest and most influential...

Differential Algebras

Dual numbers and hyper-dual numbers are special cases of a broader algebraic structure called a differential algebra. This framework abstracts differentiation away from...

Taylor Mode AD

Taylor mode automatic differentiation computes derivatives by propagating truncated Taylor series through a program.

Non-Smooth Programs

A non-smooth program contains operations where the derivative is undefined, discontinuous, set-valued, or unstable under small perturbations. These programs arise naturally in...

Eigenvalue Problems

Eigenvalue problems are fundamental in numerical analysis, optimization, physics, graph methods, control theory, and machine learning. They are also among the most subtle...

Attention Mechanisms

Attention is a sequence operation that lets each position read information from other positions. Instead of compressing the whole past into one recurrent hidden state,...

Computational Finance

Computational finance uses numerical models to price contracts, measure risk, and optimize portfolios. Automatic differentiation is useful because most financial computations...

Differentiable Compilers

A differentiable compiler is a compilation system that supports gradient propagation through compilation decisions, generated programs, or execution behavior. Instead of...

Determinism and Reproducibility

Automatic differentiation systems are often assumed to be deterministic. Given identical inputs, identical parameters, and identical code, many users expect identical...

Probabilistic Automatic Differentiation

Classical automatic differentiation computes derivatives of deterministic programs.

Program Equivalence

Automatic differentiation transforms programs. A fundamental semantic question therefore arises:

Operator Libraries

An automatic differentiation engine becomes useful only after it supports a sufficiently rich set of primitive operations. The collection of these primitives is the operator...

Zygote

Zygote is a source-to-source reverse-mode automatic differentiation system for the Julia programming language. It was designed to differentiate high-level Julia code directly,...

Zygote

Zygote is a source-to-source reverse-mode automatic differentiation system for the Julia programming language. It was designed to differentiate high-level Julia code directly,...

Accuracy, Complexity, and Stability

Derivative computation is not only a mathematical problem. It is also a numerical and systems problem. A derivative method must answer three questions simultaneously:

Computational Graphs

A computational graph represents a calculation as nodes and edges. Nodes represent operations or values. Edges represent data dependencies. Automatic differentiation uses this...

Loops and Recurrence Relations

Loops express repeated computation. Recurrence relations express the same idea mathematically: each state is computed from one or more earlier states.

Mixed-Mode Differentiation

Mixed-mode differentiation combines forward accumulation and reverse accumulation in the same derivative computation. It is used when neither pure forward mode nor pure...

Complexity Analysis

Forward mode automatic differentiation has a simple cost model. It evaluates the original program and, at the same time, evaluates the tangent program. Each primitive...

Tape-Based Systems

Most reverse mode automatic differentiation systems require a mechanism for recording the forward computation so that the reverse pass can later traverse it backward. This...

Hyper-Dual Numbers

Dual numbers compute first derivatives exactly. Truncated polynomial algebras extend this to higher-order derivatives, but practical higher-order differentiation introduces an...

Nested AD

Nested automatic differentiation means applying automatic differentiation inside another automatic differentiation computation.

Piecewise Differentiability

A piecewise differentiable function is built from several differentiable pieces joined by boundaries. Each piece has an ordinary derivative inside its region. At the...

Differentiating Factorizations

Matrix factorizations rewrite a matrix into structured factors. They are used because the factors make later computations cheaper, more stable, or easier to interpret. In...

AD in Python

Python became the dominant language for modern machine learning and differentiable computing because it combines a simple programming model with access to high-performance...

Sequence Models

Sequence models process ordered data. The input is not one independent vector, but a series:

Molecular Simulation

Molecular simulation models the behavior of atoms and molecules using physical interaction laws. Automatic differentiation is important because many molecular methods require...

Differentiable Search and Retrieval

Differentiable search and retrieval systems integrate information access into gradient-based learning. Instead of treating retrieval as an external symbolic operation, the...

Gradient Vanishing and Explosion

Gradient-based optimization relies on propagating derivative information through many layers, time steps, or computational transformations. In deep systems, these gradients...

Neural ODEs

Classical neural networks apply a finite sequence of transformations:

Lambda Calculus and AD

Automatic differentiation becomes substantially more difficult once programs contain higher-order functions.

Memory Management

Memory management is the main systems problem in reverse mode automatic differentiation. The derivative rules are usually small. The hard part is deciding which primal values,...

JAX

JAX is an automatic differentiation and array programming system for Python. It combines NumPy-like syntax with composable program transformations. Its core transformations...

JAX

JAX is an automatic differentiation and array programming system for Python. It combines NumPy-like syntax with composable program transformations. Its core transformations...

Automatic Differentiation

Automatic differentiation computes derivatives by applying the chain rule to the operations of a program. The input is ordinary code that computes a value. The output is code,...

Chain Rule as Composition Algebra

The chain rule is the central theorem behind automatic differentiation. Every useful AD algorithm is a disciplined way of applying the chain rule to a program.

Control Flow

Control flow determines which operations a program executes. Straight-line programs have a fixed sequence of operations, but ordinary programs contain branches, loops,...

Reverse Accumulation

Reverse accumulation is the reverse-mode form of automatic differentiation. It propagates derivative information backward from outputs to inputs.

Jacobian-Vector Products

The natural output of forward mode automatic differentiation is a Jacobian-vector product. Instead of constructing the full Jacobian matrix explicitly, forward mode computes...

Reverse Accumulation Algorithms

Reverse accumulation is the operational core of reverse mode automatic differentiation. The forward pass evaluates a program and records dependency information. The reverse...

Truncated Polynomial Algebras

Dual numbers capture first-order derivatives because the infinitesimal element satisfies

Higher-Order Reverse Mode

Reverse mode is efficient for scalar-output functions because it propagates one adjoint backward through the computation and produces a full gradient. For

Dynamic Graphs

A dynamic graph is a computation graph built while the program runs. Its structure depends on ordinary runtime values: branches, loop counts, recursive calls, tensor shapes,...

Linear Algebra Primitives

Linear algebra primitives are tensor operations with algebraic structure: matrix multiplication, triangular solves, factorizations, inverses, determinants, norms, and spectral...

Neural Network Training

Neural network training is the repeated application of three operations: evaluate a model, differentiate a scalar loss, and update parameters. Automatic differentiation...

Computational Fluid Dynamics

Computational fluid dynamics studies fluid motion by solving discretized forms of the governing equations. Automatic differentiation enters CFD when we want gradients of...

Differentiable Physics Engines

A differentiable physics engine computes gradients of physical simulation outputs with respect to inputs, parameters, or control signals. Instead of treating simulation as a...

Memory Explosion

Reverse-mode automatic differentiation trades computation for memory. To compute gradients efficiently, the backward pass requires access to intermediate values produced...

Continuous-Time Adjoint Methods

Many systems evolve continuously over time rather than through discrete layers. A state variable changes according to a differential equation:

Differential Categories

Cartesian differential categories model differentiation in categories with products. Differential categories generalize this idea further by shifting attention from cartesian...

Tape Design

A tape is an append-only record of the operations executed during the forward pass. Reverse mode uses the tape to replay derivative rules backward.

PyTorch Autograd

PyTorch Autograd is a dynamic reverse-mode automatic differentiation system. It records tensor operations as they execute, builds a computation graph at runtime, and then...

PyTorch Autograd

PyTorch Autograd is a dynamic reverse-mode automatic differentiation system. It records tensor operations as they execute, builds a computation graph at runtime, and then...

Symbolic Differentiation

Symbolic differentiation computes derivatives by manipulating expressions. The input is a formula. The output is another formula.

Jacobians and Hessians

The gradient is enough when a function has many inputs and one scalar output. More general programs need more general derivative objects. Two of the most important are the...

Dependency Graphs

A dependency graph describes how values in a computation depend on earlier values. Automatic differentiation operates on these dependencies.

Forward Accumulation

Forward accumulation is the forward-mode form of automatic differentiation. It propagates derivative information in the same order as ordinary program evaluation. Each...

Forward Evaluation Rules

Forward mode automatic differentiation works by replacing each primitive operation with an extended operation on pairs:

Vector-Jacobian Products

Reverse mode automatic differentiation fundamentally computes vector-Jacobian products. The gradient of a scalar function is a special case of this more general operation.

Geometric Interpretation

Dual numbers provide an algebraic mechanism for differentiation, but they also have a precise geometric meaning. A dual number represents a point together with an...

Recursion

Recursion is control flow where a function calls itself. In automatic differentiation, recursion behaves like a loop with a call stack. Each recursive call contributes one...

Broadcasting Semantics

Broadcasting is the rule system that allows tensor operations between arrays of different shapes without explicitly materializing expanded copies. It is one of the most...

Differentiable Programming

Differentiable programming treats differentiation as a general programming-language feature. A program can contain numerical kernels, control flow, data structures, solvers,...

Backpropagation

Backpropagation is reverse mode automatic differentiation applied to neural networks. In most machine learning writing, the term refers to the whole training procedure: run a...

Inverse Problems

An inverse problem asks for causes from effects. A forward model predicts observations from parameters. An inverse model tries to recover parameters from observations.

Differentiable Rendering

Differentiable rendering is the process of computing derivatives of rendered images with respect to scene parameters. A renderer becomes part of the computational graph rather...

Overflow and Underflow

Floating point systems represent numbers within a finite range. When a computed value exceeds the largest representable magnitude, overflow occurs. When a value becomes too...

Differentiable Optimization Layers

An optimization layer is a program component whose output is the solution of an optimization problem. Instead of computing

Categorical Semantics

Algebraic semantics describes differentiation through derivations, tangent maps, and linear structure. Categorical semantics goes further. It studies differentiation as a...

Graph Representation

A graph representation makes the structure of a differentiated computation explicit. In reverse mode, this structure is required because the backward pass must know which...

TensorFlow Autograd

TensorFlow Autograd refers to TensorFlow’s automatic differentiation system, mainly exposed through tf.GradientTape. It is a reverse-mode AD system designed for tensor...

TensorFlow Autograd

TensorFlow Autograd refers to TensorFlow’s automatic differentiation system, mainly exposed through tf.GradientTape. It is a reverse-mode AD system designed for tensor...

Numerical Differentiation

Numerical differentiation estimates derivatives by evaluating a function at nearby input values. It treats the function as a black box. The method does not need access to the...

Multivariate Calculus

Automatic differentiation is usually applied to functions with many inputs and many outputs. The calculus needed for this setting is multivariate calculus: the study of how a...

Intermediate Variables

Intermediate variables are the named values created between program inputs and program outputs. They make automatic differentiation mechanical.

Elementary Operations

Automatic differentiation reduces differentiation to a finite collection of elementary operations. Every program, regardless of complexity, is decomposed into primitive...

Dual Numbers

Dual numbers give forward mode automatic differentiation a compact algebraic form. Instead of storing a value and a tangent as two unrelated fields, we package them into one...

Reverse Computational Graphs

Reverse mode automatic differentiation operates on a computational graph. The forward pass evaluates the graph from inputs to outputs. The reverse pass traverses the same...

Nilpotent Elements

The defining feature of dual numbers is the existence of a nonzero element whose square vanishes:

forward

A loop repeats a computation until a condition fails or a fixed iteration count is reached. In automatic differentiation, loops are important because many numerical algorithms...

Tensor Operations

Tensor operations generalize scalar, vector, and matrix operations to arrays with arbitrary rank. In automatic differentiation, a tensor is usually treated as a typed array...

Functional Languages

Functional programming languages provide a natural semantic foundation for automatic differentiation. Programs are expressed as compositions of functions, immutable values,...

Stochastic Optimization

Stochastic optimization studies optimization when the objective is accessed through samples, noisy estimates, or partial observations. In machine learning, this is the normal...

Sensitivity Analysis

Sensitivity analysis studies how changes in inputs affect the outputs of a system. In differential equations, optimization, simulation, and machine learning, the main object...

Differentiable Databases

A differentiable database is a data system whose operations participate in gradient-based optimization. Instead of treating storage and querying as external infrastructure,...

Stability of Reverse Mode

Reverse mode automatic differentiation computes gradients by propagating adjoint values backward through a computational graph. In exact arithmetic, the reverse accumulation...

Differentiating Through Solvers

A solver is a program that computes a value by search, iteration, or factorization. Instead of evaluating a closed-form expression, it finds a value that satisfies a condition.

Algebraic Semantics

Automatic differentiation is often introduced operationally. A program executes elementary operations, and derivative information propagates alongside the computation. This...

Minimal Reverse Mode Engine

Reverse mode automatic differentiation computes derivatives by traversing the program backward after evaluation. Unlike forward mode, which propagates tangents alongside...

Tapenade

Tapenade is a source-transformation automatic differentiation system developed at INRIA. Like ADIFOR, it takes an existing program and produces a new differentiated program....

Tapenade

Tapenade is a source-transformation automatic differentiation system developed at INRIA. Like ADIFOR, it takes an existing program and produces a new differentiated program....

Chapter 1. Introduction

A derivative measures how an output changes when an input changes. That sentence is simple, but it is one of the main ideas behind numerical computing, optimization, machine...

Chapter 2. Mathematical Foundations

Automatic differentiation begins with a simple object: a function.

Chapter 3. Programs as Mathematical Objects

A straight-line program is the simplest model of computation used in automatic differentiation. It is a program with a fixed sequence of assignments, no branches, no loops,...

Chapter 4. Core Theory of Automatic Differentiation

Automatic differentiation is built on a simple observation: a complicated derivative can be computed by composing many small local derivatives. Instead of manipulating a full...

Chapter 5. Forward Mode Automatic Differentiation

Forward mode automatic differentiation computes derivatives by carrying two values through a program at the same time: the ordinary value and its tangent. The ordinary value...

Chapter 6. Reverse Mode Automatic Differentiation

Reverse mode automatic differentiation computes derivatives by propagating sensitivities backward through a computation. In forward mode, each intermediate value carries a...

Chapter 7. Dual Numbers and Algebraic Structures

Dual numbers give the cleanest algebraic model of forward mode automatic differentiation. They extend ordinary real numbers with a formal infinitesimal part. Instead of...

Chapter 8. Higher-Order Differentiation

First derivatives describe local rate of change. Second derivatives describe how that rate of change itself changes. In optimization, this is curvature. In dynamics, it is...

Chapter 9. Differentiation of Control Flow

A conditional is a program construct that chooses one computation among several possible computations. In ordinary code, this is written as if, else, switch, case, pattern...

Chapter 10. Matrix and Tensor Differentiation

Matrix calculus is the notation and rule system used to differentiate functions whose inputs, outputs, or intermediate values are vectors, matrices, or tensors. Automatic...

Chapter 13. Optimization and Machine Learning

Gradient descent is the basic optimization procedure behind much of modern machine learning. It is simple enough to state in one line, but rich enough to expose many of the...

Chapter 14. Scientific Computing Applications

Differential equations are one of the main reasons automatic differentiation matters in scientific computing. Many scientific models are not written as closed-form functions....

Chapter 15. Differentiable Systems Architecture

An end-to-end differentiable pipeline is a system whose final objective can send derivative information backward through every trainable or tunable stage of computation....

Chapter 17. Numerical and Systems Concerns

Automatic differentiation computes derivatives by executing arithmetic. On a real machine, arithmetic uses finite precision. This means AD gives the derivative of the...

Chapter 18. Advanced Topics

Many programs do not compute their output by applying a fixed sequence of explicit operations. Instead, they define the output as the solution of another problem.

Chapter 19. Theory and Foundations

Automatic differentiation is often described by a simple rule:

Chapter 20. Building an AD Engine

A minimal forward mode automatic differentiation engine has one job: evaluate a program while carrying both a value and its derivative. The engine does not build a graph. It...

Chapter 21. Major AD Systems

ADIFOR, short for Automatic Differentiation of Fortran, is one of the classical source-transformation systems for automatic differentiation. It was designed for numerical...

Appendix

ADIFOR, short for Automatic Differentiation of Fortran, is one of the classical source-transformation systems for automatic differentiation. It was designed for numerical...

Chapter 16. Sparse and Structured Differentiation

Sparse and structured differentiation studies how to compute derivatives without materializing dense derivative objects. Many real systems have enormous Jacobians and...

Chapter 22. Open Problems

Automatic differentiation works naturally on pure mathematical functions:

Ahead-of-Time vs Just-in-Time Differentiation

Automatic differentiation can be performed before a program runs, while it runs, or in a staged phase between the two.

Kernel Fusion

Kernel fusion combines several small operations into one larger executable unit.

Memory Planning

Memory planning determines where values are stored, how long they remain alive, and when storage can be reused.

Staging and Partial Evaluation

Staging is the separation of a program into phases.

Tracing Systems

Tracing is an implementation strategy where an AD system observes a program while it runs and records the operations that occur.

AD in Rust

Rust is an attractive language for automatic differentiation because it combines low-level performance with strong static guarantees. It gives the programmer control over...

Graph IRs

A graph intermediate representation models a program as nodes and edges.

SSA Form

Static single assignment form, or SSA, is an intermediate representation where each variable is assigned exactly once.

AD in C and C++

C and C++ are important targets for automatic differentiation because much scientific, engineering, graphics, finance, and machine learning infrastructure is written in these...

Intermediate Representations

An intermediate representation, or IR, is the internal program form used by a compiler or AD system after parsing and before final code generation.

Operator Overloading

Operator overloading implements automatic differentiation by changing the meaning of ordinary arithmetic operations for special numeric objects.

Chapter 11. Compiler and Runtime Design

Source transformation is an implementation strategy for automatic differentiation in which a program that computes a function is rewritten into another program that computes...

Chapter 12. AD in Modern Programming Languages

Lisp is one of the natural homes of automatic differentiation. It treats programs as data, has a simple expression syntax, and supports macro systems that can transform code...

LeetCode 500: Keyboard Row

A clear explanation of filtering words that can be typed using only one row of an American keyboard.

LeetCode 499: The Maze III

A clear explanation of finding the shortest rolling-ball path to the hole using Dijkstra with lexicographic tie-breaking.

LeetCode 498: Diagonal Traverse

A clear explanation of returning matrix elements in diagonal zigzag order by grouping cells with the same row plus column index.

LeetCode 497: Random Point in Non-overlapping Rectangles

A clear explanation of uniformly picking an integer point from non-overlapping rectangles using prefix sums and binary search.

LeetCode 496: Next Greater Element I

A clear explanation of finding the next greater element using a monotonic decreasing stack and hash map.

LeetCode 495: Teemo Attacking

A clear explanation of calculating total poisoned duration by merging overlapping attack intervals.

LeetCode 494: Target Sum

A clear explanation of counting sign assignments that reach a target using recursion first, then subset-sum dynamic programming.

LeetCode 493: Reverse Pairs

A clear explanation of counting pairs where nums[i] is greater than twice nums[j] using merge sort.

LeetCode 492: Construct the Rectangle

A clear explanation of finding rectangle dimensions with a fixed area and the smallest length-width difference.

LeetCode 491: Non-decreasing Subsequences

A clear explanation of generating all distinct non-decreasing subsequences using DFS, backtracking, and per-level duplicate control.

LeetCode 490: The Maze

A clear explanation of deciding whether a rolling ball can stop at the destination using BFS or DFS over stopping cells.

LeetCode 489: Robot Room Cleaner

A clear explanation of cleaning an unknown grid using DFS, relative coordinates, and physical backtracking.

LeetCode 488: Zuma Game

A clear explanation of solving Zuma Game with DFS, memoization, and chain-removal simulation.

LeetCode 487: Max Consecutive Ones II

A clear explanation of finding the longest run of 1s after flipping at most one 0 using a sliding window.

LeetCode 486: Predict the Winner

A clear explanation of predicting whether Player 1 can win using minimax dynamic programming over score difference.

LeetCode 485: Max Consecutive Ones

A clear explanation of finding the longest streak of 1s in a binary array with a single pass.

LeetCode 484: Find Permutation

A clear explanation of constructing the lexicographically smallest permutation that matches an I and D pattern.

LeetCode 483: Smallest Good Base

A clear explanation of finding the smallest base where n is written as all ones using geometric series and binary search.

LeetCode 482: License Key Formatting

A clear explanation of reformatting a license key by removing dashes, uppercasing characters, and grouping from the right.

LeetCode 481: Magical String

A clear explanation of constructing the magical string by using the string itself as run-length instructions.

LeetCode 480: Sliding Window Median

A clear explanation of maintaining the median of each fixed-size window using two heaps and lazy deletion.

LeetCode 479: Largest Palindrome Product

A clear explanation of finding the largest palindrome made from the product of two n-digit numbers by generating palindrome candidates directly.

LeetCode 478: Generate Random Point in a Circle

A clear explanation of generating uniformly random points inside a circle using polar coordinates.

LeetCode 477: Total Hamming Distance

A clear explanation of computing the total Hamming distance across all pairs by counting different bits column by column.

LeetCode 476: Number Complement

A clear explanation of finding the bitwise complement of a positive integer using a binary mask.

LeetCode 475: Heaters

A clear explanation of finding the minimum heater radius by sorting positions and matching each house to its nearest heater.

LeetCode 474: Ones and Zeroes

A clear explanation of solving the largest subset problem as a two-dimensional 0/1 knapsack over zero and one counts.

LeetCode 473: Matchsticks to Square

A clear explanation of deciding whether matchsticks can form a square using backtracking, sorting, and pruning.

LeetCode 472: Concatenated Words

A clear explanation of finding all words that can be formed by concatenating at least two shorter words from the same list.

LeetCode 471: Encode String with Shortest Length

A clear explanation of interval dynamic programming for encoding a string into the shortest k[encoded_string] form.

LeetCode 470: Implement Rand10() Using Rand7()

A clear explanation of generating a uniform random integer from 1 to 10 using only rand7 and rejection sampling.

LeetCode 469: Convex Polygon

A clear explanation of checking whether ordered points form a convex polygon using cross products.

LeetCode 468: Validate IP Address

A clear explanation of validating IPv4 and IPv6 addresses by checking segment count, length, characters, range, and leading-zero rules.

LeetCode 467: Unique Substrings in Wraparound String

A clear explanation of counting unique substrings that appear in the infinite alphabet wraparound string using dynamic programming by ending character.

LeetCode 466: Count The Repetitions

A clear explanation of counting how many repeated copies of one string can be obtained as a subsequence of another repeated string.

LeetCode 465: Optimal Account Balancing

A clear explanation of minimizing debt-settlement transactions using net balances, backtracking, and memoization-style pruning.

LeetCode 464: Can I Win

A clear explanation of solving the Can I Win game using minimax recursion, bitmask state compression, and memoization.

LeetCode 463: Island Perimeter

A clear explanation of counting the perimeter of an island in a grid by adding land-cell edges and subtracting shared edges.

LeetCode 462: Minimum Moves to Equal Array Elements II

A clear explanation of why the median minimizes the number of moves needed to make all array elements equal.

LeetCode 461: Hamming Distance

A clear explanation of computing the Hamming distance between two integers using XOR and bit counting.

LeetCode 460: LFU Cache

A clear explanation of designing an LFU cache with O(1) average get and put operations.

LeetCode 459: Repeated Substring Pattern

A clear explanation of checking whether a string can be built by repeating one of its proper substrings.

LeetCode 458: Poor Pigs

A clear explanation of the combinatorics behind finding the minimum number of pigs needed to identify the poisonous bucket.

LeetCode 457: Circular Array Loop

A clear explanation of detecting a valid cycle in a circular array using fast and slow pointers.

LeetCode 456: 132 Pattern

A clear explanation of detecting a 132 pattern using reverse traversal and a monotonic stack.

LeetCode 455: Assign Cookies

A clear explanation of the greedy two-pointer solution for maximizing the number of content children.

LeetCode 454: 4Sum II

A clear explanation of counting zero-sum tuples across four arrays using pair sums and a hash map.

LeetCode 453: Minimum Moves to Equal Array Elements

A clear explanation of the math behind making all array elements equal by incrementing n - 1 elements at a time.

LeetCode 452: Minimum Number of Arrows to Burst Balloons

A clear explanation of the greedy interval solution for finding the minimum number of arrows needed to burst all balloons.

LeetCode 451: Sort Characters By Frequency

A clear explanation of sorting characters by decreasing frequency using a hash map and sorting.

LeetCode 450: Delete Node in a BST

Delete a node from a binary search tree while preserving the BST property using recursive search and inorder successor replacement.

LeetCode 449: Serialize and Deserialize BST

Serialize a binary search tree compactly with preorder traversal and rebuild it using BST value bounds.

LeetCode 448: Find All Numbers Disappeared in an Array

Find all missing numbers from 1 to n in O(n) time using in-place index marking.

LeetCode 447: Number of Boomerangs

Count ordered boomerang tuples by fixing each point as the center and grouping other points by squared distance.

LeetCode 446: Arithmetic Slices II - Subsequence

Count arithmetic subsequences of length at least three using dynamic programming with one hash map per ending index.

LeetCode 445: Add Two Numbers II

Add two numbers stored in forward-order linked lists using stacks and carry propagation.

LeetCode 444: Sequence Reconstruction

Check whether nums is the unique shortest supersequence of given subsequences using topological sorting.

LeetCode 443: String Compression

Compress a character array in-place using two pointers and grouped character counting.

LeetCode 442: Find All Duplicates in an Array

Find all duplicated numbers in an array in O(n) time and O(1) extra space using index marking.

LeetCode 441: Arranging Coins

Find the maximum number of complete staircase rows that can be formed using binary search and triangular numbers.

LeetCode 440: K-th Smallest in Lexicographical Order

Find the k-th integer in lexicographical order without generating all numbers, using prefix counting over a conceptual trie.

LeetCode 439: Ternary Expression Parser

Evaluate a nested ternary expression using a right-to-left stack parser.

LeetCode 438: Find All Anagrams in a String

Find all starting indices where an anagram of p appears in s using a fixed-size sliding window.

LeetCode 437: Path Sum III

Count downward paths in a binary tree whose values sum to targetSum using DFS and prefix sums.

LeetCode 436: Find Right Interval

Find, for each interval, the interval with the smallest start point greater than or equal to its end point using sorting and binary search.

LeetCode 435: Non-overlapping Intervals

Remove the minimum number of intervals so the remaining intervals do not overlap, using greedy sorting by end time.

LeetCode 434: Number of Segments in a String

Count the number of word segments in a string by detecting transitions from spaces to non-space characters.

LeetCode 433: Minimum Genetic Mutation

Find the minimum number of valid one-character gene mutations using breadth-first search.

LeetCode 432: All O'one Data Structure

Design a data structure that supports increment, decrement, get minimum key, and get maximum key in average O(1) time.

LeetCode 431: Encode N-ary Tree to Binary Tree

Convert an N-ary tree into a binary tree and reconstruct it using the left-child right-sibling representation.

LeetCode 430: Flatten a Multilevel Doubly Linked List

Flatten a multilevel doubly linked list in-place using depth-first traversal and pointer splicing.

LeetCode 429: N-ary Tree Level Order Traversal

Traverse an N-ary tree level by level using breadth-first search.

LeetCode 428: Serialize and Deserialize N-ary Tree

Serialize an N-ary tree into a string and reconstruct the same tree using preorder traversal with child counts.

LeetCode 427: Construct Quad Tree

Build a quad tree from a binary square grid using recursive divide and conquer.

LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List

Convert a BST into a sorted circular doubly linked list in-place using inorder traversal.

LeetCode 425: Word Squares

A clear explanation of building all word squares using backtracking with prefix pruning.

LeetCode 424: Longest Repeating Character Replacement

A clear explanation of finding the longest substring that can become all one letter using a sliding window.

LeetCode 423: Reconstruct Original Digits from English

A clear explanation of reconstructing digits from shuffled English words using character frequency counts and unique identifying letters.

LeetCode 422: Valid Word Square

A clear explanation of checking whether rows and columns read the same using direct index comparison.

LeetCode 421: Maximum XOR of Two Numbers in an Array

A clear explanation of finding the maximum XOR of two numbers using greedy bit prefixes.

LeetCode 419: Battleships in a Board

A clear explanation of counting battleships in a board using one-pass observation without modifying the grid.

LeetCode 418: Sentence Screen Fitting

A clear explanation of fitting a sentence onto a screen using cyclic string simulation and greedy row transitions.

LeetCode 417: Pacific Atlantic Water Flow

A clear explanation of finding cells that can flow to both oceans using reverse graph traversal from the borders.

LeetCode 416: Partition Equal Subset Sum

A clear explanation of deciding whether an array can be split into two equal-sum subsets using 0/1 knapsack dynamic programming.

LeetCode 415: Add Strings

A clear explanation of adding two non-negative integer strings using manual digit-by-digit simulation.

LeetCode 414: Third Maximum Number

A clear explanation of finding the third distinct maximum number using one pass and constant space.

LeetCode 413: Arithmetic Slices

A clear explanation of counting arithmetic subarrays using dynamic programming and consecutive differences.

LeetCode 412: Fizz Buzz

A clear explanation of the Fizz Buzz problem using direct simulation and divisibility checks.

LeetCode 411: Minimum Unique Word Abbreviation

A clear explanation of finding the shortest abbreviation that does not conflict with any dictionary word using bit masks.

LeetCode 409: Longest Palindrome

A clear explanation of finding the longest palindrome length that can be built from given letters using character counts.

LeetCode 407: Trapping Rain Water II

A clear explanation of trapping rain water in a 2D elevation map using a min heap and boundary expansion.

LeetCode 404: Sum of Left Leaves

A clear explanation of the Sum of Left Leaves problem using depth-first traversal of a binary tree.

LeetCode 403: Frog Jump

A clear explanation of the Frog Jump problem using dynamic programming with reachable jump sizes.

LeetCode 420: Strong Password Checker

A clear explanation of checking the minimum edits needed to make a password strong using greedy handling of length, missing character types, and repeated runs.

LeetCode 410: Split Array Largest Sum

A clear explanation of minimizing the largest subarray sum using binary search on the answer and greedy validation.

LeetCode 408: Valid Word Abbreviation

A clear explanation of validating a word abbreviation using two pointers and number parsing.

LeetCode 406: Queue Reconstruction by Height

A clear explanation of reconstructing a queue using greedy sorting and indexed insertion.

LeetCode 405: Convert a Number to Hexadecimal

A clear explanation of converting integers to hexadecimal using bit manipulation and two's complement representation.

LeetCode 402: Remove K Digits

A clear explanation of the Remove K Digits problem using a greedy monotonic stack.

LeetCode 401: Binary Watch

A clear explanation of the Binary Watch problem using bit counting over all valid times.

LeetCode 400: Nth Digit

A clear explanation of finding the nth digit in the infinite integer sequence using digit groups and arithmetic.

LeetCode 399: Evaluate Division

A clear explanation of solving division equations using graph traversal and weighted edges.

LeetCode 398: Random Pick Index

A clear explanation of picking a uniformly random index for a target value using reservoir sampling, with an alternative hash map approach.

LeetCode 397: Integer Replacement

A clear explanation of reducing an integer to 1 with the fewest operations using greedy bit decisions.

LeetCode 396: Rotate Function

A clear explanation of maximizing the rotation function using a recurrence instead of simulating every rotation.

LeetCode 395: Longest Substring with At Least K Repeating Characters

A clear explanation of finding the longest substring where every character appears at least k times using divide and conquer.

LeetCode 394: Decode String

A clear explanation of decoding nested repeat expressions using a stack.

LeetCode 393: UTF-8 Validation

A clear explanation of validating a byte sequence as UTF-8 using bit masks and a continuation-byte counter.

LeetCode 392: Is Subsequence

A clear explanation of checking whether one string is a subsequence of another using two pointers.

LeetCode 391: Perfect Rectangle

A clear explanation of checking whether many small axis-aligned rectangles form one exact rectangular cover using area and corner parity.

LeetCode 390: Elimination Game

A clear explanation of finding the last remaining number after alternating left-to-right and right-to-left eliminations.

LeetCode 389: Find the Difference

A clear explanation of finding the extra character added to a shuffled string using counting and XOR.

LeetCode 388: Longest Absolute File Path

A clear explanation of computing the longest absolute path to a file from a serialized file system string using path lengths by depth.

LeetCode 387: First Unique Character in a String

A clear explanation of finding the first non-repeating character in a string using character frequency counting.

LeetCode 386: Lexicographical Numbers

A clear explanation of generating numbers from 1 to n in lexicographical order using an iterative DFS-style traversal.

LeetCode 385: Mini Parser

A clear explanation of parsing a serialized nested integer string using a stack.

LeetCode 384: Shuffle an Array

A clear explanation of shuffling an array uniformly using the Fisher-Yates algorithm while supporting reset.

LeetCode 383: Ransom Note

A clear explanation of checking whether one string can be constructed from another using character frequency counting.

LeetCode 382: Linked List Random Node

A clear explanation of selecting a random linked list node with equal probability using reservoir sampling.

LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed

A clear explanation of designing a randomized multiset with average O(1) insert, remove, and getRandom operations.

LeetCode 380: Insert Delete GetRandom O(1)

A clear explanation of designing a randomized set with average O(1) insert, remove, and getRandom operations.

LeetCode 379: Design Phone Directory

A clear explanation of designing a phone directory that can allocate, check, and release numbers efficiently.

LeetCode 378: Kth Smallest Element in a Sorted Matrix

A clear explanation of finding the kth smallest value in a row-sorted and column-sorted matrix using binary search on values.

LeetCode 377: Combination Sum IV

A clear explanation of Combination Sum IV using dynamic programming to count ordered combinations that sum to a target.

LeetCode 376: Wiggle Subsequence

A clear explanation of the Wiggle Subsequence problem using dynamic programming intuition and an optimized greedy solution.

LeetCode 375: Guess Number Higher or Lower II

A clear explanation of finding the minimum guaranteed cost using interval dynamic programming.

LeetCode 374: Guess Number Higher or Lower

A clear explanation of finding the picked number using binary search and the guess API.

LeetCode 373: Find K Pairs with Smallest Sums

A clear explanation of finding the k smallest pair sums from two sorted arrays using a min heap and best-first search.

LeetCode 372: Super Pow

A clear explanation of computing large modular exponentiation using fast power, modular arithmetic, and digit decomposition.

LeetCode 371: Sum of Two Integers

A clear explanation of adding two integers without using plus or minus by using XOR, AND, carry, and a 32-bit mask.

LeetCode 370: Range Addition

A clear explanation of applying many range updates efficiently using a difference array and prefix sums.

LeetCode 369: Plus One Linked List

A clear explanation of adding one to a number stored as a linked list using the rightmost non-nine digit.

LeetCode 368: Largest Divisible Subset

A clear explanation of finding the largest subset where every pair is divisible using sorting, dynamic programming, and parent reconstruction.

LeetCode 367: Valid Perfect Square

A clear explanation of checking whether an integer is a perfect square using binary search without sqrt.

LeetCode 366: Find Leaves of Binary Tree

A clear explanation of grouping binary tree nodes by the round in which they become leaves using postorder DFS.

LeetCode 365: Water and Jug Problem

A clear explanation of solving the Water and Jug Problem using Bézout's identity and greatest common divisor.

LeetCode 364: Nested List Weight Sum II

A clear explanation of computing inverse depth weighted sum using level-order traversal.

LeetCode 363: Max Sum of Rectangle No Larger Than K

A clear explanation of reducing a 2D rectangle problem to a 1D prefix-sum problem with binary search.

LeetCode 362: Design Hit Counter

A clear explanation of designing a hit counter for the last 5 minutes using a queue with compressed timestamps.

LeetCode 361: Bomb Enemy

A clear explanation of finding the best bomb placement in a grid using cached row and column segment counts.

LeetCode 360: Sort Transformed Array

A clear explanation of sorting values after applying a quadratic function using two pointers.

LeetCode 359: Logger Rate Limiter

A clear explanation of designing a logger that prints each message at most once every 10 seconds using a hash map.

LeetCode 358: Rearrange String k Distance Apart

A clear explanation of rearranging a string so equal characters are at least k positions apart using a heap and cooldown queue.

LeetCode 357: Count Numbers with Unique Digits

A clear explanation of counting numbers with unique digits using combinatorics.

LeetCode 356: Line Reflection

A clear explanation of checking whether 2D points are symmetric around a vertical line using min and max x-coordinates.

LeetCode 355: Design Twitter

A clear explanation of implementing a simplified Twitter using hash maps, sets, timestamps, and a heap.

LeetCode 354: Russian Doll Envelopes

A clear explanation of solving Russian Doll Envelopes using sorting and longest increasing subsequence.

LeetCode 353: Design Snake Game

A clear explanation of implementing Snake Game with a deque for body order and a set for constant-time collision checks.

LeetCode 352: Data Stream as Disjoint Intervals

A clear explanation of maintaining disjoint sorted intervals from a stream using insertion and merging.

LeetCode 351: Android Unlock Patterns

A clear explanation of Android Unlock Patterns using backtracking, a jump table, and symmetry optimization.

LeetCode 350: Intersection of Two Arrays II

A clear explanation of Intersection of Two Arrays II using frequency counting.

LeetCode 349: Intersection of Two Arrays

A clear explanation of Intersection of Two Arrays using hash sets for uniqueness and fast lookup.

LeetCode 348: Design Tic-Tac-Toe

A clear explanation of Design Tic-Tac-Toe using row, column, and diagonal counters for constant-time winner checks.

LeetCode 347: Top K Frequent Elements

A clear explanation of Top K Frequent Elements using frequency counting and bucket sort.

LeetCode 346: Moving Average from Data Stream

A clear explanation of Moving Average from Data Stream using a queue and rolling sum.

LeetCode 345: Reverse Vowels of a String

A clear explanation of Reverse Vowels of a String using two pointers and selective swaps.

LeetCode 344: Reverse String

A clear explanation of Reverse String using two pointers and in-place swaps.

LeetCode 343: Integer Break

A clear explanation of Integer Break using dynamic programming, with a note on the greedy math solution.

LeetCode 342: Power of Four

A clear explanation of Power of Four using bit manipulation and binary properties.

LeetCode 341: Flatten Nested List Iterator

A clear explanation of Flatten Nested List Iterator using lazy stack-based flattening.

LeetCode 340: Longest Substring with At Most K Distinct Characters

A clear explanation of Longest Substring with At Most K Distinct Characters using a sliding window and character counts.

LeetCode 339: Nested List Weight Sum

A clear explanation of Nested List Weight Sum using depth-first search over a nested structure.

LeetCode 338: Counting Bits

A clear explanation of Counting Bits using dynamic programming and bit manipulation.

LeetCode 337: House Robber III

A clear explanation of House Robber III using tree dynamic programming with rob and skip states.

LeetCode 336: Palindrome Pairs

A clear explanation of Palindrome Pairs using reversed-word lookup and palindrome split checks.

LeetCode 335: Self Crossing

A clear explanation of Self Crossing using constant-space checks for the only possible crossing patterns.

LeetCode 334: Increasing Triplet Subsequence

A clear explanation of Increasing Triplet Subsequence using greedy tracking of two minimum values.

LeetCode 333: Largest BST Subtree

A clear explanation of Largest BST Subtree using postorder traversal and subtree state propagation.

LeetCode 332: Reconstruct Itinerary

A clear explanation of Reconstruct Itinerary using a directed graph and Hierholzer's algorithm.

LeetCode 331: Verify Preorder Serialization of a Binary Tree

A clear explanation of verifying preorder serialization using slot counting without reconstructing the tree.

LeetCode 330: Patching Array

A clear explanation of Patching Array using a greedy smallest-missing-sum invariant.

LeetCode 329: Longest Increasing Path in a Matrix

A clear explanation of Longest Increasing Path in a Matrix using DFS with memoization.

LeetCode 328: Odd Even Linked List

A clear explanation of Odd Even Linked List using in-place pointer rewiring.

LeetCode 327: Count of Range Sum

A clear explanation of Count of Range Sum using prefix sums and merge sort counting.

LeetCode 326: Power of Three

A clear explanation of the Power of Three problem using repeated division and integer arithmetic.

LeetCode 325: Maximum Size Subarray Sum Equals k

A clear explanation of Maximum Size Subarray Sum Equals k using prefix sums and earliest-index hashing.

LeetCode 324: Wiggle Sort II

A clear explanation of Wiggle Sort II using sorting, median splitting, and virtual indexing.

LeetCode 323: Number of Connected Components in an Undirected Graph

A clear explanation of counting connected components using Union-Find and graph traversal.

LeetCode 322: Coin Change

A clear explanation of Coin Change using dynamic programming for minimum coin count.

LeetCode 321: Create Maximum Number

A clear explanation of Create Maximum Number using monotonic stacks for subsequences and greedy merging.

LeetCode 320: Generalized Abbreviation

A clear explanation of Generalized Abbreviation using backtracking to choose whether each character is kept or abbreviated.

LeetCode 319: Bulb Switcher

A clear explanation of Bulb Switcher using divisor parity and perfect squares.

LeetCode 318: Maximum Product of Word Lengths

A clear explanation of Maximum Product of Word Lengths using bit masks to test disjoint character sets efficiently.

LeetCode 317: Shortest Distance from All Buildings

A clear explanation of Shortest Distance from All Buildings using BFS from each building with distance and reach accumulation.

LeetCode 316: Remove Duplicate Letters

A clear explanation of Remove Duplicate Letters using a greedy monotonic stack.

LeetCode 315: Count of Smaller Numbers After Self

A clear explanation of Count of Smaller Numbers After Self using coordinate compression and a Fenwick Tree.

LeetCode 314: Binary Tree Vertical Order Traversal

A clear explanation of Binary Tree Vertical Order Traversal using BFS with column indices.

LeetCode 313: Super Ugly Number

A clear explanation of Super Ugly Number using dynamic programming with one pointer per prime.

LeetCode 312: Burst Balloons

A clear explanation of Burst Balloons using interval dynamic programming and the last-burst idea.

LeetCode 311: Sparse Matrix Multiplication

A clear explanation of Sparse Matrix Multiplication using non-zero entries to avoid wasted work.

LeetCode 310: Minimum Height Trees

A clear explanation of Minimum Height Trees using leaf trimming to find the center of a tree.

LeetCode 309: Best Time to Buy and Sell Stock with Cooldown

A clear explanation of Best Time to Buy and Sell Stock with Cooldown using dynamic programming states.

LeetCode 308: Range Sum Query 2D - Mutable

A clear explanation of Range Sum Query 2D - Mutable using a 2D Fenwick Tree for efficient updates and rectangle sum queries.

LeetCode 307: Range Sum Query - Mutable

A clear explanation of Range Sum Query - Mutable using a Fenwick Tree for efficient updates and range sums.

LeetCode 306: Additive Number

A clear explanation of Additive Number using split enumeration and deterministic checking.

LeetCode 305: Number of Islands II

A clear explanation of Number of Islands II using Union-Find to dynamically merge connected land cells.

LeetCode 304: Range Sum Query 2D - Immutable

A clear explanation of Range Sum Query 2D - Immutable using a 2D prefix sum matrix for constant-time rectangle queries.

LeetCode 303: Range Sum Query - Immutable

A clear explanation of Range Sum Query - Immutable using prefix sums for constant-time range queries.

LeetCode 302: Smallest Rectangle Enclosing Black Pixels

A clear explanation of Smallest Rectangle Enclosing Black Pixels using binary search on rows and columns.

LeetCode 301: Remove Invalid Parentheses

A clear explanation of Remove Invalid Parentheses using BFS to guarantee the minimum number of removals.

LeetCode 300: Longest Increasing Subsequence

A dynamic programming and patience sorting solution for finding the longest strictly increasing subsequence in an array.

LeetCode 299: Bulls and Cows

A counting solution for producing the Bulls and Cows hint while handling duplicate digits correctly.

LeetCode 298: Binary Tree Longest Consecutive Sequence

A DFS solution for finding the longest parent-to-child path where each node value increases by exactly one.

LeetCode 297: Serialize and Deserialize Binary Tree

A preorder DFS codec for converting a binary tree to a string and reconstructing the same tree from that string.

LeetCode 296: Best Meeting Point

A median-based solution for minimizing total Manhattan distance in a grid.

LeetCode 295: Find Median from Data Stream

A two-heap data structure for adding numbers from a stream and returning the current median in constant time.

LeetCode 294: Flip Game II

A recursive game theory solution with memoization for deciding whether the starting player can force a win.

LeetCode 293: Flip Game

A simple string scanning solution for generating every possible next state after flipping one consecutive ++ pair into --.

LeetCode 292: Nim Game

A game theory solution for deciding whether the first player can win by using the losing-position pattern of multiples of four.

LeetCode 291: Word Pattern II

A backtracking solution for matching a pattern string to a target string using a bijective character-to-substring mapping.

LeetCode 290: Word Pattern

A hash map solution for checking whether a pattern string and a space-separated word string form a bijection.

LeetCode 289: Game of Life

An in-place matrix simulation for computing the next state of Conway's Game of Life using temporary encoded states.

LeetCode 288: Unique Word Abbreviation

A hash map design for checking whether a word's abbreviation is unique in a dictionary.

LeetCode 287: Find the Duplicate Number

A Floyd cycle detection solution for finding the repeated number without modifying the array and using constant extra space.

LeetCode 286: Walls and Gates

A multi-source BFS solution for filling each empty room with its shortest distance to the nearest gate.

LeetCode 285: Inorder Successor in BST

A binary-search-style solution for finding the smallest node greater than p in a binary search tree.

LeetCode 284: Peeking Iterator

A wrapper iterator design that supports peeking at the next element without advancing the iterator.

LeetCode 283: Move Zeroes

A two-pointer in-place solution for moving all zeroes to the end while preserving the relative order of non-zero elements.

LeetCode 282: Expression Add Operators

A backtracking solution for inserting operators into a numeric string so the expression evaluates to a target value.

LeetCode 281: Zigzag Iterator

A queue-based iterator design for returning elements from two vectors in alternating order, with a clean extension to k vectors.

LeetCode 280: Wiggle Sort

A greedy in-place solution for rearranging an array into a non-strict wiggle pattern.

LeetCode 279: Perfect Squares

A dynamic programming solution for finding the least number of perfect square numbers that sum to n.

LeetCode 278: First Bad Version

A binary search solution for finding the first bad version while minimizing calls to the isBadVersion API.

LeetCode 277: Find the Celebrity

A two-pass solution for finding a celebrity using the knows API with O(n) calls and O(1) extra space.

LeetCode 276: Paint Fence

A dynamic programming solution for counting ways to paint fence posts with no more than two adjacent posts sharing the same color.

LeetCode 275: H-Index II

A clear explanation of the H-Index II problem using binary search on a sorted citations array.

LeetCode 274: H-Index

A clear explanation of the H-Index problem using sorting, then an optimized counting approach.

LeetCode 273: Integer to English Words

A clear explanation of the Integer to English Words problem using three-digit chunks and scale words.

LeetCode 272: Closest Binary Search Tree Value II

A clear explanation of the Closest Binary Search Tree Value II problem using inorder traversal and a fixed-size sliding window.

LeetCode 271: Encode and Decode Strings

A clear explanation of the Encode and Decode Strings problem using length-prefix encoding.

LeetCode 270: Closest Binary Search Tree Value

A clear explanation of the Closest Binary Search Tree Value problem using the BST property to walk toward the target.

LeetCode 269: Alien Dictionary

A clear explanation of the Alien Dictionary problem using graph construction and topological sorting.

LeetCode 268: Missing Number

A clear explanation of the Missing Number problem using sum formula and XOR.

LeetCode 267: Palindrome Permutation II

A clear explanation of the Palindrome Permutation II problem using character counts and backtracking over half of the palindrome.

LeetCode 266: Palindrome Permutation

A clear explanation of the Palindrome Permutation problem using character parity counting.

LeetCode 265: Paint House II

A clear explanation of the Paint House II problem using optimized dynamic programming with minimum and second minimum tracking.

LeetCode 264: Ugly Number II

A clear explanation of the Ugly Number II problem using dynamic programming with three pointers.

LeetCode 263: Ugly Number

A clear explanation of the Ugly Number problem using repeated division by the only allowed prime factors.

LeetCode 261: Graph Valid Tree

A clear explanation of the Graph Valid Tree problem using Union Find to detect cycles and verify connectivity.

LeetCode 260: Single Number III

A clear explanation of the Single Number III problem using XOR partitioning to isolate the two unique numbers.

LeetCode 259: 3Sum Smaller

A clear explanation of the 3Sum Smaller problem using sorting and the two-pointer technique.

LeetCode 258: Add Digits

A clear explanation of the Add Digits problem using repeated digit sums first, then the digital root formula.

LeetCode 257: Binary Tree Paths

A clear explanation of the Binary Tree Paths problem using DFS backtracking to collect every root-to-leaf path.

LeetCode 256: Paint House

A clear explanation of the Paint House problem using dynamic programming with constant space.

LeetCode 255: Verify Preorder Sequence in Binary Search Tree

A clear explanation of the Verify Preorder Sequence in Binary Search Tree problem using a monotonic stack and lower bound tracking.

LeetCode 254: Factor Combinations

A clear explanation of the Factor Combinations problem using DFS backtracking with non-decreasing factors.

LeetCode 253: Meeting Rooms II

A clear explanation of the Meeting Rooms II problem using a min heap to track active meeting end times.

LeetCode 252: Meeting Rooms

A clear explanation of the Meeting Rooms problem using interval sorting to detect overlaps.

LeetCode 251: Flatten 2D Vector

A clear explanation of the Flatten 2D Vector problem using row and column pointers to implement an iterator.

LeetCode 225: Implement Stack using Queues

A clear explanation of implementing a LIFO stack using only FIFO queue operations.

LeetCode 224: Basic Calculator

A clear explanation of evaluating an expression with plus, minus, spaces, and parentheses using a stack.

LeetCode 223: Rectangle Area

A clear explanation of computing the total covered area of two axis-aligned rectangles by subtracting their overlap.

LeetCode 222: Count Complete Tree Nodes

A clear explanation of counting nodes in a complete binary tree faster than visiting every node.

LeetCode 221: Maximal Square

A clear explanation of finding the largest square of 1s in a binary matrix using dynamic programming.

LeetCode 220: Contains Duplicate III

A clear explanation of checking nearby indices with nearby values using a sliding window and bucket hashing.

LeetCode 219: Contains Duplicate II

A clear explanation of detecting whether equal values appear within distance k using a hash map or sliding window set.

LeetCode 218: The Skyline Problem

A clear explanation of computing the skyline formed by buildings using sweep line and a max-heap.

LeetCode 217: Contains Duplicate

A clear explanation of detecting duplicates in an array using a hash set and sorting.

LeetCode 216: Combination Sum III

A clear explanation of finding k distinct numbers from 1 to 9 that sum to n using backtracking.

LeetCode 215: Kth Largest Element in an Array

A clear explanation of finding the kth largest element using sorting, a min-heap, and Quickselect.

LeetCode 214: Shortest Palindrome

A clear explanation of building the shortest palindrome by finding the longest palindromic prefix using KMP.

LeetCode 213: House Robber II

A clear explanation of maximizing robbed money from circularly arranged houses using dynamic programming.

LeetCode 212: Word Search II

A clear explanation of finding multiple words in a character board using a Trie and DFS backtracking.

LeetCode 211: Design Add and Search Words Data Structure

A clear explanation of designing a word dictionary with addWord and wildcard search using a Trie and DFS.

LeetCode 210: Course Schedule II

A clear explanation of finding a valid course ordering using topological sorting and cycle detection.

LeetCode 209: Minimum Size Subarray Sum

A clear explanation of finding the shortest contiguous subarray whose sum is at least target using a sliding window.

LeetCode 208: Implement Trie Prefix Tree

A clear explanation of implementing a Trie with insert, search, and startsWith operations.

LeetCode 207: Course Schedule

A clear explanation of detecting cycles in a prerequisite graph using topological sorting and DFS.

LeetCode 206: Reverse Linked List

A clear explanation of reversing a singly linked list using iterative and recursive approaches.

LeetCode 205: Isomorphic Strings

A clear explanation of checking whether two strings follow the same character mapping pattern.

LeetCode 204: Count Primes

A clear explanation of counting prime numbers less than n using the Sieve of Eratosthenes.

LeetCode 203: Remove Linked List Elements

A clear explanation of removing all linked list nodes with a target value using iteration and a dummy node.

LeetCode 202: Happy Number

A clear explanation of detecting whether repeated digit-square sums eventually reach 1.

LeetCode 201: Bitwise AND of Numbers Range

A clear explanation of finding the bitwise AND of every number in an inclusive range using the common binary prefix.

LeetCode 100: Same Tree

A detailed guide to solving Same Tree with recursive DFS and structural comparison.

LeetCode 99: Recover Binary Search Tree

A detailed guide to solving Recover Binary Search Tree with inorder traversal and two misplaced nodes.

LeetCode 98: Validate Binary Search Tree

A detailed guide to solving Validate Binary Search Tree with recursive lower and upper bounds.

LeetCode 97: Interleaving String

A detailed guide to solving Interleaving String with two-dimensional dynamic programming.

LeetCode 96: Unique Binary Search Trees

A detailed guide to solving Unique Binary Search Trees with dynamic programming and the Catalan recurrence.

LeetCode 95: Unique Binary Search Trees II

A detailed guide to solving Unique Binary Search Trees II with recursive tree generation over value ranges.

LeetCode 94: Binary Tree Inorder Traversal

A detailed guide to solving Binary Tree Inorder Traversal with recursion and an iterative stack.

LeetCode 93: Restore IP Addresses

A detailed guide to solving Restore IP Addresses with backtracking over four valid IP segments.

LeetCode 92: Reverse Linked List II

A detailed guide to solving Reverse Linked List II with a dummy node and in-place sublist reversal.

LeetCode 91: Decode Ways

A detailed guide to solving Decode Ways with dynamic programming and careful handling of zeroes.

LeetCode 90: Subsets II

A detailed guide to solving Subsets II with sorting, backtracking, and duplicate skipping.

LeetCode 89: Gray Code

A detailed guide to solving Gray Code using the binary-to-Gray-code formula.

LeetCode 88: Merge Sorted Array

A detailed guide to solving Merge Sorted Array in-place by merging from the back with three pointers.

LeetCode 87: Scramble String

A detailed guide to solving Scramble String with recursive dynamic programming and memoization.

LeetCode 86: Partition List

A detailed guide to solving Partition List with two dummy lists while preserving relative order.

LeetCode 85: Maximal Rectangle

A detailed guide to solving Maximal Rectangle by converting each matrix row into a histogram and applying a monotonic stack.

LeetCode 84: Largest Rectangle in Histogram

A detailed guide to solving Largest Rectangle in Histogram with a monotonic increasing stack.

LeetCode 83: Remove Duplicates from Sorted List

A detailed guide to solving Remove Duplicates from Sorted List with one pointer and in-place linked list rewiring.

LeetCode 82: Remove Duplicates from Sorted List II

A detailed guide to solving Remove Duplicates from Sorted List II with a dummy node and pointer rewiring.

LeetCode 81: Search in Rotated Sorted Array II

A detailed guide to solving Search in Rotated Sorted Array II with modified binary search and duplicate handling.

LeetCode 80: Remove Duplicates from Sorted Array II

A detailed guide to solving Remove Duplicates from Sorted Array II with an in-place two-pointer method.

LeetCode 79: Word Search

A detailed guide to solving Word Search with depth-first search and backtracking on a grid.

LeetCode 78: Subsets

A detailed guide to solving Subsets with backtracking and the include-or-skip recursion idea.

LeetCode 77: Combinations

A detailed guide to solving Combinations with backtracking and pruning.

LeetCode 76: Minimum Window Substring

A detailed guide to solving Minimum Window Substring with a sliding window and frequency counters.

LeetCode 262: Trips and Users

A clear explanation of the Trips and Users SQL problem using joins, filtering, grouping, and conditional aggregation.

LeetCode 200: Number of Islands

A clear explanation of counting connected groups of land cells in a grid using DFS or BFS.

LeetCode 199: Binary Tree Right Side View

A clear explanation of returning the visible nodes from the right side of a binary tree using level-order traversal.

LeetCode 198: House Robber

A clear explanation of maximizing robbery profit without robbing adjacent houses using dynamic programming.

LeetCode 191: Number of 1 Bits

A clear explanation of counting set bits in an integer using bit manipulation and Brian Kernighan's algorithm.

LeetCode 190: Reverse Bits

A clear explanation of reversing the bits of a 32-bit integer using bit manipulation.

LeetCode 189: Rotate Array

A clear explanation of rotating an array to the right by k steps using in-place reversal.

LeetCode 188: Best Time to Buy and Sell Stock IV

A clear explanation of maximizing stock trading profit with at most k transactions using dynamic programming.

LeetCode 187: Repeated DNA Sequences

A clear explanation of finding repeated 10-letter DNA substrings using a fixed-size sliding window and hash sets.

LeetCode 186: Reverse Words in a String II

A clear explanation of reversing the order of words in a character array in-place using two reversals.

LeetCode 179: Largest Number

A clear explanation of arranging non-negative integers to form the largest possible concatenated number using a custom sort order.

LeetCode 174: Dungeon Game

A clear explanation of computing the minimum initial health needed to survive a dungeon using reverse dynamic programming.

LeetCode 173: Binary Search Tree Iterator

A clear explanation of designing an iterator over a BST using controlled inorder traversal with a stack.

LeetCode 171: Excel Sheet Column Number

A clear explanation of converting an Excel column title into its numeric index using base 26 accumulation.

LeetCode 170: Two Sum III - Data Structure Design

A clear explanation of designing a data structure that supports add and find operations for pair sums.

LeetCode 169: Majority Element

A clear explanation of finding the element that appears more than half the time using Boyer-Moore voting.

LeetCode 168: Excel Sheet Column Title

A clear explanation of converting a positive integer into an Excel column title using bijective base 26.

LeetCode 167: Two Sum II - Input Array Is Sorted

A clear explanation of finding two numbers in a sorted array using two pointers and constant extra space.

LeetCode 166: Fraction to Recurring Decimal

A clear explanation of converting a fraction into decimal form and detecting repeating fractional parts with a hash map.

LeetCode 165: Compare Version Numbers

A clear explanation of comparing version strings revision by revision while ignoring leading zeros.

LeetCode 164: Maximum Gap

A clear explanation of finding the maximum adjacent gap in sorted order using buckets and the pigeonhole principle.

LeetCode 163: Missing Ranges

A clear explanation of finding all missing ranges inside an inclusive interval by scanning sorted unique numbers.

LeetCode 162: Find Peak Element

A clear explanation of finding any peak element using binary search on the slope of the array.

LeetCode 161: One Edit Distance

A clear explanation of checking whether two strings are exactly one edit apart using a linear scan.

LeetCode 160: Intersection of Two Linked Lists

A clear explanation of finding the node where two singly linked lists intersect using two pointers.

LeetCode 159: Longest Substring with At Most Two Distinct Characters

A clear explanation of finding the longest substring with at most two distinct characters using a sliding window.

LeetCode 158: Read N Characters Given read4 II - Call Multiple Times

A clear explanation of implementing read with read4 when read may be called multiple times.

LeetCode 157: Read N Characters Given Read4

A clear explanation of implementing read using the given read4 API and copying only the needed characters.

LeetCode 156: Binary Tree Upside Down

A clear explanation of flipping a binary tree upside down by rewiring pointers from the left spine.

LeetCode 155: Min Stack

A clear explanation of designing a stack that can return the current minimum element in constant time.

LeetCode 154: Find Minimum in Rotated Sorted Array II

A clear explanation of finding the minimum element in a rotated sorted array that may contain duplicates.

LeetCode 153: Find Minimum in Rotated Sorted Array

A clear explanation of finding the minimum element in a rotated sorted array using binary search.

LeetCode 152: Maximum Product Subarray

A detailed explanation of tracking both maximum and minimum products while scanning the array.

LeetCode 151: Reverse Words in a String

A clear explanation of reversing word order while removing extra spaces.

LeetCode 150: Evaluate Reverse Polish Notation

Evaluate an arithmetic expression written in Reverse Polish Notation using a stack.

LeetCode 149: Max Points on a Line

Find the maximum number of points lying on the same straight line using slope counting and normalization.

LeetCode 148: Sort List

Sort a singly linked list in ascending order using merge sort with fast and slow pointers.

LeetCode 147: Insertion Sort List

Sort a singly linked list using insertion sort by splicing each node into a growing sorted list.

LeetCode 146: LRU Cache

Design an LRU cache with O(1) get and put operations using a hash map and doubly linked list.

LeetCode 145: Binary Tree Postorder Traversal

Return the postorder traversal of a binary tree using recursion or an iterative stack-based approach.

LeetCode 144: Binary Tree Preorder Traversal

Return the preorder traversal of a binary tree using recursion or an explicit stack.

LeetCode 143: Reorder List

Reorder a singly linked list in-place by finding the middle, reversing the second half, and merging the two halves alternately.

LeetCode 142: Linked List Cycle II

Find the node where a linked list cycle begins using Floyd’s tortoise and hare algorithm with cycle entry mathematics.

LeetCode 141: Linked List Cycle

Detect whether a linked list contains a cycle using Floyd’s tortoise and hare two-pointer algorithm.

LeetCode 140: Word Break II

Return all valid sentences formed by inserting spaces into a string so every word belongs to the dictionary, using DFS with memoization.

LeetCode 139: Word Break

Decide whether a string can be segmented into dictionary words using dynamic programming over prefixes.

LeetCode 138: Copy List with Random Pointer

Create a deep copy of a linked list with next and random pointers using hash maps or interleaved node cloning.

LeetCode 137: Single Number II

Find the number that appears once when every other number appears three times using bit counting or finite-state bit manipulation.

LeetCode 136: Single Number

Find the only number that appears once using the XOR operator, while every other number appears exactly twice.

LeetCode 135: Candy

Compute the minimum candies needed using two greedy passes, one from the left and one from the right.

LeetCode 134: Gas Station

Find the unique starting gas station index using a greedy scan with total fuel balance and current tank balance.

LeetCode 133: Clone Graph

Create a deep copy of a connected undirected graph using DFS and a hash map from original nodes to cloned nodes.

LeetCode 132: Palindrome Partitioning II

Find the minimum number of cuts needed to split a string into palindromic substrings using palindrome precomputation and dynamic programming.

LeetCode 131: Palindrome Partitioning

Generate all ways to split a string so that every piece is a palindrome, using backtracking with palindrome precomputation.

LeetCode 130: Surrounded Regions

Capture surrounded O regions by marking border-connected O cells first, then flipping the remaining O cells.

LeetCode 129: Sum Root to Leaf Numbers

Compute the sum of all numbers formed by root-to-leaf paths using depth-first search and decimal accumulation.

LeetCode 128: Longest Consecutive Sequence

Find the longest run of consecutive integers in an unsorted array using a hash set and sequence-start detection.

LeetCode 127: Word Ladder

Use breadth-first search to find the shortest transformation sequence length between two words.

LeetCode 126: Word Ladder II

Find all shortest word transformation sequences using BFS to build shortest-path parents, then backtracking to reconstruct every answer.

LeetCode 125: Valid Palindrome

A clear explanation of checking whether a string is a palindrome after ignoring non-alphanumeric characters and case.

LeetCode 124: Binary Tree Maximum Path Sum

A clear explanation of finding the maximum path sum in a binary tree using bottom-up depth-first search.

LeetCode 123: Best Time to Buy and Sell Stock III

A clear explanation of maximizing stock profit with at most two transactions using dynamic programming.

LeetCode 122: Best Time to Buy and Sell Stock II

A clear explanation of maximizing stock profit with unlimited transactions using a greedy single-pass method.

LeetCode 121: Best Time to Buy and Sell Stock

A clear explanation of finding the maximum profit from one stock transaction using a single pass.

LeetCode 120: Triangle

A clear explanation of finding the minimum path sum in a triangle using bottom-up dynamic programming.

LeetCode 119: Pascal's Triangle II

A clear explanation of generating a single row of Pascal's Triangle using in-place dynamic programming.

LeetCode 118: Pascal's Triangle

A clear explanation of generating Pascal's Triangle row by row using dynamic programming.

LeetCode 117: Populating Next Right Pointers in Each Node II

A clear explanation of connecting next pointers in any binary tree using constant extra space.

LeetCode 116: Populating Next Right Pointers in Each Node

A clear explanation of connecting next pointers in a perfect binary tree using constant extra space.

LeetCode 115: Distinct Subsequences

A clear explanation of counting distinct subsequences using dynamic programming.

LeetCode 114: Flatten Binary Tree to Linked List

A clear explanation of flattening a binary tree into a linked list in preorder traversal order using recursive depth-first search.

LeetCode 113: Path Sum II

A clear explanation of finding all root-to-leaf paths whose values add up to a target sum using depth-first search and backtracking.

LeetCode 112: Path Sum

A clear explanation of checking whether a binary tree has a root-to-leaf path whose values add up to a target sum.

LeetCode 111: Minimum Depth of Binary Tree

A clear explanation of finding the minimum depth of a binary tree using breadth-first search.

LeetCode 110: Balanced Binary Tree

A clear explanation of checking whether a binary tree is height-balanced using bottom-up depth-first search.

LeetCode 109: Convert Sorted List to Binary Search Tree

A clear explanation of converting a sorted linked list into a height-balanced binary search tree using slow and fast pointers.

LeetCode 108: Convert Sorted Array to Binary Search Tree

A clear explanation of building a height-balanced binary search tree from a sorted array using divide and conquer.

LeetCode 107: Binary Tree Level Order Traversal II

A clear explanation of returning binary tree levels from bottom to top using breadth-first search.

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

A clear explanation of rebuilding a binary tree from inorder and postorder traversals using recursion and an index map.

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

A clear explanation of rebuilding a binary tree from preorder and inorder traversals using recursion and an index map.

LeetCode 104: Maximum Depth of Binary Tree

A clear explanation of finding the maximum depth of a binary tree using recursive depth-first search.

LeetCode 103: Binary Tree Zigzag Level Order Traversal

A clear explanation of zigzag level order traversal using breadth-first search and alternating level direction.

LeetCode 102: Binary Tree Level Order Traversal

A clear explanation of binary tree level order traversal using breadth-first search and a queue.

LeetCode 101: Symmetric Tree

A clear explanation of checking whether a binary tree is symmetric using mirror recursion.

LeetCode 75: Sort Colors

A clear guide to sorting an array of 0s, 1s, and 2s in place using the Dutch National Flag algorithm.

LeetCode 74: Search a 2D Matrix

A clear guide to searching a sorted 2D matrix using binary search over a virtual one-dimensional array.

LeetCode 73: Set Matrix Zeroes

A clear guide to setting matrix rows and columns to zero in place using the first row and first column as markers.

LeetCode 72: Edit Distance

A clear guide to computing the minimum number of insert, delete, and replace operations needed to convert one string into another.

LeetCode 71: Simplify Path

A clear guide to simplifying Unix-style file paths using a stack.

LeetCode 70: Climbing Stairs

A clear guide to counting distinct ways to climb stairs using dynamic programming.

LeetCode 69: Sqrt(x)

A clear guide to computing the integer square root using binary search without built-in exponent functions.

LeetCode 68: Text Justification

A clear guide to formatting text with greedy line packing and even space distribution.

LeetCode 67: Add Binary

A clear guide to adding two binary strings using two pointers and a carry.

LeetCode 66: Plus One

A clear guide to adding one to a large integer represented as an array of digits.

LeetCode 65: Valid Number

A clear guide to validating whether a string is a valid number using grammar rules and one left-to-right scan.

LeetCode 64: Minimum Path Sum

A clear guide to finding the minimum path sum in a grid using dynamic programming.

LeetCode 63: Unique Paths II

A clear guide to counting unique paths in a grid with obstacles using dynamic programming.

LeetCode 62: Unique Paths

A clear guide to counting unique paths in a grid using dynamic programming.

LeetCode 61: Rotate List

A clear guide to rotating a linked list to the right by k places using a circular list.

LeetCode 60: Permutation Sequence

A clear guide to finding the kth permutation sequence using factorial blocks instead of generating all permutations.

LeetCode 59: Spiral Matrix II

A clear guide to generating an n x n matrix filled from 1 to n squared in spiral order.

LeetCode 58: Length of Last Word

A clear guide to solving Length of Last Word by scanning the string from right to left.

LeetCode 57: Insert Interval

A clear guide to solving Insert Interval with one linear scan over sorted, non-overlapping intervals.

LeetCode 56: Merge Intervals

A clear guide to solving Merge Intervals by sorting intervals and merging them in one pass.

LeetCode 55: Jump Game

A clear guide to solving Jump Game with greedy reachability.

LeetCode 54: Spiral Matrix

A clear guide to reading a matrix in spiral order using shrinking boundaries.

LeetCode 53: Maximum Subarray

A clear guide to solving Maximum Subarray with brute force first, then Kadane's dynamic programming algorithm.

LeetCode 52: N-Queens II

A clear guide to solving N-Queens II by counting valid queen placements with backtracking.

LeetCode 51: N-Queens

A clear guide to solving N-Queens with backtracking, row-by-row placement, and constant-time conflict checks.

LeetCode 40: Combination Sum II

A clear explanation of finding unique combinations that sum to a target when each array element may be used at most once.

LeetCode 39: Combination Sum

A clear explanation of finding all unique combinations that sum to a target using backtracking.

LeetCode 38: Count and Say

A clear explanation of generating the count-and-say sequence using run-length encoding.

LeetCode 37: Sudoku Solver

A clear explanation of solving a Sudoku board using backtracking and constraint checking.

LeetCode 36: Valid Sudoku

A clear explanation of checking whether a partially filled Sudoku board is valid using hash sets.

LeetCode 35: Search Insert Position

A clear explanation of finding the index of a target, or where it should be inserted, using binary search.

LeetCode 34: Find First and Last Position of Element in Sorted Array

A clear explanation of finding the first and last index of a target in a sorted array using two binary searches.

LeetCode 33: Search in Rotated Sorted Array

A clear explanation of searching a rotated sorted array in logarithmic time using modified binary search.

LeetCode 32: Longest Valid Parentheses

A clear explanation of finding the longest well-formed parentheses substring using a stack of indices.

LeetCode 31: Next Permutation

A clear explanation of finding the next lexicographically greater permutation in place using a right-to-left scan.

LeetCode 30: Substring with Concatenation of All Words

A clear explanation of finding all starting indices where a substring is formed by concatenating every word exactly once.

LeetCode 29: Divide Two Integers

A clear explanation of integer division without using multiplication, division, or modulo, using repeated doubling with bit shifts.

LeetCode 28: Find the Index of the First Occurrence in a String

A clear explanation of finding the first occurrence of one string inside another using direct string matching.

LeetCode 27: Remove Element

A clear explanation of removing all occurrences of a value from an array in place using a write pointer.

LeetCode 26: Remove Duplicates from Sorted Array

A clear explanation of removing duplicates from a sorted array in place using two pointers.

LeetCode 25: Reverse Nodes in k-Group

A detailed explanation of reversing linked-list nodes in groups of k using pointer manipulation and constant extra space.

LeetCode 24: Swap Nodes in Pairs

A detailed explanation of swapping every two adjacent nodes in a linked list using pointer manipulation.

LeetCode 23: Merge k Sorted Lists

A detailed explanation of merging k sorted linked lists using a min heap.

LeetCode 22: Generate Parentheses

A detailed explanation of generating all well-formed parentheses strings using backtracking.

LeetCode 21: Merge Two Sorted Lists

A detailed explanation of merging two sorted linked lists using a dummy node and pointer splicing.

LeetCode 20: Valid Parentheses

A detailed explanation of checking whether a bracket string is valid using a stack.

LeetCode 19: Remove Nth Node From End of List

A detailed explanation of removing the nth node from the end of a singly linked list using two pointers and a dummy node.

LeetCode 18: 4Sum

A detailed explanation of finding all unique quadruplets that sum to a target using sorting and two pointers.

LeetCode 17: Letter Combinations of a Phone Number

A detailed explanation of generating all possible phone keypad letter combinations using backtracking.

LeetCode 16: 3Sum Closest

A detailed explanation of finding the sum of three integers closest to a target using sorting and two pointers.

LeetCode 15: 3Sum

A detailed explanation of finding all unique triplets that sum to zero using sorting and two pointers.

LeetCode 14: Longest Common Prefix

A detailed explanation of finding the longest common prefix among an array of strings by comparing characters column by column.

LeetCode 13: Roman to Integer

A detailed explanation of converting a Roman numeral string into an integer using symbol values and the subtraction rule.

LeetCode 12: Integer to Roman

A detailed explanation of converting an integer into a Roman numeral using a fixed value-symbol table and greedy subtraction.

LeetCode 11: Container With Most Water

A detailed explanation of finding the maximum water container area using two pointers.

LeetCode 10: Regular Expression Matching

A detailed explanation of matching a full string against a simplified regular expression with dot and star using dynamic programming.

LeetCode 9: Palindrome Number

A detailed explanation of checking whether an integer is a palindrome using digit operations without converting it to a string.

LeetCode 8: String to Integer (atoi)

A detailed explanation of parsing a string into a 32-bit signed integer with whitespace, sign, digit reading, and clamping rules.

LeetCode 7: Reverse Integer

A detailed explanation of reversing a signed 32-bit integer while handling overflow correctly.

LeetCode 6: Zigzag Conversion

A detailed explanation of converting a string into a zigzag pattern using row simulation.

LeetCode 5: Longest Palindromic Substring

A detailed explanation of finding the longest palindromic substring using expand-around-center.

LeetCode 4: Median of Two Sorted Arrays

A detailed explanation of finding the median of two sorted arrays using binary search over partitions.

LeetCode 3: Longest Substring Without Repeating Characters

A clear explanation of the longest substring problem using sliding window and a hash set.

LeetCode 2: Add Two Numbers

A detailed explanation of the Add Two Numbers linked list problem, including digit-by-digit addition, carry handling, and linked list construction.

LeetCode 1: Two Sum

A clear explanation of the Two Sum problem using brute force first, then an optimized hash map solution.

LeetCode 172: Factorial Trailing Zeroes

A clear explanation of counting trailing zeroes in n! by counting factors of 5 instead of computing the factorial directly.

LeetCode 185: Department Top Three Salaries

A clear SQL solution for finding employees whose salaries are in the top three unique salary levels within their department.

LeetCode 184: Department Highest Salary

A clear SQL solution for finding every employee who earns the highest salary in their department.

LeetCode 183: Customers Who Never Order

A clear SQL solution for finding customers who have no matching rows in the Orders table.

LeetCode 182: Duplicate Emails

A clear SQL solution for reporting email values that appear more than once in the Person table.

LeetCode 181: Employees Earning More Than Their Managers

A clear SQL solution for finding employees whose salary is greater than their manager's salary using a self join.

LeetCode 180: Consecutive Numbers

A clear SQL solution for finding numbers that appear at least three times consecutively in the Logs table.

LeetCode 178: Rank Scores

A clear SQL solution for ranking scores with dense ranking, where ties share the same rank and no rank numbers are skipped.

LeetCode 177: Nth Highest Salary

A clear SQL solution for finding the nth highest distinct salary from the Employee table.

LeetCode 176: Second Highest Salary

A clear SQL solution for finding the second highest distinct salary from the Employee table.

CPU and GPU Tensors

PyTorch tensors live on devices. A device is the hardware location where tensor storage exists and where tensor operations execute.

Tensor Memory Layout and Performance

A tensor has a logical shape and a physical memory layout. The shape tells us how to interpret the tensor as an array. The memory layout tells us how the entries are stored in memory.

Symbolic Versus Dynamic Computation

Deep learning frameworks need a way to represent computation.

Data Leakage and Experimental Design

Data leakage occurs when information that should be unavailable during training or evaluation enters the modeling process. It causes performance estimates to look better than they really are.

Weight Decay and Regularization

Training loss measures how well a model fits the training data.

Tensor Data Types and Devices

A tensor has values, shape, data type, and device placement.

Summary and Further Reading

Attention is a differentiable retrieval mechanism. A query asks for information, keys define where information can be found, and values carry the content returned to the model.

Structure of a PyTorch Project

A PyTorch project should separate concerns. Model code should define computation.

Stochastic Depth

Stochastic depth regularizes deep residual networks by randomly skipping residual branches during training.

Retrieval-Augmented Generation

Retrieval-augmented generation, usually abbreviated RAG, combines a language model with an external information retrieval system.

Pretraining Objectives

A pretraining objective defines the prediction task used to train a model before it is adapted to a downstream use case.

Language Modeling

Language modeling is the task of predicting text sequences. A language model assigns probabilities to sequences of tokens and learns the statistical structure of language.

Inference Optimization

Training produces model parameters. Inference uses those parameters to generate predictions.

Evaluation Metrics

Evaluation metrics convert model behavior into numbers. A loss function guides training. A metric reports performance. Sometimes they are the same. Often they are different.

Early diffusion systems used convolutional U-Nets as denoising networks. U-Nets worked well because images contain strong local structure, and convolutions efficiently model nearby spatial relationships.

Choosing and Combining Loss Functions

A loss function defines what the model is trained to improve. It translates a modeling goal into a scalar value that can be minimized by gradient-based optimization.

Automatic Differentiation Engines

An automatic differentiation engine is the system that records numerical operations and computes derivatives from them.

Video Diffusion Systems

Video diffusion extends image diffusion from still images to moving sequences. Instead of generating one image, the model generates a sequence of frames that should remain visually coherent over time.

Training Foundation Models

Foundation models are large neural networks trained on broad datasets and adapted to many downstream tasks.

Tool Use and Agents

A language model becomes more useful when it can interact with external systems.

Summary and Further Reading

Probabilistic deep learning extends neural networks with explicit probability models.

Stable Training in Deep Networks

Stable training means that a model can make steady progress without numerical collapse, uncontrolled gradients, or large oscillations in the loss.

Sparse Expert Architectures

Dense transformers activate every parameter for every token.

Self-Supervised Objectives

Self-supervised learning trains a model using supervision constructed from the data itself. Instead of requiring human labels, the training task is derived from structure already present in the input.

Random Tensor Generation

Random tensors are used throughout deep learning. They initialize parameters, shuffle examples, sample noise, apply dropout, augment data, and generate outputs from probabilistic models.

Practical Activation Selection

Activation functions should be chosen for the architecture, loss, initialization, normalization, and training scale. There is no universal best activation. The right choice depends on what the layer must do.

Overfitting and Underfitting

Overfitting and underfitting describe two common ways a model can fail.

Mixup and CutMix

Mixup and CutMix are data augmentation methods that create new training examples by combining two examples and their labels. They regularize the model by discouraging overly sharp decision boundaries.

Limits of Linear Models

Linear models are the first useful class of predictive models in deep learning.

Learning Rate Scheduling

The learning rate controls the size of each parameter update.

Installing and Configuring PyTorch

A PyTorch installation must match three things: the Python environment, the operating system, and the available hardware.

Gradient Flow in Deep Networks

Gradient flow describes how derivative information moves backward through a neural network during training.

Exercises

---

Embeddings and Output Projections

After tokenization, text is represented as integer token IDs.

Efficient Convolutions

Efficient convolutions reduce computation, memory use, or latency while preserving useful spatial modeling.

Efficient Attention Methods

Standard self-attention compares every token with every other token. For a sequence of length $T$, this produces a $T \times T$ attention matrix. The cost grows quadratically with sequence length.

Cross-Lingual Transfer

Cross-lingual transfer is the ability of a model trained or adapted in one language to work in another language.

Conversational Systems

A conversational system processes dialogue between users and machines.

Automated Machine Learning

Automated machine learning, or AutoML, refers to systems that automate parts of the model development process.

Attention Complexity

Attention gives a model direct access between positions in a sequence.

Transformer Decoders

A transformer decoder maps a partial output sequence to predictions for the next token or next output step.

Text-to-Image Systems

Text-to-image generation aims to synthesize images from natural language descriptions. A model receives a prompt such as:

Subword Methods

Subword methods split text into units smaller than words but usually larger than single characters.

Stochastic Depth

Stochastic depth is a regularization method for deep residual networks.

Sequence Modeling Applications

Recurrent neural networks were among the first deep learning architectures capable of handling variable-length sequential data.

Saturation and Gradient Flow

Activation functions control both the forward signal and the backward signal.

Residual Networks

Residual networks are convolutional networks built from blocks with skip connections.

Residual Connections

Residual connections allow a layer or block to add its input directly to its output. Instead of forcing a block to learn a complete transformation from scratch, the block learns a correction to the input.

Representation Learning

Representation learning is the study of how a model converts raw data into useful internal variables.

Representation Learning

Representation learning is the study of how models learn useful internal descriptions of data.

Question Answering

Question answering, often abbreviated QA, is the task of producing an answer to a question.

PyTorch Versus Other Frameworks

PyTorch is one of several major frameworks for deep learning.

Probabilistic Circuits

Probabilistic circuits are tractable probabilistic models built from simple computational graphs.

Practical Probabilistic Modeling in PyTorch

Probabilistic deep learning adds distributions to ordinary neural networks.

Neural Architecture Search

Neural architecture search, or NAS, is the process of automatically searching for model architectures.

Multi-Task Objectives

Multi-task learning trains one model on several objectives at the same time.

Multi-Node Training

Multi-node training uses more than one machine for a single training job. Each machine contributes one or more accelerators, and all machines cooperate to train the same model.

Multi-Head Attention

Multi-head attention runs several attention operations in parallel. Each head has its own query, key, and value projections. The outputs of the heads are concatenated and projected back to the model dimension.

Momentum and Adaptive Methods

Stochastic gradient descent uses the current minibatch gradient to update the parameters.

Model Editing

Model editing modifies a trained model so that it changes a specific behavior while preserving most other behaviors.

Matrix Operations

Matrix operations are the main arithmetic language of deep learning.

Limits of Linear Decision Boundaries

A linear classifier separates classes using a hyperplane. In two dimensions this boundary is a line. In three dimensions it is a plane. In higher dimensions it is a hyperplane.

In-Context Learning

Large language models can often perform new tasks without updating their parameters.

Efficient Transformers

Standard transformer attention scales quadratically with sequence length. For a sequence of length $T$, self-attention constructs a score matrix of size

Dialogue Systems

A dialogue system is a model or collection of models that interacts with users through natural language.

Conclusion

Deep learning systems have progressed from small task-specific models to large multimodal foundation systems capable of perception, language understanding, reasoning, planning, generation, and interaction.

Calibration and Confidence

A classifier returns scores. Users often interpret those scores as confidence. This interpretation is safe only when the scores are calibrated. A calibrated model assigns probabilities that match empirical correctness.

Bias and Variance

Bias and variance describe two different sources of prediction error. They are useful because they separate errors caused by an overly simple model from errors caused by an overly sensitive model.

Backpropagation

Backpropagation is the algorithm used to compute gradients in neural networks efficiently.

Transformer Encoders

A transformer encoder is a stack of layers that maps an input sequence to a contextual sequence representation.

Training, Validation, and Test Sets

A machine learning dataset is usually divided into three parts: a training set, a validation set, and a test set.

Tokenization Systems

A language model does not read raw text directly. It reads tokens. Tokenization is the process that maps a string of text into a sequence of discrete symbols, and later maps generated symbols back into text.

Stochastic Gradient Descent

Stochastic gradient descent, usually abbreviated as SGD, is the standard form of gradient-based training used in deep learning.

Speech Recognition Systems

Speech recognition maps an acoustic signal to a text sequence. The input is continuous audio. The output is discrete symbols: characters, subword tokens, words, or phonemes.

Softmax and Output Activations

Many neural networks produce raw scores. These scores are called logits.

Scaling Transformers

Scaling a transformer means increasing its capacity, data exposure, context length, training compute, or serving throughput.

Population-Based Training

Population-based training, or PBT, is a hyperparameter optimization method that trains many models at the same time.

Open Research Problems

Deep learning has made large empirical gains, but many scientific and engineering questions remain open.

Mechanistic Interpretability

Mechanistic interpretability studies neural networks by treating them as learned computational systems.

Machine Translation

Machine translation converts text from one language into another. Given a source sentence in one language, the model generates a semantically equivalent sentence in a target language.

Long-Horizon Agents

A long-horizon agent is a model-driven system that pursues goals over many steps. It observes the environment, chooses actions, records intermediate state, uses tools, and adjusts its plan as new information arrives.

Linear Separability

Linear separability describes when a classification dataset can be divided perfectly by a linear decision boundary. It is one of the central geometric ideas behind linear classification.

Latent Space Manipulation

A latent space is the internal coordinate system learned by an encoder or generative model.

Latent Space Manipulation

Latent space manipulation studies how to change a learned representation $z$ in order to produce controlled changes in the decoded output. In an autoencoder, the encoder maps an input into a latent vector,

Latent Diffusion

Early diffusion models operated directly in pixel space. A model generated images by iteratively denoising tensors such as

Large-Scale Training

Large-scale training means training models on datasets, model sizes, or hardware configurations that exceed a simple single-GPU workflow.

Label Smoothing

Label smoothing is a regularization method for classification.

Jacobians and Hessians

Gradients are enough for most neural network training. A gradient tells us how a scalar loss changes with respect to parameters.

Information Retrieval

Information retrieval is the task of finding relevant items from a collection in response to a query.

Indexing, Slicing, and Tensor Views

Indexing and slicing select parts of a tensor. These operations are used constantly in PyTorch: selecting batches, cropping images, extracting token positions, applying masks, gathering logits, and rearranging model

Group and Instance Normalization

Batch normalization and layer normalization are the two most common normalization layers, but they do not cover every setting well.

GPUs and Accelerators

Deep learning became practical at scale because neural network computation maps well to parallel hardware.

Gaussian Processes

A Gaussian process is a probabilistic model over functions. Instead of defining a probability distribution over parameters, as in Bayesian neural networks, a Gaussian process defines a probability distribution directly

Flow-Based Models

Flow-based models are generative models that learn an invertible transformation between a simple probability distribution and a complex data distribution. Unlike many other generative models, flow-based systems provide:

Fault Tolerance

Distributed training systems fail regularly. GPUs crash, network connections reset, processes hang, disks fill, filesystems become unavailable, and nodes disappear from the cluster.

Cross-Attention

Cross-attention is attention between two different sequences or sources of information. The queries come from one sequence, while the keys and values come from another.

Contrastive Objectives

Contrastive objectives train a model by comparing examples. Instead of learning only from an input and its target, the model learns which examples should be close together and which examples should be far apart.

Constitutional Alignment

Reinforcement learning from human feedback improves model behavior using preference data. However, collecting large amounts of human feedback is expensive, slow, and difficult to scale consistently.

CNN Architectures

A convolutional neural network architecture defines how convolutional layers, activation functions, normalization layers, pooling layers, residual paths, and classifier heads are arranged.

Bidirectional Networks

Standard recurrent neural networks process sequences in one direction, usually from left to right. At time step $t$, the hidden state summarizes only the past:

Variational Autoencoders

A variational autoencoder, or VAE, is an autoencoder with a probabilistic latent space.

Variational Autoencoders

A variational autoencoder, or VAE, is a generative latent variable model trained with neural networks.

Vanishing Gradients in RNNs

Recurrent neural networks were designed to process sequential data by maintaining a hidden state over time.

Uncertainty Estimation

Uncertainty estimation measures how much confidence a model should place in its own predictions.

The Perceptron Algorithm

The perceptron is one of the earliest algorithms for binary classification. It learns a linear decision boundary by updating its weights whenever it makes a mistake.

The Chain Rule

The chain rule is the mathematical rule that makes backpropagation possible. Neural networks are built by composing many functions. The chain rule tells us how to differentiate such compositions.

Tensor-Based Computation

PyTorch programs are tensor programs. A tensor stores numbers in a structured array, and most model computation is expressed as operations over tensors.

Tensor Arithmetic and Broadcasting

Tensor arithmetic is the basic computation layer of PyTorch.

Summarization

Summarization is the task of producing a shorter version of one or more source texts while preserving the important information.

Self-Attention

Self-attention is attention applied within a single sequence.

Robotics and Embodied AI

Robotics and embodied AI study learning systems that act in the physical world.

Retrieval Systems

A retrieval system finds relevant information from an external memory source.

Residual and Normalization Layers

Transformer layers are deep stacks of attention and feedforward blocks.

Reinforcement Learning Overview

Reinforcement learning studies how an agent learns to act through interaction with an environment.

Reinforcement Learning from Human Feedback

Instruction tuning teaches a model to imitate demonstrations.

Positional Encoding

Self-attention compares tokens by content. By itself, it has no built-in notion of token order.

Pipeline Parallelism

Pipeline parallelism splits a model into sequential stages and places each stage on a different device. It is a form of model parallelism designed to reduce idle time.

Padding and Stride

Padding and stride control the spatial size of convolutional feature maps.

Noise Schedules

A diffusion model needs a rule for how noise increases during the forward process.

Neural Machine Translation

Neural machine translation maps a sentence in one language to a sentence in another language using a neural sequence model. The model receives a source sentence and generates a target sentence.

Named Entity Recognition

Named entity recognition, usually abbreviated NER, identifies spans of text that refer to named or typed entities.

Masked Language Modeling

Masked language modeling trains a model to recover missing tokens from their surrounding context.

Margin-Based Losses

Margin-based losses are used when the goal is not only to make the correct prediction, but to make it by a sufficient margin.

Layer Normalization

Layer normalization is a normalization method that normalizes features within each individual example.

Gradient Descent

Gradient descent is the basic optimization method used to train neural networks. It updates model parameters in the direction that reduces the loss.

Energy-Based Models

Energy-based models, or EBMs, define probability distributions using energy functions rather than normalized output probabilities directly.

ELU, GELU, and Swish

ReLU and its variants improved optimization in deep networks, but they still have limitations.

Data Augmentation Strategies

Data augmentation creates modified versions of training examples without changing their labels.

Data Augmentation

Data augmentation is a regularization method that creates modified versions of training examples while preserving their labels.

Bayesian Optimization

Bayesian optimization is a hyperparameter optimization method for expensive black-box functions. It is useful when each training run costs enough that random search wastes too much compute.

Attribution Methods

Attribution methods assign credit or blame to parts of an input, hidden representation, neuron, feature, or training example for a model output.

Unified Foundation Models

A unified foundation model is a neural network trained across many modalities, tasks, and domains using a shared architecture and shared representations.

Text Classification

Text classification assigns one or more labels to a piece of text.

Tensor Creation and Initialization

Neural networks start with tensors. Some tensors come from data.

Softmax Regression

Softmax regression extends logistic regression from two classes to many classes. It is the standard linear model for multiclass classification.

Self-Supervised Learning

Self-supervised learning is a form of learning where the training signal is created from the data itself. The dataset does not need human-written labels, but the model still receives a prediction task.

Score Matching

Diffusion models can be understood from multiple mathematical viewpoints.

Scientific Deep Learning

Scientific deep learning applies neural networks and differentiable computation to scientific and engineering problems.

Saliency Maps

A saliency map is a visualization that assigns an importance score to each part of an input.

Reverse-Mode Differentiation

Reverse-mode differentiation is the method used by backpropagation. It computes derivatives by first evaluating a function forward, then propagating gradient information backward from the output to the inputs.

Random Search

Random search is a hyperparameter optimization method that samples configurations at random from a search space.

Question Answering

Question answering is the task of producing an answer to a question. The input may contain only the question, or it may contain both a question and one or more passages that may contain the answer.

Positional Encoding

Self-attention compares tokens to other tokens, but by itself it has no built-in notion of order.

Multi-Head Attention

Multi-head attention runs several attention operations in parallel.

Monte Carlo Methods

Monte Carlo methods approximate difficult mathematical quantities using random samples.

Model Parallelism

Model parallelism splits a model across multiple devices. Instead of copying the whole model onto every GPU, different parts of the model live on different GPUs.

Loss Functions

A loss function measures how wrong a model’s predictions are.

Likelihood-Based Objectives

Many deep learning loss functions can be understood as likelihood maximization.

Leaky and Parametric ReLU

ReLU is simple and effective, but it has one sharp weakness.

Instruction Tuning

Pretraining teaches a language model to predict text. It does not directly teach the model to follow user instructions, answer safely, maintain dialogue structure, or format outputs in a useful way.

Fine-Tuning Pretrained Models

Fine-tuning adapts a pretrained model to a target dataset by continuing training from learned weights instead of starting from random initialization.

Feature Maps

A feature map is the spatial output produced by a convolutional filter. In a convolutional neural network, each output channel can be read as a map of where a learned feature appears in the input.

Dynamic Computation Graphs

Deep learning models are built from sequences of mathematical operations.

Dropout

Dropout is a regularization method that randomly removes parts of a neural network during training.

Dot-Product Attention

Dot-product attention uses an inner product to measure how well a query matches a key.

Denoising Autoencoders

A denoising autoencoder learns to reconstruct a clean input from a corrupted version of that input. Instead of copying $x$ to $\hat{x}$, the model receives a noisy input $\tilde{x}$ and must recover the original $x$.

Denoising Autoencoders

A denoising autoencoder learns to recover a clean input from a corrupted version of that input.

Deep Belief Networks

A deep belief network, or DBN, is a probabilistic generative model formed by stacking multiple layers of latent variables.

Beam Search

Beam search is a decoding algorithm for autoregressive sequence models. It is used when a model must generate a sequence, but greedy decoding is too narrow.

Batch Normalization

Batch normalization is a layer that normalizes activations using statistics computed from a mini-batch.

Backpropagation Through Time

Recurrent networks reuse the same parameters at every time step.

Autoregressive Modeling

Autoregressive modeling is the dominant formulation for modern language generation. The model predicts the next token from previous tokens. Repeating this prediction step produces a sequence.

Variational Inference

Bayesian neural networks require inference over a posterior distribution:

Vanishing and Exploding Gradients

Deep networks train by sending information in two directions.

Unsupervised Learning

Unsupervised learning studies data without explicit target labels. The dataset contains inputs only:

Transformer Decoders

A transformer decoder is a neural network block that maps a prefix sequence to a sequence of next-token representations. It is used when the model must generate output one step at a time.

Transfer Learning

Transfer learning reuses a model trained on one task as the starting point for another task.

The PyTorch Ecosystem

PyTorch is a deep learning platform built around tensors, automatic differentiation, and composable neural network modules.

Tensor Shapes, Dimensions, and Memory Layout

Deep learning systems manipulate tensors with millions or billions of numerical entries.

Teacher Forcing

Teacher forcing is a training method for autoregressive sequence models. It is used when a model generates an output sequence one token at a time, but during training we already know the correct output sequence.

Subword Tokenization

A language model cannot process raw text directly. Text must first be converted into a sequence of token IDs. The procedure that performs this conversion is called tokenization.

Sparse Autoencoders

An undercomplete autoencoder constrains the representation by reducing the latent dimension.

Sparse Autoencoders

An ordinary autoencoder compresses information by forcing the latent representation to have fewer dimensions than the input.

Self-Attention

Self-attention is attention applied within a single sequence. The same input supplies the queries, keys, and values. Each position builds a new representation by reading from other positions in the same sequence.

Scaling Laws for Language Models

Scaling laws describe how model performance changes as we increase compute, parameter count, dataset size, and training tokens.

Reverse Denoising Processes

The forward diffusion process gradually transforms data into noise.

Restricted Boltzmann Machines

A restricted Boltzmann machine, or RBM, is a simplified Boltzmann machine with a bipartite structure.

Recurrent Computation

A feedforward neural network processes inputs through a fixed sequence of layers. Once the output is produced, the computation ends. There is no memory of previous inputs.

Rectified Linear Units

The rectified linear unit, usually called ReLU, is the most widely used activation function in modern deep learning.

Pooling Layers

Pooling is a downsampling operation used in convolutional neural networks.

Neural Language Models

Statistical language models estimate probabilities from discrete counts.

Named Entity Recognition

Named entity recognition, or NER, is the task of finding spans of text that refer to entities and assigning each span a type.

Logistic Regression

Logistic regression is a linear model for classification. It predicts a probability instead of a raw numerical value. Despite its name, logistic regression is mainly used for classification, not regression.

Logistic Regression

Linear regression predicts a real number. Logistic regression predicts a probability for binary classification.

Grid Search

Grid search is one of the simplest methods for hyperparameter optimization.

Gradient Computation

Gradient computation is the process of measuring how a scalar output changes when its input values change. In deep learning, the scalar output is usually the loss, and the inputs are usually the model parameters.

Efficient AI Systems

Modern deep learning systems are constrained by compute, memory, bandwidth, latency, and energy. As models become larger, efficiency becomes a central engineering problem rather than a secondary optimization.

Early Stopping

Neural networks are usually trained iteratively. An optimizer repeatedly updates model parameters to reduce the training loss.

Distribution Shift

A distribution shift occurs when the data seen at deployment differs from the data used during training.

Distributed Data Parallel

Distributed Data Parallel, usually abbreviated as DDP, is PyTorch’s primary system for synchronous multi-GPU training.

Cross-Entropy Loss

Cross-entropy loss is the standard loss function for classification. It measures how well a model’s predicted class distribution matches the true class label.

Audio-Visual Learning

Audio-visual learning studies models that jointly process sound and visual information. The goal is to learn representations that combine what is seen with what is heard.

Additive Attention

Additive attention was one of the first successful neural attention mechanisms. It was introduced for neural machine translation to allow a decoder to selectively focus on different encoder states during generation.

Word Embeddings

Natural language models cannot operate directly on words as strings.

What Is Deep Learning

Deep learning is a branch of machine learning that studies models built from many layers of learned computation.

Vision-Language Models

A vision-language model learns a joint representation of images and text.

Transformer Encoders

A transformer encoder is a neural network block that maps a sequence of input vectors to a sequence of contextualized output vectors.

Text Classification

Text classification is the task of assigning one or more labels to a piece of text.

Supervised Learning

Supervised learning is the central paradigm of modern machine learning and deep learning.

Statistical Language Models

A language model assigns probabilities to sequences of tokens. The tokens may be words, subwords, characters, bytes, or other discrete symbols. In the classical setting, a sentence is represented as a finite sequence

Sigmoid and Hyperbolic Tangent

Activation functions give neural networks their nonlinear structure.

Sequential Data

Many learning problems involve data whose meaning depends on order.

Search Spaces

Hyperparameter optimization begins by deciding what may vary.

Scaling Laws

Modern deep learning systems often improve when we increase three quantities: model size, dataset size, and compute. This empirical regularity is called a scaling law.

Scalars, Vectors, Matrices, and Tensors

Deep learning represents data and computation using arrays of numbers.

Pretraining Objectives

A large language model is trained in two broad phases. The first phase is pretraining.

Parameter Initialization

A neural network begins training with parameters that have not yet been learned from data.

Motivation for Attention

Sequence models often need to decide which parts of an input are relevant to a particular output.

Mean Squared Error

Mean squared error is one of the simplest and most widely used loss functions in supervised learning. It measures the average squared difference between a model’s prediction and the target value.

Linear Regression

Linear regression is the simplest supervised learning model used in deep learning.

L1 and L2 Regularization

A neural network is trained by minimizing a loss function. For a supervised learning problem, this loss measures how far the model predictions are from the target values.

Forward Diffusion Processes

Diffusion models are generative models built around a simple idea: learn to reverse a gradual corruption process.

Encoder-Decoder Architectures

A sequence-to-sequence model maps one sequence to another sequence.

Dimensionality Reduction

High-dimensional data often contains structure that can be described with fewer variables than the raw representation suggests.

Dimensionality Reduction

Deep learning often begins with data that has many coordinates.

Datasets and DataLoaders

A deep learning model does not train directly from files. It trains from tensors. The purpose of a data pipeline is to convert stored data into batches of tensors with consistent shapes, data types, and labels.

Data Parallelism

Data parallelism is the simplest and most widely used form of distributed deep learning.

Convolution Operations

Convolution is the central operation in convolutional neural networks.

Computational Graphs

A computational graph is a graph that represents a numerical computation. The nodes represent values or operations. The edges describe how data flows from one operation to the next.

Classification Pipelines

Image classification assigns one label, or a small set of labels, to an image.

Boltzmann Machines

A Boltzmann machine is a probabilistic neural network that defines a probability distribution over binary variables.

Bayesian Neural Networks

A Bayesian neural network is a neural network whose parameters are treated as random variables rather than fixed unknown constants.

Attention Mechanisms

Attention is a method for letting a model choose which parts of an input are most relevant when producing an output.

Adversarial Examples

An adversarial example is an input that has been deliberately modified so that a model makes a wrong prediction, while the modification is small enough that a human observer still sees the original object.

Chapter 81. Spectral Theorems

Chapter 80. Eigenvalues and Eigenvectors

Chapter 79. Spectrum of a Graph

Chapter 78. Laplacian Matrices

Chapter 77. Incidence Matrices

Chapter 76. Adjacency Matrices

Chapter 75. Fractional Coloring

Chapter 74. List Coloring

Chapter 73. Ramsey Theory

Chapter 72. Perfect Graphs

Chapter 71. Brooks' Theorem

Chapter 70. Greedy Coloring

Chapter 69. Chromatic Polynomial

Chapter 68. Chromatic Number

Chapter 67. Edge Coloring

Chapter 66. Vertex Coloring

Chapter 65. Dominating Sets

Chapter 64. Cliques

Chapter 63. Independent Sets

Chapter 62. Edge Covers

Chapter 61. Vertex Covers

Chapter 60. Maximum Matching Algorithms

Chapter 59. Bipartite Matching

Chapter 58. Hall's Marriage Theorem

Chapter 57. Perfect Matchings

Chapter 56. Matchings

Chapter 55. Random Walks on Graphs

Chapter 54. Sparse and Dense Graphs

Chapter 53. Graph Separators

Chapter 52. Expansion and Expanders

Chapter 51. Network Reliability

Chapter 50. Menger's Theorem

Chapter 49. Bridges and Articulation Points

Chapter 48. Cuts and Cut Sets

Chapter 47. Edge Connectivity

Chapter 46. Vertex Connectivity

Chapter 45. Computational Geometry Connections

Chapter 44. Intersection Graphs

Chapter 43. Geometric Graphs

Chapter 42. Dual Graphs

Chapter 41. Graph Coloring of Planar Graphs

Chapter 40. Kuratowski's Theorem

Chapter 39. Faces and Regions

Chapter 38. Euler's Formula

Chapter 37. Plane Embeddings

Chapter 36. Planar Graphs

Chapter 35. Applications of Trees

Chapter 34. Tree Decomposition

Chapter 33. Tree Traversal

Chapter 32. Prufer Sequences

Chapter 31. Minimum Spanning Trees

Chapter 30. Spanning Trees

Chapter 29. Binary Trees

Chapter 28. Rooted Trees

Chapter 27. Forests

Chapter 26. Trees

Chapter 25. Signed and Labeled Graphs

Chapter 24. Hypergraphs

Chapter 23. Multigraphs

Chapter 22. Weighted Graphs

Chapter 21. Topological Ordering

Chapter 20. Directed Acyclic Graphs

Chapter 19. Strong Connectivity

Chapter 18. Directed Paths and Cycles

Chapter 17. In-Degree and Out-Degree

Chapter 16. Directed Graphs

Chapter 15. Graph Isomorphism

Chapter 14. Graph Invariants

Chapter 13. Complement Graphs

Chapter 12. Graph Operations

Chapter 11. Subgraphs

Chapter 10. Trees

Chapter 9. Components

Chapter 8. Connected Graphs

Chapter 7. Cycles and Circuits

Chapter 6. Walks, Trails, and Paths

Chapter 5. Degree of a Vertex

Chapter 4. Graph Representations

Chapter 3. Vertices and Edges

Chapter 2. Basic Definitions

Chapter 1. What Graph Theory Is

Appendix K. Symbol Index

Appendix J. Common Identities and Formulas

Appendix I. Glossary

Appendix H. Historical Notes

Appendix G. Mathematical Notation

Appendix F. Numerical Computation

Appendix E. Calculus Review

Appendix D. Polynomial Algebra

Appendix C. Real and Complex Numbers

Appendix B. Proof Techniques

Appendix A. Set Theory and Logic

Chapter 140. Modern Applications in AI

Chapter 139. Matrix Calculus

Chapter 138. Tensor Decompositions

Chapter 137. Compressed Sensing

Chapter 136. Spectral Graph Theory

Chapter 135. Operator Theory

Chapter 134. Numerical Optimization

Chapter 133. Random Matrices

Chapter 132. Convex Geometry

Chapter 131. Category-Theoretic Perspective

Chapter 130. Modules and Linear Algebra

Chapter 129. Linear Algebra over Arbitrary Fields

Chapter 128. Finite Fields

Chapter 127. Complex Vector Spaces

Chapter 126. Numerical Linear Algebra

Chapter 125. Finite Element Methods

Chapter 124. Cryptography

Chapter 123. Coding Theory

Chapter 122. PageRank and Network Analysis

Chapter 121. Principal Component Analysis

Chapter 120. Machine Learning

Chapter 119. Quantum Mechanics

Chapter 118. Control Theory

Chapter 117. Robotics and Kinematics

Chapter 116. Computer Graphics

Chapter 115. Signal Processing

Chapter 114. Fourier Series and Transforms

Chapter 113. Differential Equations

Chapter 112. Markov Chains

Chapter 111. Graphs and Adjacency Matrices

Chapter 110. Optimization and Linear Algebra

Chapter 109. Linear Regression

Chapter 108. Functional Analysis Connections

Chapter 107. Infinite-Dimensional Vector Spaces

Chapter 106. Representation Theory Basics

Chapter 105. Lie Algebras

Chapter 104. Clifford Algebras

Chapter 103. Alternating Forms

Chapter 102. Bilinear Forms

Chapter 101. Multilinear Maps

Chapter 100. Symmetric Algebra

Chapter 99. Exterior Algebra

Chapter 98. Tensor Products

Chapter 97. Randomized Linear Algebra

Chapter 96. Structured Matrices

Chapter 95. Sparse Matrices

Chapter 94. QR Algorithm

Chapter 93. Power Iteration

Chapter 92. Krylov Subspaces

Chapter 91. Conjugate Gradient Method

Chapter 90. Gauss-Seidel Method

Chapter 89. Jacobi Method

Chapter 88. Iterative Methods for Linear Systems

Chapter 87. Error Analysis

Chapter 86. Conditioning and Stability

Chapter 85. Floating Point Arithmetic

Chapter 84. Bidiagonal Form

Chapter 83. Tridiagonal Form

Chapter 82. Hessenberg Form

Chapter 81. Polar Decomposition

Chapter 80. Singular Value Decomposition

Chapter 79. Schur Decomposition

Chapter 78. QR Decomposition

Chapter 77. Cholesky Decomposition

Chapter 76. PLU Decomposition

Chapter 75. LU Decomposition

Chapter 74. Perron-Frobenius Theory

Chapter 73. Matrix Exponential

Chapter 72. Matrix Functions

Chapter 71. Rational Canonical Form

Chapter 70. Cayley-Hamilton Theorem

Chapter 69. Minimal Polynomial

Chapter 68. Jordan Canonical Form

Chapter 67. Normal Operators

Chapter 66. Hermitian Operators

Chapter 65. Symmetric Matrices

Chapter 64. Spectral Theorem

Chapter 63. Diagonalization

Chapter 62. Eigenspaces

Chapter 61. Characteristic Polynomial

Chapter 60. Eigenvectors

Chapter 59. Eigenvalues

Chapter 58. Sylvester's Law of Inertia

Chapter 57. Singular Value Decomposition

Chapter 56. Hermitian and Normal Matrices

Chapter 55. Hermitian Spaces

Chapter 54. Unitary and Orthogonal Matrices

Chapter 53. QR Factorization

Chapter 52. Least Squares Problems

Chapter 51. Orthogonal Projections

Chapter 50. Gram-Schmidt Orthogonalization

Chapter 49. Orthonormal Bases

Chapter 47. Orthogonality

Chapter 48. Orthogonal Complements

Chapter 46. Norms and Metrics

Chapter 45. Inner Products

Chapter 44. Quotient Spaces and Quotient Operators

Chapter 43. Invariant Subspaces

Chapter 42. Similarity Transformations

Chapter 41. Shears and Scalings

Chapter 40. Rotation Operators

Chapter 39. Reflection Operators

Chapter 38. Projection Operators

Chapter 37. Automorphisms

Chapter 36. Isomorphisms

Chapter 35. Composition of Transformations

Chapter 34. Matrix Representation of Linear Maps

Chapter 33. Kernel and Image

Chapter 32. Linear Transformations

Chapter 31. Affine Spaces

Chapter 30. Inner Products

Chapter 29. Annihilators

Chapter 28. Dual Spaces

Chapter 27. Quotient Spaces

Chapter 26. Null Space

Chapter 25. Row Space and Column Space

Chapter 24. Change of Basis

Chapter 23. Coordinate Systems

Chapter 22. Dimension

Chapter 21. Basis

Chapter 20. Linear Independence

Chapter 19. Span and Linear Combination

Chapter 18. Subspaces

Chapter 17. Vector Spaces

10.5 Equivalence of Models

Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.

10.2 Partial vs Total Functions

Distinction between partial and total computable functions, undefined values, domains of definition, and the role of nontermination.

10.1 Recursive Functions

Primitive recursive functions, general recursive functions, minimization, and the formal construction of computable numerical functions.

9.2 Large Cardinals

An introduction to large cardinal axioms, inaccessible cardinals, measurable cardinals, elementary embeddings, and consistency strength.

9.1 Forcing

An introduction to forcing, generic filters, forcing names, the forcing relation, and the basic extension theorem.

8.3 Constructible Universe (L)

The constructible universe, definable subsets, the hierarchy L_alpha, and the axiom of constructibility.

8.2 Equivalent Formulations

Equivalent forms of the axiom of choice, including Zorn's lemma, the well ordering theorem, maximal principles, and right inverses of surjections.

8.1 Axiom of Choice

The axiom of choice, choice functions, indexed families, and first consequences in axiomatic set theory.

7.4 Arithmetic of Cardinals

Cardinal addition, multiplication, exponentiation, finite and infinite cardinal arithmetic, and basic comparison laws.

7.1 Sets, Relations, Functions

Basic set theoretic language, including sets, membership, subsets, operations, relations, equivalence relations, order relations, and functions.

6.2 Types and Realizations

Definition of complete and partial types, realization of types in structures, examples, consistency, and basic properties.

4.4 Isomorphism and Invariants

Isomorphisms of first order structures, structural invariants, and properties preserved by isomorphism.

4.2 Substructures and Embeddings

Substructures, generated substructures, homomorphisms, embeddings, and preservation of atomic formulas.

Chapter 16. Matrix Factorizations Overview

Chapter 15. Block Matrices

Chapter 14. Cofactors and Adjugates

Chapter 13. Determinants

Chapter 12. Rank and Nullity

Chapter 11. Invertible Matrices

Chapter 10. Gauss-Jordan Elimination

Chapter 9. Gaussian Elimination

Chapter 8. Elementary Row Operations

Chapter 7. Matrix Operations

Chapter 6. Matrices

Chapter 4. Linear Equations

Chapter 3. Geometry of Euclidean Space

Chapter 2. Scalars, Vectors, and Fields

Chapter 1. What Linear Algebra Is

Chapter 5. Systems of Linear Equations

Static Array

Store a fixed number of elements in contiguous memory with constant-time indexing.

14.3 Second Incompleteness Theorem

Proof that no sufficiently strong consistent system can prove its own consistency.

14.1 Arithmetization of Syntax

Encoding symbols, formulas, and proofs as natural numbers to allow arithmetic to reason about its own syntax.

Galloping Intersection Search

Find intersection of two sorted sequences using exponential jumps followed by binary search.

Interpolation Search with Fallback

Use interpolation to estimate the target position, with binary search fallback when estimates become unreliable.

SIMD Linear Search

Search several array elements at once using vector instructions.

Cache Aware Binary Search

Arrange and search sorted data with explicit knowledge of cache lines or memory blocks.

Van Emde Boas Layout Search

Search a binary tree stored in recursive cache oblivious layout to reduce memory transfers.

Eytzinger Layout Search

Binary search over an array arranged in heap order to improve cache locality and branch predictability.

Branchless Binary Search

Perform binary search with conditional moves or arithmetic updates instead of unpredictable branches.

Recursive Model Index Search

Use a hierarchy of learned models to predict a key position, then search inside a bounded error range.

Suffix Array Radix Sort

Construct a suffix array by sorting rank pairs with radix or counting sort during the doubling method.

Burstsort String Sorting

String sorting method that groups strings by prefixes in a trie and sorts leaf buckets for cache efficient lexicographic order.

Burstsort

Cache efficient string sorting algorithm that builds a trie and sorts buckets lazily for high performance on large text data.

LSD Radix Sort

Sort fixed width keys by processing digits from least significant to most significant using a stable inner sort.

Radix Sort

Sort integer or string keys by processing one digit, byte, or character position at a time.

Kth Smallest Subarray Sum

Find the k-th smallest sum among all contiguous subarrays, usually for nonnegative arrays.

Kth Smallest Pair Distance

Find the k-th smallest absolute difference among all pairs in an array.

Selection in Sorted Matrix

Select the k-th smallest element from a matrix whose rows and columns are sorted.

100. Future Directions

Active PEPs, the free-threaded and JIT roadmaps, memory model work, and how to follow CPython development.

Parallel Binary Search with DSU

Answer offline connectivity queries by combining parallel binary search with a disjoint set union.

Parametric Search

Convert an optimization problem into a decision problem and search the parameter space.

Array Alignment

Place array elements at memory addresses that satisfy hardware and type alignment requirements.

32. Method Calls

LOAD_METHOD and CALL_METHOD optimization, bound method objects, and the method cache.

Array Bounds Checking

Validate array indices before access to prevent invalid reads and writes.

27. Evaluation Loop

The main evaluation loop in Python/ceval.c, opcode dispatch via computed gotos, and the eval breaker mechanism.

Array Union

Combine elements from two arrays into one collection without duplicates.

Array Intersection

Compute the common elements between two arrays.

Difference Array

Represent range updates compactly by storing changes between adjacent values.

Prefix Sum Array

Precompute cumulative sums to answer range sum queries in constant time.

gopy gc, weakrefs, finalizers

v0.10 cycle GC port. Maps Python/gc.c, Python/gc_gil.c, Python/object_stack.c, Objects/weakrefobject.c onto gopy/gc and objects/weakref. Defines what '100% behavioural compatibility' means when the host runtime is Go (which already collects cycles).

99. Security Boundaries

CPython security model: what is and is not sandboxed, restricted execution limits, and audit hook coverage.

98. Serialization Internals

pickle protocol versions, the __reduce__ / __reduce_ex__ protocol, marshal format, and shelve internals.

97. Import System Edge Cases

Circular import resolution, namespace package search order, zip imports, and __import__ hook edge cases.

96. Stable ABI Design Tradeoffs

What breaking the stable ABI costs, historical breakages, versioning policy, and the tradeoff against new features.

95. JIT Work in CPython

CPython 3.13 copy-and-patch JIT: template JIT design, trace selection, and the roadmap toward full JIT compilation.

94. Per-Interpreter GIL

PEP 684 per-interpreter GIL: isolated interpreter state, shared-nothing model, and module isolation requirements.

93. Immortal Objects

PEP 683 immortal objects: _Py_IMMORTAL_REFCNT sentinel, zero-cost incref/decref, and implications for forks.

92. Free-Threaded CPython

PEP 703 no-GIL build: per-object locking, biased reference counting, and the free-threaded evaluation loop.

91. Release Process

CPython version numbering, alpha/beta/RC schedule, branch management, and the role of the release manager.

90. Reading PEPs

PEP document structure, the steering council review process, and tracking PEP status on peps.python.org.

89. Making a CPython Patch

GitHub workflow: forking, branching, opening a PR, responding to review, and the CLA requirement.

88. Documentation Workflow

Doc/ Sphinx source layout, building docs with make html, and the process for submitting documentation fixes.

87. Writing Core Tests

test_* module conventions, unittest patterns, support helpers in Lib/test/support/, and writing C-level tests.

86. Tracing Memory Bugs

Valgrind suppression files, tracemalloc snapshot diffing, and libasan leak detection in CPython builds.

85. Sanitizers

Building CPython with AddressSanitizer, UBSan, and ThreadSanitizer to catch memory and concurrency bugs.

84. GDB and LLDB

CPython-aware GDB and LLDB scripts in Tools/gdb/, py-bt, py-list, and inspecting live interpreter frames.

83. Debug Builds

Py_DEBUG compile flag, assertion macros, the --with-pydebug configure option, and debugging allocator.

82. Running the Test Suite

python -m test flags, regrtest test selection, parallel execution (-j), and interpreting test output.

81. Benchmarking CPython

pyperformance benchmark suite, microbenchmark pitfalls, timer resolution, and interpreter warm-up effects.

80. Profiling CPython

Using perf, Instruments, and py-spy to profile CPython; reading perf maps generated by the JIT.

79. Memory Locality

Object allocation locality, arena page placement, freelists for common types, and cache-line–aware design.

78. Attribute Access Performance

Type version tags, LOAD_ATTR inline cache hits, and the attribute specialization guards for slots and descriptors.

77. Dictionary Performance

Compact dict memory layout, hash collision probing strategy, split-table sharing, and lookup specialization.

76. Vectorcall

PEP 590 vectorcall protocol, _Py_TPFLAGS_HAVE_VECTORCALL, and stack-based argument passing for zero-overhead calls.

75. Function Call Fast Paths

CALL_PY_EXACT_ARGS, CALL_BUILTIN_FAST, and the fast-path conditions that bypass the generic call machinery.

74. Specializing Adaptive Interpreter

Adaptive counter logic, specialization guards, and how CPython 3.11+ rewrites opcodes to LOAD_ATTR_SLOT and friends.

73. Inline Caches

Inline cache entries appended to CACHE instructions in the bytecode array and their layout per opcode family.

72. Interpreter Dispatch

Computed goto dispatch table, the switch fallback, and how opcode prediction reduces branch mispredictions.

71. Calling C From Python

ctypes, cffi, and CFFI-based extension dispatch as the primary paths for calling C libraries from Python.

70. Calling Python From C

PyObject_Call, PyObject_CallNoArgs, argument tuple construction, and error checking after calling into Python.

69. Embedding Python

Py_Initialize, PyConfig, embedding CPython in a host process, and managing interpreter lifetime.

68. Limited API

Py_LIMITED_API version macros, symbols excluded from the limited API, and building abi3-compatible extensions.

67. Stable ABI

The stable ABI symbol set, abi3 wheel tagging, and the constraints imposed by maintaining ABI compatibility.

66. Capsules

PyCapsule_New, PyCapsule_GetPointer, and the pattern for passing opaque C pointers between extension modules.

65. Buffer Protocol

Py_buffer, PyBUF_* flags, PyObject_GetBuffer, and implementing the buffer protocol in a custom type.

64. Defining New Types

PyTypeObject slot-by-slot walkthrough: tp_new, tp_init, tp_dealloc, tp_methods, tp_getset, and inheritance.

63. Creating Extension Modules

PyModuleDef structure, PyModule_Create, multi-phase initialization (PEP 451), and module state.

62. Reference Ownership Rules

Borrowed vs. owned references, Py_XDECREF patterns, and common reference counting mistakes in extensions.

61. The Python C API

Public C API overview, Include/ header organization, and the stable vs. internal API distinction.

60. `asyncio`

asyncio event loop internals, the coroutine runner, I/O selector integration, and Task scheduling.

59. `multiprocessing`

multiprocessing Process creation strategies (fork/spawn/forkserver), shared memory, and the pickle channel.

58. `ctypes`

ctypes CDLL and WinDLL, fundamental types, Structure/Union layout, function prototypes, and libffi integration.

57. `importlib`

importlib.machinery finders and loaders, importlib.util helpers, and the Python-level import bootstrap.

56. `types`

types.FunctionType, types.CodeType, types.SimpleNamespace, and dynamic type creation with types.new_class.

55. `gc`

gc.collect, gc.get_objects, gc.freeze, callbacks, and tuning generational thresholds.

54. `dis`

dis.dis output, Instruction namedtuples, the bytecode iterator API, and reading adaptive specializations.

53. `inspect`

inspect.getmembers, signature objects, frame introspection, and source retrieval via linecache.

52. `sys`

sys module fields that expose interpreter state: sys.modules, sys._getframe, sys.getsizeof, and audit hooks.

51. Audit Hooks

sys.addaudithook, the cpython.PyAudit_AddHook C API, and auditable events across the standard library.

50. Context Variables

PEP 567 Context and ContextVar objects, context copying on task creation, and asyncio integration.

49. Signals

Signal handler registration, the eval breaker flag, and safe SIGINT delivery to Python code.

48. Subinterpreters

Per-interpreter state isolation, Py_NewInterpreterFromConfig, and the experimental per-interpreter GIL.

47. Threads

Python thread objects, OS thread mapping, the GIL acquisition protocol, and thread-local state management.

46. The GIL

GIL purpose, implementation in Python/ceval_gil.c, forced release intervals, and its effect on multi-core performance.

45. The MRO

C3 linearization algorithm, mro() computation, and how Python resolves method lookup across multiple inheritance.

44. Classes and Metaclasses

type.__new__ and type.__init__, __init_subclass__, __set_name__, and metaclass resolution order.

43. Descriptors

__get__, __set__, __delete__ protocol, data vs. non-data descriptors, and property/classmethod/staticmethod internals.

42. The Import Lock

The per-module import lock, re-entrant import detection, and deadlock scenarios in multithreaded code.

41. Packages

Package __init__.py, namespace packages (PEP 420), relative imports, and __path__ manipulation.

40. Modules and Imports

The import machinery: finders, loaders, sys.modules cache, and the importlib bootstrap sequence.

39. Closures and Cells

MAKE_CELL, LOAD_DEREF, STORE_DEREF opcodes and the PyCellObject that captures variables in enclosing scopes.

38. Comprehensions

How list/dict/set comprehensions and generator expressions compile to nested code objects with implicit iteration.

37. Pattern Matching

match/case compilation to MATCH_* opcodes, pattern semantics, and guard evaluation in the interpreter.

36. Coroutines and Async

async def, await, SEND opcode, coroutine wakeup, and how asyncio integrates with CPython's coroutine machinery.

35. Generators

Generator object internals, YIELD_VALUE and RESUME opcodes, and frame suspension and resumption mechanics.

34. Exception Handling

Exception tables, the try/except/finally bytecode pattern, exception chaining, and the unwinding protocol.

33. Attribute Lookup

LOAD_ATTR bytecode, __getattribute__ dispatch, the descriptor protocol, and type version tag caching.

31. Function Calls

CALL opcode mechanics, positional and keyword argument handling, *args/**kwargs unpacking, and call overhead.

30. Bytecode Instructions

Catalogue of CPython opcodes: LOAD/STORE variants, binary ops, comparison, jumps, and call instructions.

29. Stack-Based Execution

The value stack, operand push/pop discipline, and how the interpreter maintains stack depth invariants.

28. Frames

PyFrameObject and _PyInterpreterFrame layout, frame creation, the frame stack, and frame introspection.

26. Bytecode Optimization

Peephole optimizer passes: constant folding, dead code elimination, and superinstruction formation in Python/flowgraph.c.

25. Bytecode Generation

Instruction emission, jump fixup, and the assembler in Python/compile.c that produces the final bytecode array.

24. Constants, Names, and Locals

How compile-time constants are folded, names interned, and local variable slots assigned in the code object.

23. Code Objects

PyCodeObject fields: co_code, co_consts, co_names, co_varnames, co_filename, and how they are used at runtime.

22. Compiler Passes

Multi-pass lowering from AST to CFG to linear bytecode, and the role of each compiler pass in Python/compile.c.

21. Symbol Tables

Scope analysis in Python/symtable.c: local, global, free, and cell variable classification before compilation.

20. The AST

AST node types defined in Parser/Python.asdl, the ast module, and how AST nodes map to source locations.

19. Parsing

CPython's PEG parser, Grammar/python.gram, the generated Parser/parser.c, and parse tree construction.

18. Tokenization

Tokenize module internals, the C tokenizer in Parser/tokenize.c, and how indentation becomes INDENT/DEDENT tokens.

17. Integers, Floats, and Complex Numbers

PyLongObject digit array for arbitrary precision, PyFloatObject IEEE 754 storage, and complex number layout.

16. Dictionaries and Sets

Compact dict implementation, hash table probing, split-key sharing, and PySetObject collision resolution.

15. Lists, Tuples, and Arrays

PyListObject dynamic resizing strategy, PyTupleObject immutability, and the array module's typed buffer.

14. Strings, Bytes, and Unicode

PyUnicodeObject internal encodings, the interning table, bytes vs. bytearray, and the codec infrastructure.

13. Built-in Object Implementations

C-level implementations of None, True, False, NotImplemented, and Ellipsis as statically allocated objects.

12. Object Layout and Type Slots

PyTypeObject slot layout, tp_* function pointers, and how type slots encode object behavior for the interpreter.

11. Memory Allocators

The pymalloc small-object allocator, arenas, pools, blocks, and when CPython falls back to system malloc.

10. The Garbage Collector

Cycle detection algorithm, generational collection, gc thresholds, and the interaction with reference counting.

9. Reference Counting

Py_INCREF, Py_DECREF, and the deterministic lifetime rules that drive most memory reclamation in CPython.

8. PyObject and PyVarObject

The PyObject and PyVarObject C structs: ob_refcnt, ob_type, and the ob_size extension for variable-length objects.

7. The Python Object Model

How every value in Python is a heap-allocated object, and the role of type objects in defining behavior.

6. From Source Code to Execution

End-to-end journey of a .py file through lexing, parsing, compilation, and bytecode evaluation.

5. The Runtime Model

The interpreter state, thread state, frame stack, and the runtime lifecycle from Py_Initialize to Py_Finalize.

4. Reading CPython C Code

Conventions, macros, naming patterns, and header layout used throughout the CPython C codebase.

3. Repository Layout

Tour of the CPython source tree: Modules/, Objects/, Python/, Parser/, Include/, and the build system.

2. Building CPython From Source

Cloning the repository, installing dependencies, running ./configure, and compiling CPython from source.

1. What CPython Is

What CPython is, how it differs from other Python implementations, and why its internals are worth studying.

Array Padding

Insert unused space between array elements or groups to control alignment and reduce interference.

Array Vectorization

Process multiple array elements per instruction using SIMD-friendly layout and loops.

Array Tiling

Process multidimensional arrays in small rectangular regions to improve locality.

Array Blocking

Process an array in fixed-size blocks to improve cache locality and batch behavior.

Array Stride Access

Access array elements at regular intervals and understand the effect on locality.

Array Index Mapping

Map logical array positions to physical storage positions.

Array Buffering

Use temporary array storage to stage data before writing it to its final location.

Array Copying

Copy array elements into a new storage block using shallow or deep copy semantics.

Array Memory Layout

Understand how arrays are stored in memory and how layout affects performance.

Array Merge

Merge two sorted arrays into a single sorted array.

Array Deduplication

Remove duplicate values from an array while keeping one representative of each value.

Array Compaction

Remove elements in-place based on a predicate while preserving the remaining elements.

Array Scan

Traverse an array sequentially to compute an aggregate or apply a function.

Array Shuffle

Generate a uniform random permutation of an array in-place.

Array Reversal

Reverse the order of elements in an array in-place using symmetric swaps.

Stable Partition

Partition an array while preserving the relative order of elements inside each group.

Array Partition

Rearrange elements so that those satisfying a predicate appear before others.

Amortized Analysis

Analyze the average cost per operation over a sequence of dynamic array operations.

Capacity Reservation

Preallocate array capacity to reduce reallocations and copying during growth.

Bit-Packed Array

Store small integers or booleans using compact bit-level representation.

Sparse Array

Store only non-default values from a large logical array.

Sliding Window Array

Maintain a contiguous window over an array while moving its left and right boundaries.

Array Rotation

Rotate elements of an array by a given offset in-place or using auxiliary space.

Array Slicing

Represent a contiguous subrange of an array as either a view or a copied array.

Jagged Array

Store rows of different lengths as an array of arrays.

Multidimensional Array

Store values indexed by two or more dimensions using a linear memory layout.

Circular Array

Array that wraps indices modulo capacity to support efficient cyclic access.

Dynamic Array

Resizable array that grows and shrinks automatically while preserving contiguous storage.

gopy roadmap

Phased milestone plan from v0.0.1 (parser smoke) to v1.0 (full CPython parity). Defines the ordering of subsystem ports and the gating criteria for each release.

gopy overview

Top-level overview of the gopy project. Ports CPython's Python/ runtime to Go with 100% behavioural compatibility.

Exponential Backoff Search

Expand the search range exponentially until the target is bracketed, then refine within the range.

Merge Path Search

Find diagonal partition points that split a sorted merge into independent balanced ranges.

SIMD Binary Search

Use vector instructions to evaluate multiple candidate positions in a binary search step.

Branchless Lower Bound

Compute lower bound using arithmetic or conditional moves instead of branches.

Learned Index Search

Use a predictive model to estimate where a key should appear, then search within a bounded local range.

Interpolation Sequential Search

Estimate the likely position using interpolation, then refine by local sequential scan.

Finger Search

Search starting from a known nearby position, achieving time proportional to distance rather than full size.

Shear Sort

Sort a two dimensional mesh by alternating row sorts and column sorts until the grid is globally ordered.

Bitonic Sort on Hypercube

Sort distributed keys across hypercube processors using dimension based compare and exchange stages.

Parallel Sorting by Regular Sampling (PSRS)

Sort data in parallel by local sorting, regular sampling, global splitter selection, redistribution, and final local merge.

gopy pytime

Internal time utilities. Ports cpython/Python/pytime.c. Provides PyTime_t (int64 nanoseconds), monotonic / perf / wall clocks, double / timespec / timeval conversions, deadline math.

Distributed Range Partition Sort

Sort distributed data by assigning fixed key ranges to workers, routing records by range, then sorting locally.

Distributed Sample Sort

Sort data across machines by sampling keys, choosing splitters, redistributing records into ordered buckets, and sorting buckets locally.

TeraSort

Sort very large datasets with range partitioning, distributed shuffle, and reducer local sorting.

MapReduce Sort

Sort large distributed datasets by partitioning records by key range, sorting partitions locally, and writing ordered output shards.

Bitonic Merge Network

Merge a bitonic sequence into a sorted sequence using a fixed comparator network.

Odd Even Sorting Network

Sort a fixed size sequence using a data independent network of odd even compare exchange stages.

Bitonic Sorting Network

Sort a fixed size sequence with a bitonic compare and exchange network whose schedule is independent of input values.

SIMD Sorting Network

Sort a fixed size vector by mapping a data independent sorting network to SIMD compare, shuffle, and blend operations.

SIMD Bitonic Sort

Sort small vectors using SIMD registers with a fixed bitonic compare exchange network.

CUDA Block Sort

Sort a block sized tile on the GPU using shared memory and cooperative threads.

CUDA Warp Sort

Sort a small set of values inside one CUDA warp using shuffle operations and compare exchange steps.

GPU Sample Sort

Sort data on a GPU by selecting splitters, partitioning into buckets in parallel, then sorting buckets independently.

GPU Merge Sort

Sort data on a GPU by recursively merging sorted runs using parallel merge primitives.

GPU Radix Sort

Sort fixed width keys on a GPU using digit passes, parallel histograms, prefix sums, and scatter operations.

GPU Bitonic Sort

Sort data on a GPU using a regular bitonic compare and exchange network.

Parallel Counting Sort

Count key frequencies in parallel, compute prefix sums, then scatter elements into sorted positions.

Parallel Odd Even Sort

Sort an array by repeatedly comparing odd indexed and even indexed adjacent pairs in parallel.

Parallel Bitonic Sort

Sort data by building and merging bitonic sequences through a regular compare and exchange network.

Parallel Radix Sort

Sort integer keys by processing fixed width digit groups in parallel using counting and prefix sums.

Parallel Sample Sort

Choose splitters from samples, partition the input into buckets, sort buckets independently, then concatenate the sorted buckets.

Parallel Quicksort

Partition the array around a pivot, then sort partitions concurrently using parallel recursion.

Parallel Merge Sort

Divide the input, sort subarrays in parallel, then merge them using parallel merge procedures.

gopy vm remaining bytecodes

Bytecodes ported in v0.9 that finish the Tier-1 panel: import, generator, pattern-match, with/finally, set builders, and the async-protocol stubs.

gopy tokenize

Public TokenizerIter wrapper. Ports Python-tokenize.c. The actual lexer lives in cpython/Parser/tokenizer/ and is covered by the parser spec series.

gopy contextvars

PEP 567 contextvars. Ports cpython/Python/context.c plus _contextvars.c. Uses the HAMT (1662) as backing store.

gopy runtime helpers

Two small infra ports - getopt.c (CLI option parser used during interpreter init) and hashtable.c (generic _Py_hashtable_t internal hash table). Bundled because each is tiny and self-contained.

gopy hamt

Hash Array Mapped Trie immutable mapping. Backs contextvars (1663). Ports cpython/Python/hamt.c byte-for-byte preserving the 5-bit-per-level tree shape.

gopy objects overview

Top-level overview of the gopy Objects port. Ports cpython/Objects/ to Go with 100% behavioural compatibility. Lives in the 1670-1689 block of the 1600 spec series.

K Way Winner Tree Merge

K-way merge using a tournament tree that stores winners at internal nodes and repeatedly updates the winning path.

K Way Loser Tree Merge

Efficient k-way merge using a tournament tree that stores losers to reduce comparisons and improve external merge performance.

External Bucket Sort

External-memory bucket sort that partitions records into ordered buckets stored on disk and sorts each bucket separately.

External Sample Sort

External-memory sorting algorithm that uses sampling to partition data into balanced buckets, then sorts each bucket independently.

External Radix Sort

External-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.

Parallel External Merge Sort

External sorting algorithm that performs run generation and merging concurrently across multiple processors and disks.

Spill Sort

Sorting method that keeps data in memory until a memory limit is reached, then spills sorted runs to external storage and merges them.

Chunked Sort

Sorting method that divides input into bounded-size chunks, sorts each chunk independently, and then combines the chunks.

Memory Mapped External Sort

External sorting method that uses memory-mapped files so large data can be accessed through virtual memory while still sorting in chunks and merging runs.

Tape Merge Sort

External sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.

Replacement Selection Run Generation

External sorting technique that uses a heap to produce initial sorted runs longer than the available memory.

Sort Merge Join Sort Phase

The sorting stage used before a sort-merge join when one or both inputs are not already ordered by the join key.

Database External Sort

External sorting procedure used by database systems for ORDER BY, GROUP BY, DISTINCT, and sort-merge joins.

LSM Tree Compaction Sort

Sorting through hierarchical merging in Log Structured Merge Trees using compaction across levels.

B Tree Bulk Load Sort

Sorting method that builds a B-tree directly from sorted data using bulk loading to minimize I/O operations.

Buffer Tree Sort

External-memory sorting method that inserts records into a buffered tree and extracts them in sorted order.

Funnel Sort

Cache oblivious sorting algorithm that achieves optimal memory transfer complexity using recursive multiway merging structures called funnels.

Cache Oblivious Sorting

Sorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.

Cache Aware Sorting

Sorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.

Distribution Sweeping Sort

External-memory sorting method that partitions data into key ranges, sorts each range, and concatenates the sorted partitions.

Cascade Merge Sort

External sorting method that merges sorted runs through staged levels so output from one level feeds the next.

Balanced K Way Merge Sort

External sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.

Polyphase Merge Sort

External sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.

Two Phase Multiway Merge Sort

External sorting algorithm that performs run generation and a single multiway merge using limited memory.

External Merge Sort

Sort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.

Order Maintenance Sort

Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.

Lazy Selection Sort

Select the next smallest element on demand, avoiding full sorting until all elements are requested.

Lazy Sort

Delay sorting work until ordered output or ordered queries are actually needed.

Tournament Tree Partial Sort

Use a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.

Cartesian Tree Adaptive Sort

Sort by building a Cartesian tree that captures local order, then extracting elements in sorted order.

Smoothsort Adaptive Heap Sort

Sort in place with a heap-like structure that keeps worst-case O(n log n) time while approaching linear time on nearly sorted input.

Adaptive Heap Sort

A heap-based sorting method that adapts to partially ordered input to reduce unnecessary heap operations.

External Replacement Selection

Generate long initial runs for external sorting using replacement selection with disk-based streams.

Rolling Median Sort

Maintain the median of a sliding window using two heaps while the window moves over a stream.

Sliding Window Sort

Maintain sorted order over a moving window of the most recent elements in a stream.

Stream Sort by Buffer

Sort a stream in bounded chunks by buffering records, sorting each chunk, and emitting sorted runs or partially ordered output.

Binary Tree Online Sort

Maintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.

Insertion Sort with Sentinel

Optimize insertion sort by placing the minimum element at the front so the inner loop does not need a bounds check.

Online Topological Sort

Maintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.

Patience Sort with Piles

Sort a sequence by building piles using patience sorting and then merging them.

Adaptive Shivers Sort

An adaptive merge-based sorting algorithm that merges natural runs using stack rules designed to minimize merge cost.

Adaptive Samplesort

Partition data by sampled splitters, while adapting splitter choice to skewed or partially ordered input.

Galloping Merge

Accelerate merging by switching from one-by-one comparison to exponential search when one run wins repeatedly.

Timsort Run Detection

Detect natural runs in input and normalize them for efficient merging in Timsort.

Min Heap K Sorted Sort

Sort a k-sorted array using a sliding min heap window of size k+1.

K Sorted Array Sort

Sort an array where every element is at most k positions away from its final sorted position.

Nearly Sorted Insertion Sort

Sort an almost ordered sequence efficiently by using insertion sort, whose running time improves when few elements are far from their final positions.

Replacement Selection

Generate long sorted runs from a stream using a heap, commonly used in external sorting.

Patience Sorting for LIS

Use patience sorting to compute the length and structure of the longest increasing subsequence efficiently.

Natural Runs Sort

Sort a sequence by detecting already sorted runs and repeatedly merging them.

Adaptive Merge Sort

A merge sort variant that exploits existing order in the input by detecting natural runs and reducing work.

Online Insertion Sort

Sort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.

Incremental Sort

Maintain a sorted sequence while elements are inserted one by one, updating order incrementally.

Top K Sort

Extract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.

Partial Sort

Rearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.

Signed Integer Radix Sort

Radix sort for signed integers by transforming values to preserve ordering across negative and positive ranges.

Floating Point Radix Sort

Radix sort for floating-point numbers by transforming their bit representation to preserve numeric order.

DC7 Suffix Array Sort

Difference cover modulo 7 suffix array construction method that generalizes DC3 with a larger recursive sample.

DC3 Suffix Array Sort

Difference cover modulo 3 algorithm for linear-time suffix array construction using radix sorting and merging.

Skew Suffix Array Sort

Linear-time suffix array construction using the DC3 algorithm that recursively sorts positions modulo 3.

SA IS

Linear-time suffix array construction algorithm based on induced sorting of LMS suffixes.

Induced Sorting

Linear-time technique for suffix array construction that induces order of suffixes from a subset of sorted suffixes.

Least Significant Byte Sort

LSD radix sort variant that processes keys byte by byte from least significant to most significant.

Bytewise Radix Sort

Radix sort that processes fixed-width keys one byte at a time using 256 counting buckets.

Word Radix Sort

Radix sort specialized for fixed-width machine words using byte or bit extraction for high throughput.

Sparse Key Counting Sort

Counting sort variant that stores counts only for keys that appear, avoiding dense arrays over large key ranges.

Coordinate Compression Sort

Sort values by mapping them to a dense rank space and ordering by compressed indices.

Counting Sort with Negative Keys

Extend counting sort to handle negative integers by shifting keys into a nonnegative index range.

Suffix Array Doubling Sort

Construct a suffix array by iteratively sorting suffixes using doubling technique with rank pairs.

Three Way String Quicksort

String sorting algorithm that uses three-way partitioning on characters to efficiently handle repeated prefixes.

Multikey Quicksort

String sorting algorithm that partitions strings by the character at the current depth using three-way quicksort.

American Flag String Sort

In-place MSD radix string sort that partitions strings by character using American flag style bucket permutation.

Most Significant Byte Sort

MSD radix sort variant that partitions keys by the most significant byte and recursively sorts subarrays.

Integer Sample Sort

Sample sort specialized for integer keys using range-based partitioning and optional radix-style bucket classification.

IPS4o

In-place parallel super scalar samplesort for high performance comparison sorting on modern multicore machines.

Ska Sort

High performance radix sort variant using cache friendly block partitioning and branchless techniques.

Radix Exchange Sort

In place binary radix sort that partitions keys by bits from most significant to least significant.

Spreadsort

Hybrid distribution and comparison sort that adapts between radix-like partitioning and comparison sorting.

Flashsort

Distribution sorting algorithm that approximates uniform distribution and then refines with insertion sort.

Pigeonhole Sort

Sort integer keys by placing each value into a direct address slot over a small contiguous range.

Histogram Sort

Sort elements by building a frequency histogram and reconstructing the output from cumulative counts.

Uniform Bucket Sort

Bucket sort variant that assumes uniform distribution and uses equal-width buckets with simple mapping.

Bucket Sort

Distribute elements into buckets based on value ranges and sort each bucket independently.

Binary Radix Sort

Sort integers by processing bits directly using partitioning instead of counting arrays.

Counting Sort

Sort integers by counting occurrences of each key and reconstructing the output in linear time.

In Place Radix Sort

Sort digit based keys by redistributing elements inside the original array with only small auxiliary bucket state.

American Flag Sort

In place radix sort that partitions elements by digit using cycle leader permutation.

MSD Radix Sort

Sort keys by processing the most significant digit first and recursively sorting subarrays.

Key Indexed Counting

Counting-based stable sorting technique that maps keys to index ranges using frequency and prefix sums.

Stable Counting Sort

Stable variant of counting sort using prefix sums to preserve relative order of equal keys.

gopy marshal

Port of cpython/Python/marshal.c (2163 lines) to the marshal/ package. Full type-tag dispatch, TYPE_LONG arbitrary-precision encoding, FLAG_REF back-reference dedup, TYPE_CODE read/write, and .pyc file header. Gates the v0.8 milestone.

gopy codecs

Port of cpython/Python/codecs.c (1708 lines) to the codecs/ package. Codec registry, error-handler registry, Encode/Decode entry points, and the three built-in codecs (utf-8, ascii, latin-1) needed by the import source reader.

gopy import

Port of cpython/Python/import.c (4956 lines) and Python/frozen.c (132 lines). Frozen module loader, sys.modules lookup, source and bytecode loaders, builtin module table, and the IMPORT_NAME / IMPORT_FROM / IMPORT_STAR bytecodes. Gates v0.8.

gopy modules

Port of cpython/Python/bltinmodule.c (subset), sysmodule.c (subset), _warnings.c, and the _contextvars hook. The minimum builtins/sys surface v0.7 needs to ship.

gopy pythonrun

Port of cpython/Python/pythonrun.c. PyRun_SimpleString, PyRun_File, the REPL loop, and the .pyc read/write helpers that the lifecycle calls.

gopy lifecycle

Port of cpython/Python/pylifecycle.c, preconfig.c, initconfig.c, interpconfig.c, pathconfig.c. Py_Initialize / Py_Finalize and the config plumbing they consume.

gopy vm overview

Top-level overview of the gopy VM (Tier-1 bytecode interpreter) port. Covers ceval, ceval_macros, ceval_gil, frame, stackrefs, and the bytecodes DSL output. Lives in the 1630-1639 block.

gopy eval loop

Port of cpython/Python/ceval.c and cpython/Python/ceval_macros.h. The Tier-1 bytecode dispatch loop, exception unwind, generator resume, and call/return trampolines.

gopy eval gil

Port of cpython/Python/ceval_gil.c. The GIL acquire/release protocol, the eval breaker bitfield, signal pending flags, and the gopy-vs-Go-runtime threading mapping.

gopy bytecodes DSL

Port of cpython/Tools/cases_generator. Reads Python/bytecodes.c, emits the Go dispatch table at vm/opcodes_gen.go and metadata at compile/opcodes_gen.go.

gopy stackref

Port of cpython/Python/stackrefs.c. Tagged stack reference values, borrow tracking, and the conversion shims between PyObject* and stackref.

gopy intrinsics

Port of cpython/Python/intrinsics.c. The CALL_INTRINSIC_1 / CALL_INTRINSIC_2 dispatch tables that back compile-time-emitted runtime helpers (print expr, list-to-tuple, import-star, type-alias).

gopy frame

Port of cpython/Python/frame.c. Frame layout, locals-plus storage, frame chain push/pop, generator frame suspension.

Tournament Merge Sort

Merge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.

Multiway Merge Sort

Merge sort variant that merges more than two sorted sequences at each step.

Sample Sort

Divide and conquer sorting algorithm that uses sampling to partition data into balanced buckets.

Cache Oblivious Merge Sort

Merge sort variant that improves locality without tuning parameters for a specific cache size.

Cache Efficient Merge Sort

Merge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.

Batcher Merge Sort

Sorting network algorithm based on recursively sorting halves and merging them with Batcher's odd even merge network.

Pairwise Sorting Network

Sorting network that sorts by repeatedly applying pairwise compare and swap stages.

Odd Even Merge Sort

Sorting network algorithm that recursively merges sorted sequences using odd even comparisons.

Bitonic Sort

Comparison sorting algorithm that sorts a bitonic sequence using structured compare and swap operations.

Ford Johnson Sort

Comparison optimal sorting algorithm that minimizes comparisons using a structured insertion schedule.

Merge Insertion Sort

Comparison-optimal sorting algorithm that combines merging and insertion guided by a structured schedule.

Weak Heapsort

Heapsort variant based on weak heaps, reducing the number of comparisons while retaining in-place sorting.

Ternary Heapsort

Heapsort variant that uses a ternary heap with three children per node.

Bottom Up Heapsort

Heapsort variant that uses bottom up sift down to reduce comparisons during heapify.

Heapsort

Comparison sorting algorithm that builds a heap and repeatedly extracts the maximum.

Lomuto Partition Quicksort

Quicksort variant using the Lomuto single-index partition scheme.

Hoare Partition Quicksort

Quicksort variant that uses Hoare's two pointer partition scheme.

Quicksort Ninther

Quicksort variant that selects the pivot using Tukey's ninther, the median of three medians of three.

Quicksort Median of Three

Quicksort variant that chooses the pivot as the median of the first, middle, and last elements.

Stable Quicksort

Quicksort variant that preserves the relative order of equal elements.

Block Quicksort

Quicksort variant that processes elements in blocks to reduce branch misprediction and improve cache efficiency.

Pattern Defeating Quicksort

Quicksort variant that detects and avoids bad input patterns using adaptive partitioning and pivot selection.

Introsort

Hybrid sorting algorithm that starts with quicksort and falls back to heapsort when recursion becomes too deep.

Dual Pivot Quicksort

Quicksort variant that partitions the array using two pivots into three regions.

Three Way Quicksort

Quicksort variant that partitions into less than, equal to, and greater than pivot.

Randomized Quicksort

Quicksort variant that selects pivots randomly to avoid worst case patterns.

Quicksort

Divide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.

Powersort

Stable adaptive merge sort that uses power based ordering of runs for near optimal merging.

Timsort

Adaptive stable sorting algorithm that combines merge sort with run detection and insertion sort.

Block Merge Sort

Stable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.

In Place Merge Sort

Merge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.

Natural Merge Sort

Adaptive merge sort that detects existing sorted runs and merges them.

Bottom Up Merge Sort

Iterative merge sort that builds sorted runs from size 1 upward without recursion.

Top Down Merge Sort

Recursive merge sort that splits the array from the top and merges sorted halves.

Merge Sort

Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.

Exchange Sort

A simple quadratic sorting algorithm that compares all pairs and swaps out-of-order elements.

Bingo Sort

Repeatedly place all occurrences of the current minimum value before moving to the next distinct value.

Cartesian Tree Sort

Sort by building a Cartesian tree and extracting elements via inorder traversal.

Weak Heap Sort

A variant of heapsort using weak heaps with fewer comparisons.

Smoothsort

An adaptive in-place comparison sort based on Leonardo heaps.

Tournament Sort

Sort by repeatedly selecting the minimum element using a tournament tree.

Tree Sort

Insert all elements into a binary search tree, then traverse the tree in sorted order.

Patience Sort

Sort by building piles using patience card game rules and then merging them.

Library Sort

An insertion-based sorting algorithm that leaves gaps between elements to reduce shifting.

Strand Sort

Extract increasing subsequences and merge them to form a sorted sequence.

Bead Sort

Sort non-negative integers by simulating gravity on beads arranged in columns.

Slow Sort

A deliberately inefficient recursive sorting algorithm based on divide and conquer followed by maximum placement.

Stooge Sort

A recursive sorting algorithm with extremely poor performance based on overlapping subproblems.

Pancake Sort

Sort by repeatedly flipping prefixes to move the maximum element to its correct position.

Cycle Sort

Minimizes writes by placing each element directly into its correct position using cycles.

Comb Sort

A bubble-sort variant that compares elements at a shrinking gap to remove long-distance inversions early.

Shell Sort with Sedgewick Gaps

Shell sort using Sedgewick gap sequence for improved practical performance.

Shell Sort with Hibbard Gaps

Shell sort using Hibbard gap sequence 1, 3, 7, 15, ..., improving over simple halving.

Shell Sort with Shell Gaps

Shell sort using the original gap sequence n/2, n/4, ..., 1.

Shell Sort

Generalization of insertion sort that compares elements at a gap, reducing long-distance inversions early.

Binary Insertion Sort

Insertion sort that uses binary search to find the insertion position, reducing comparisons.

Insertion Sort

Build a sorted sequence by inserting each element into its correct position.

Double Selection Sort

Select both minimum and maximum elements in each pass and place them at the beginning and end.

Stable Selection Sort

A stable variant of selection sort that preserves the relative order of equal elements by shifting instead of swapping.

Selection Sort

Repeatedly select the minimum element from the unsorted portion and place it at the beginning.

Gnome Sort

A simple sorting algorithm that moves elements backward when out of order, similar to insertion sort with swaps.

Odd Even Sort

A variation of bubble sort that alternates between comparing odd-even and even-odd index pairs.

Bubble Sort

Repeatedly swap adjacent elements that are out of order until the sequence becomes sorted.

Cocktail Shaker Sort

A bidirectional variant of bubble sort that alternates passes from left to right and right to left.

Optimized Bubble Sort

Bubble sort with early termination when no swaps occur, reducing unnecessary passes on nearly sorted data.

Greenwald Khanna Quantile

Maintain deterministic approximate quantiles of a stream with rank error guarantees.

Quantile Summary

Maintain approximate quantiles of a stream using compact summaries.

Sample Sort Selection

Use sampling to approximate order statistics and refine selection efficiently.

Floyd Sampling

Select k distinct integers uniformly from a fixed range without shuffling the whole range.

Weighted Reservoir Sampling

Select a random sample from a stream where each item has a nonnegative weight.

Reservoir Sampling

Select a uniform random sample from a stream of unknown length using fixed memory.

Kth Largest in Stream

Maintain the k-th largest value while values arrive one at a time.

Kth Smallest Fraction

Select the k-th smallest fraction formed by pairs from a sorted array using heap or binary search.

Kth Smallest in Two Sorted Arrays

Select the k-th smallest element from two sorted arrays without merging them.

Multi Selection

Select multiple order statistics in one pass more efficiently than repeated selection.

Upper Median Selection

Select the upper median, the element at index floor(n/2), using selection or partitioning.

Lower Median Selection

Select the lower median, the element at index floor((n-1)/2), using selection or partitioning.

Weighted Median

Select an element whose total weight on each side is at most half of the total weight.

Order Statistic Tree Rank

Compute the sorted-order rank of a key in a search tree augmented with subtree sizes.

Order Statistic Tree Select

Select the element with a given rank from a balanced search tree augmented with subtree sizes.

Median Maintenance by Two Heaps

Maintain the median of a stream using a max heap and a min heap.

Quickselect

Select the k-th smallest element in an unsorted array using partitioning.

Count Min Sketch Query

Estimate item frequencies in a stream using a compact hash based summary.

Space Saving Algorithm

Approximate frequent items in a stream with tighter error bounds than Misra Gries.

Misra Gries

Find frequent items in a stream by maintaining a bounded set of counters.

Streaming Heavy Hitters

Find frequent items in a stream using bounded memory.

Streaming Top K

Maintain the k largest elements while values arrive one at a time.

Bottom K Selection

Select the k smallest elements using bounded structures or partitioning.

Top K by Quickselect

Find the k largest elements using partition-based selection in linear time.

Top K by Heap

Find the k largest or k smallest elements by maintaining a bounded heap.

Nth Element

Rearrange an array so that the element at position k is the same as in sorted order, with partition guarantees.

Partial Sort Selection

Select the k-th element by partially sorting only the needed prefix of the array.

Heap Select

Select the k-th smallest or largest element by maintaining a heap of candidate values.

Introselect

Hybrid selection algorithm that combines Quickselect with worst-case fallback.

Median of Medians

Choose a pivot with guaranteed quality by taking the median of group medians.

Deterministic Select

Selection algorithm with guaranteed linear time using structured pivot choice.

Randomized Quickselect

Quickselect with random pivot selection to achieve robust expected linear time.

Octree Search

Search for points or regions in 3D space using recursive octant decomposition.

SA-IS Suffix Array Construction

Linear time suffix array construction using induced sorting of LMS substrings.

Quadtree Search

Search for points or regions in 2D space using recursive quadrant decomposition.

R Tree Search

Search for spatial objects using hierarchical minimum bounding rectangles.

Cover Tree Search

Nearest neighbor search in metric space using hierarchical covers with exponential scale separation.

VP Tree Search

Nearest neighbor search in metric space using vantage point partitioning.

Ball Tree Search

Search for nearest neighbors in metric space using hierarchical clustering with hyperspheres.

k-d Tree Search

Search for nearest or range points in k-dimensional space using recursive axis splitting.

Range Tree Search

Search for all points within a multidimensional range using layered balanced search trees.

Interval Tree Search

Search for all intervals that overlap a query interval using a balanced interval tree.

DC7 Suffix Array Sort

Generalized divide and conquer suffix array construction using modulo 7 partitioning.

Skew Suffix Array Sort (DC3)

Linear time suffix array construction using the DC3 divide and conquer strategy.

Suffix Array Doubling Sort

Build a suffix array using the prefix doubling technique with iterative ranking.

LCP Accelerated Suffix Search

Search for a pattern in a suffix array using LCP information to reduce redundant character comparisons.

Suffix Array Binary Search

Search for a pattern in a text by binary searching the lexicographically sorted suffix array.

Suffix Tree Search

Search for a pattern in a text using a suffix tree in time proportional to the pattern length.

Ternary Search Tree Search

Search for a string key in a ternary search tree using character comparisons and three-way branching.

Patricia Trie Search

Search for a key in a Patricia trie using bitwise branching with path compression.

Radix Tree Search

Search for a string or byte key in a radix tree using variable length edge labels.

Compressed Trie Search

Search for a string key in a trie whose unary paths are compressed into edge labels.

Trie Search

Search for a string key in a prefix tree by following character transitions.

Y Fast Trie Search

Search for an integer key using a Y fast trie, combining hashing with balanced trees for linear space.

X Fast Trie Search

Search for an integer key in an X fast trie using hashed prefixes over a binary trie.

Van Emde Boas Search

Search for an integer key in a van Emde Boas tree using recursive universe decomposition.

B Star Tree Search

Search in a B* tree, a B tree variant that keeps nodes denser by redistributing entries before splitting.

B Plus Tree Search

Search in a B+ tree where all records are stored in leaves and internal nodes guide traversal.

B Tree Search

Search for a key in a multiway balanced search tree optimized for block based storage.

Weight Balanced Tree Search

Search in a binary search tree that keeps subtree sizes balanced to guarantee logarithmic height.

Scapegoat Tree Search

Search in a weight balanced binary search tree that rebuilds subtrees to preserve logarithmic height.

Splay Tree Search

Search in a self-adjusting binary search tree that moves accessed nodes toward the root.

Binary Search Tree Search

Search for a key in a binary search tree by exploiting ordering between nodes.

Randomized BST Search

Search in a binary search tree maintained with randomization to achieve expected logarithmic height.

Treap Search

Search in a randomized binary search tree that also maintains heap order over priorities.

Red Black Tree Search

Search in a balanced binary search tree with relaxed balancing using color properties.

AVL Tree Search

Search in a height balanced binary search tree with guaranteed logarithmic depth.

Binary Search

Search a sorted array by repeatedly halving the search interval.

Last Occurrence Search

Find the largest index at which a target value appears in a sequence.

First Occurrence Search

Find the smallest index at which a target value appears in a sequence.

Recursive Linear Search

Linear search expressed recursively by reducing the problem size one element at a time.

Hash Index Probe

Retrieve rows by probing a hash-based index structure using an exact key match.

Hash Join Lookup

Find matching records during a join by probing a hash table built from one relation.

Rabin Karp Search

Search for a pattern in text by comparing rolling hash values before verifying matching windows.

Separate Chaining Search

Resolve hash collisions by storing multiple elements in buckets using linked structures.

Hash Table Lookup

Retrieve a value by computing a hash and probing a table for the corresponding key.

Bounded Linear Search

Linear search restricted to a specified index range within a sequence.

Reverse Linear Search

Scan a sequence from right to left to find the last occurrence of a target value.

Sentinel Linear Search

Linear search optimized by placing a sentinel value to eliminate boundary checks inside the loop.

Linear Search

Scan a sequence from left to right until the target value is found or the sequence ends.

Rolling Hash Search

Search for a pattern in a sequence by maintaining a hash over a sliding window.

MinHash Similarity Search

Estimate set similarity and find similar items using compact MinHash signatures and banding.

SimHash Near Duplicate Search

Find near duplicate documents by comparing compact SimHash fingerprints under Hamming distance.

Locality Sensitive Hashing Search

Search for approximate nearest neighbors by hashing similar items into the same buckets with high probability.

Rendezvous Hashing Lookup

Map a key to the node that receives the highest hash score for that key.

Consistent Hashing Lookup

Map a key to a node by placing both on a hash ring and selecting the next node clockwise.

Binary Fuse Filter Lookup

Test approximate membership using a compact XOR-based filter with improved construction and cache locality.

XOR Filter Lookup

Test approximate membership with a static fingerprint filter built from three hash locations and XOR constraints.

Cuckoo Filter Lookup

Test approximate membership by storing compact fingerprints in cuckoo hash table buckets.

Quotient Filter Lookup

Test approximate membership by splitting a hash fingerprint into quotient and remainder fields.

Counting Bloom Filter Membership

Test membership with a Bloom filter variant that supports deletions using small counters instead of bits.

Bloom Filter Membership

Test set membership with a compact probabilistic bit array that allows false positives but no false negatives.

Minimal Perfect Hashing Lookup

Look up a key using a collision free hash function that maps a static key set to exactly n table positions.

Perfect Hashing Lookup

Look up a key in a static hash table whose hash function has no collisions for the stored key set.

Robin Hood Hashing Lookup

Search in an open addressing hash table that keeps probe distances balanced across keys.

Hopscotch Hashing Lookup

Search in a hash table that maintains elements within a small neighborhood of their home bucket.

Cuckoo Hashing Lookup

Look up a key in a cuckoo hash table by checking a small fixed set of candidate positions.

Double Hashing Search

Resolve hash collisions using a second hash function to define probe steps.

Quadratic Probing Search

Resolve hash collisions by probing with quadratic offsets to reduce clustering.

Linear Probing Search

Resolve hash collisions by scanning sequential slots until the key is found or an empty slot appears.

Last True Binary Search

Find the last position where a monotone predicate remains true.

Equal Range Search

Find the range of indices containing all occurrences of a value in a sorted array.

Upper Bound

Find the first index where elements become strictly greater than a given value.

Integer Square Root by Binary Search

Compute the floor of the square root of a nonnegative integer using binary search.

Monotone Predicate Search

Find the boundary where a Boolean predicate changes value over an ordered domain.

gopy parser overview

Top-level overview of the gopy Parser port. Covers the PEG parser, lexer, tokenizer drivers, string literal parser, error helpers, and readline. Lives in the 1640-1645 block of the 1600 spec series.

gopy parser errors and helpers

Port of cpython/Parser/pegen_errors.c, action_helpers.c, peg_api.c, and token.c. SyntaxError text panel, AST construction helpers, and the token table.

gopy lexer and tokenizer

Port of cpython/Parser/lexer/ and cpython/Parser/tokenizer/. Lexer state machine, buffer, token emission, and the four tokenizer drivers (file, string, utf8, readline).

gopy pegen

Port of cpython/Parser/pegen.c and the generated cpython/Parser/parser.c. PEG runtime plus the parser table that turns a token stream into an AST.

Bisection Method

Find a root of a continuous function by repeatedly halving an interval where the function changes sign.

Offline Binary Search

Answer many monotone queries by processing them together after all input is known.

Parallel Binary Search

Answer many offline queries by searching their answers simultaneously with shared checks.

Powers of Two Search

Search for a boundary by trying decreasing jumps whose lengths are powers of two.

Binary Lifting Search

Find a target state by jumping through powers of two in a precomputed lifting table.

Fractional Cascading Search

Speed up repeated binary searches across related sorted lists by linking sampled elements between lists.

Sorted Matrix Search

Search a matrix sorted by rows and columns using divide and conquer.

Saddleback Search

Search a matrix sorted by rows and columns using a monotone path from a corner.

Matrix Binary Search

Search a row-major sorted matrix by treating it as a virtual sorted array.

Two Dimensional Peak Finding

Find a peak element in a 2D grid using divide and conquer.

One Dimensional Peak Finding

Find an element that is at least as large as its immediate neighbors.

Bitonic Array Search

Search a value in an array that first increases and then decreases.

Rotated Array Minimum Search

Find the smallest element in a sorted array that has been rotated around an unknown pivot.

Rotated Array Search

Search a value in a sorted array that has been rotated around an unknown pivot.

Continuous Ternary Search

Find the maximum or minimum of a unimodal function over a continuous domain.

Discrete Ternary Search

Find the maximum or minimum of a unimodal function defined on discrete indices.

Jump Search

Search a sorted array by jumping in fixed steps, then performing a linear scan within a block.

Fibonacci Search

Search a sorted array using Fibonacci numbers to divide the range.

Uniform Binary Search

Binary search variant that uses precomputed step sizes instead of dynamic midpoint calculation.

Interpolation Search

Search a sorted numeric array by estimating the likely position of the target from its value.

Galloping Search

Expand the search range exponentially from a starting position, then apply binary search.

Exponential Search

Locate a search interval by exponential growth, then apply binary search.

Binary Search on Answer

Find an optimal value by binary searching a monotone feasibility condition.

First True Binary Search

Find the first position where a monotone predicate becomes true.

Lower Bound

Find the first position where a value can be inserted without violating sorted order.

Recursive Binary Search

Binary search implemented using recursion over a shrinking interval.

Iterative Binary Search

Binary search implemented using a loop without recursion.

Unsorted Membership Search

Check whether a value exists in an unsorted sequence.

Local Minimum Linear Search

Find an index where an element is smaller than its neighbors using a linear scan.

Second Maximum Search

Find the second largest element in a sequence.

Second Minimum Search

Find the second smallest element in a sequence.

Boyer Moore Majority Vote

Find a majority element in linear time using cancellation.

Majority Candidate Scan

Find a candidate element that may appear more than half the time using a linear scan.

Frequency Count Search

Count the number of occurrences of a target value in a sequence.

Duplicate Detection by Scan

Detect whether a sequence contains duplicate elements using a direct scan.

Pairwise Min Max Search

Find both minimum and maximum with fewer comparisons by processing elements in pairs.

Min Max Search

Find both the minimum and maximum elements in a sequence using a single pass.

Maximum Search

Find the index of the maximum element in an unsorted sequence.

Minimum Search

Find the index of the minimum element in an unsorted sequence.

All Occurrences Search

Find all indices where a target value appears in a sequence.

gopy string parser

Port of cpython/Parser/string_parser.c. Decodes Python string, bytes, f-string, and t-string literals into AST nodes. Handles escape sequences, prefixes, and f-string interpolation re-entry.

Preface

How this volume defines the ground layer of mathematics: language, structure, and method before specialization.

Preface

Purpose, scope, and approach of this volume on the history and biography of mathematics.

Preface

Overview of mathematical logic, its scope, and the structure of the book.

Preface

This book is a working manual for the Lean proof assistant.

Chapter 24. Limits of Formal Systems

Incompleteness, undecidability, independence, practical implications, and future directions in logic and foundations.

Chapter 22. Foundations Programs

Logicism, formalism, intuitionism, structuralism, and modern perspectives on the foundations of mathematics.

Chapter 22. Foundations Programs

Logicism, formalism, intuitionism, structuralism, and modern perspectives on the foundations of mathematics.

Chapter 20. Logic in Programming

Logic programming, type systems, verification, model checking, and program synthesis.

Chapter 20. Logic in Programming

Logic programming, type systems, verification, model checking, and program synthesis.

Chapter 19. Formal Languages

Grammars, syntax, automata theory, regular and context free languages, parsing, recognition, and applications in compilers.

Chapter 17. Type Theory

Simple type theory, dependent types, Curry-Howard correspondence, proof assistants, and formalized mathematics.

Chapter 17. Type Theory

Simple type theory, dependent types, Curry-Howard correspondence, proof assistants, and formalized mathematics.

Chapter 16. Intuitionistic Logic

Constructive semantics, proof interpretation, differences from classical logic, Kripke models, and applications in computation.

Chapter 15. Ordinal Analysis

Proof theoretic ordinals, transfinite induction, strength of theories, applications to arithmetic, and limits of formal strength.

14.5 Extensions and Refinements

Stronger forms of incompleteness, Rosser’s improvement, Löb’s theorem, and connections to computability.

14.4 Implications for Formal Systems

Consequences of incompleteness for truth, provability, independence, and the structure of formal systems.

14.2 First Incompleteness Theorem

Construction of a true but unprovable statement using diagonalization and self-reference.

Chapter 14. Godel Theorems

Arithmetization of syntax, the first and second incompleteness theorems, implications for formal systems, and refinements.

13.5 Proof Length and Complexity

Quantitative study of proofs, including proof size, efficiency, and connections to computational complexity.

13.4 Consistency Proofs

Methods for proving consistency of formal systems, including syntactic and semantic approaches.

13.3 Normal Forms

Normalization of proofs, elimination of detours, and structural simplification of derivations.

13.2 Derivability

Formal notion of deriving formulas from assumptions, including structural properties and inference behavior.

13.1 Syntax of Proofs

Formal structure of proofs, including derivations, inference rules, axioms, and proof representations.

Chapter 13. Formal Proof Systems

Syntax of proofs, derivability, normal forms, consistency proofs, proof length, and proof complexity.

12.5 Structure of Degrees

Global properties of the Turing degrees including incomparability, density, and jump structure.

12.4 Post’s Problem

Existence of intermediate degrees between computable sets and the halting problem.

12.3 Recursively Enumerable Sets

Sets that can be enumerated by algorithms and their role in semi-decidability and computability theory.

12.2 Turing Degrees

Equivalence classes of sets under Turing reducibility and the ordering of computational power.

12.1 Reducibility

Formal methods for comparing decision problems using many-one and Turing reducibility.

Chapter 12. Degrees of Unsolvability

Reducibility, Turing degrees, recursively enumerable sets, Post's problem, and the structure of degrees.

11.5 Undecidability Results

Extensions of undecidability using reductions and general results such as Rice’s theorem.

11.4 Halting Problem

The undecidable problem of determining whether a Turing machine halts on a given input.

11.3 Universal Machines

Machines that simulate any other Turing machine, establishing the concept of programmable computation.

11.2 Computation Traces

Step-by-step evolution of Turing machine configurations and how computations are represented as traces.

11.1 Machine Definitions

Formal definition of Turing machines, including states, tape, alphabets, and transition functions.

Chapter 11. Turing Machines

Turing machine definitions, computation traces, universal machines, the halting problem, and undecidability results.

10.5 Style Guidelines

Practical rules for writing mathematics in a clear, consistent, and readable way.

10.4 Common Pitfalls

Common mistakes in mathematical writing and how to avoid them.

10.4 Formal Models of Computation

Turing machines, register machines, lambda calculus, recursive functions, and the precise mathematical models used to define computation.

10.3 Clarity and Minimalism

How to write mathematics with enough detail, few distractions, and clear logical structure.

10.3 Church Turing Thesis

The Church Turing thesis, formal models of computation, equivalence of models, and the distinction between mathematical theorem and foundational principle.

10.2 Definitions, Theorems, Proofs

How definitions, theorems, and proofs work together in mathematical writing.

10.1 Structure of a Paper

How a mathematical paper or article is organized so that readers can follow the main ideas.

Chapter 10. Writing Mathematics

Overview of how to write mathematical ideas clearly, precisely, and in a useful structure.

Chapter 10. Computable Functions

Recursive functions, partial and total functions, the Church-Turing thesis, formal models of computation, and equivalence of models.

9.5 Reproducibility and Verification

How to make computational results repeatable, checkable, and trustworthy.

9.5 Applications in Analysis and Topology

Applications of advanced set theory to analysis and topology, including regularity properties, Banach spaces, measure theory, and topological classification.

9.4 Symbolic vs Numeric Methods

Understanding the difference between manipulating exact mathematical expressions and computing with numerical values.

9.4 Determinacy Principles

An introduction to infinite games, determined games, the axiom of determinacy, projective determinacy, and consequences for sets of reals.

9.3 Exact vs Approximate Computation

When to compute exact results and when to use approximations.

9.3 Descriptive Set Theory

An introduction to Polish spaces, Borel sets, analytic sets, projective sets, regularity properties, and the role of definability in set theory.

9.2 Complexity Awareness

Understanding how the cost of an algorithm grows with input size.

9.1 Algorithmic Thinking

How to think step by step and turn mathematical ideas into clear procedures.

Chapter 9. Computation and Algorithms

Overview of algorithmic thinking, computational methods, complexity, approximation, and verification in mathematics.

Chapter 9. Advanced Set Theory

Forcing, large cardinals, descriptive set theory, determinacy principles, and applications in analysis and topology.

8.5 Counterexamples and Edge Cases

Using failures, boundary conditions, and extreme cases to test, refine, and understand mathematical statements.

8.5 Independence Phenomena

Independence results in set theory, including the axiom of choice and the continuum hypothesis, and the methods used to establish independence.

8.4 Heuristics and Experimentation

Using examples, informal rules, and exploratory computation to guide mathematical problem solving.

8.4 Consistency Results

Relative consistency, inner models, constructibility, and the role of consistency results in axiomatic set theory.

8.3 Analogy and Transfer

Using structural similarity between problems to move ideas, methods, and proofs across domains.

8.2 Generalization and Specialization

Expanding or restricting a problem to reveal structure and guide solution.

8.1 Reduction and Transformation

Solving a problem by converting it into a simpler, known, or more structured form.

Chapter 8. Problem Solving Strategies

Overview of general methods used to approach, transform, and solve mathematical problems.

Chapter 8. Axiomatic Systems

Axiom of Choice, equivalent formulations, constructible universe, consistency results, and independence phenomena.

7.5 Probabilistic and Combinatorial Proofs

Using counting, random choice, and finite structure to prove identities and existence statements.

7.5 Zermelo Fraenkel Axioms (ZF, ZFC)

The axioms of Zermelo Fraenkel set theory, the role of choice, and the use of axioms as a foundation for mathematics.

7.4 Constructive Proofs

Proving existence by giving explicit witnesses, algorithms, or methods of construction.

7.3 Induction and Recursion

Using base cases and step rules to prove statements about objects built recursively.

7.3 Ordinals and Well Ordering

Well ordered sets, order isomorphisms, ordinals, successor ordinals, limit ordinals, and transfinite induction.

7.2 Proof by Contradiction

Proving a statement by assuming its negation and deriving an impossibility.

7.2 Cardinality and Countability

Cardinality, finite and infinite sets, countable sets, uncountable sets, and Cantor diagonal arguments.

7.1 Direct Proof

Proving a statement by starting from its assumptions and deriving its conclusion step by step.

Chapter 7. Proof Techniques

Overview of the main methods used to prove mathematical statements.

Chapter 7. Basic Set Theory

Basic set theoretic notions including sets, relations, functions, cardinality, ordinals, well ordering, cardinal arithmetic, and the ZF and ZFC axioms.

6.25 Choosing the Right Sort

Select the appropriate sorting algorithm based on input size, data characteristics, memory constraints, and required guarantees such as stability or worst-case bounds.

6.24 Common Bugs

Identify boundary errors, broken invariants, and comparator mistakes that cause sorting implementations to fail on edge cases or duplicate-heavy inputs.

6.23 Testing Sort Correctness

Verify both the ordering and permutation properties of sorting implementations using randomized, edge-case, and adversarial test strategies.

6.22 Parallel Sorting

Distribute sorting work across multiple processors to reduce wall-clock time, with analysis of total work, span, communication, and synchronization.

6.21 Lower Bounds for Sorting

Prove that any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case using a decision tree argument.

6.20 Inversion Counting

Count pairs of elements in the wrong relative order to measure how far an array is from sorted, using a modified merge sort in O(n log n) time.

6.19 Coordinate Compression

Replace large or sparse keys with small dense ranks that preserve order, making range-based and indexed structures practical on wide-valued data.

6.18 Sorting Records

Sort structured values by one or more fields while moving the full record, with attention to key extraction, stability, and multi-key ordering.

6.17 Custom Comparators

Define correct comparison relations for user-defined types and non-trivial orderings — consistency requirements that sorting correctness depends on.

6.16 Nearly Sorted Data

Exploit near-sorted structure in inputs like append-only logs or incremental updates to sort in linear or near-linear time.

6.15 External Sorting

Sort datasets that exceed main memory by organizing the algorithm around sequential disk access, merge passes, and minimizing I/O operations.

6.14 Median Selection

Find the middle value of a collection in linear time using selection algorithms, without the overhead of a full sort.

6.13 Quickselect

Find the element at a given rank using quicksort's partition step but recursing into only one side, achieving expected linear time.

6.12 Top k Selection

Find the largest or smallest k elements without sorting the full input, using a heap or partition-based approach.

6.11 Partial Sorting

Produce only the smallest k elements in sorted order rather than sorting the entire array, reducing unnecessary work when the full order is not needed.

6.10 Stable Sorting

A stable sort preserves the original relative order of equal keys — an extra guarantee required when sorting by secondary fields or compound criteria.

6.9 Bucket Sort

Distribute elements into buckets by value range, sort each bucket, then concatenate — achieving linear expected time on uniformly distributed input.

6.8 Radix Sort

Sort keys digit by digit using a stable subroutine, achieving linear time for fixed-width integers without any key comparisons.

6.7 Counting Sort

Sort integer keys from a small range in linear time by counting occurrences and reconstructing the output from those counts.

6.6 Heap Sort

Build a max-heap in place, then repeatedly extract the maximum to produce a sorted array in O(n log n) worst-case time.

6.5 Recursion and Induction

Defining objects step by step and proving properties by following the same construction.

6.5 Classification Programs

Detailed overview of classification theory, dividing lines such as stability, simplicity, and NIP, and the structural analysis of first order theories.

6.5 Quick Sort

Partition around a pivot so smaller elements go left and larger go right, then recursively sort each partition in expected O(n log n) time.

6.4 Decomposition and Composition

Breaking complex objects into simpler parts and building larger structures from controlled combinations.

6.4 Stability Theory Overview

Detailed introduction to stability theory, counting types, order property, definability of types, and structural consequences.

6.4 Merge Sort

Divide the input into halves, recursively sort each half, then merge them — combining local order into global order in O(n log n) time.

6.3 Local-to-Global Principles

How mathematics studies small pieces first and then assembles them into statements about the whole.

6.3 Saturated Models

Saturated models, realization of types, and their role in controlling definability and extensions.

6.3 Insertion Sort

Build a sorted prefix one element at a time by inserting each new element into its correct position within the already-sorted portion.

6.2 Symmetry and Invariance

How transformations preserve structure and how invariants record what remains unchanged.

6.2 Selection Sort

Sort by repeatedly selecting the minimum element from the unsorted suffix and placing it into the next output position.

6.1 Duality

Understanding how reversing structure reveals parallel theories and results.

6.1 Definable Sets and Functions

Definition of definable sets and functions in first order structures, with parameters, examples, closure properties, and proofs.

6.1 Sorting Contracts

A sorting algorithm is correct only when its output is both ordered and a permutation of the input — two properties every implementation must preserve.

Chapter 6. Patterns Across Mathematics

Overview of recurring patterns such as duality, symmetry, local-to-global reasoning, decomposition, recursion, and induction.

Chapter 6. Definability and Types

Definable sets, definable functions, types, realizations, saturated models, stability theory, and classification programs.

5.25 Case Studies

Examine hash-based structures in complete systems: streaming pipelines, graph algorithms, caches, and distributed workflows.

5.24 Real-World Hash Table Design

Choose and implement hash tables that perform reliably under mixed key types, uneven access patterns, and adversarial input.

5.23 Cache-Aware Hashing

Design hash table layouts that minimize cache misses and align memory access patterns with hardware behavior.

5.22 Hybrid Hash Structures

Combine hash tables with other data structures to handle skewed distributions, heavy deletions, and mixed workloads.

5.21 Consistent Performance Guarantees

Achieve predictable worst-case bounds for hash-based structures rather than relying solely on average-case expectations.

5.20 Testing Hash Logic

Verify correctness, stability, and performance of hash-based structures through randomized and adversarial test strategies.

5.19 Deterministic Hashing

Produce stable hash values that remain consistent across program runs, machines, builds, and language runtimes.

5.18 Attack Resistance

Defend hash tables against adversarial inputs that force worst-case collision behavior using randomized hashing.

5.17 Cache Behavior

Understand how memory hierarchy effects cause hash table performance to deviate from asymptotic expectations.

5.16 Hash-Based Deduplication

Remove duplicate entries from a dataset or stream efficiently using hash sets for membership tracking.

5.15 Hash Joins

Join two collections by key using a hash table to reduce the cost from quadratic to linear expected time.

5.14 Consistent Hashing

Distribute keys across a dynamic set of nodes so that adding or removing nodes moves only a minimal fraction of keys.

5.13 Count-Min Sketch

Approximate frequency counting for large key streams using a compact probabilistic data structure with bounded error.

5.12 Bloom Filters

Test set membership approximately using a compact bit array and multiple hash functions, with no false negatives and bounded false positives.

5.11 Rolling Hashes

Compute hash values for sliding windows over a sequence in constant time by incrementally updating rather than recomputing.

5.10 Composite Keys

Hash and compare multi-field keys correctly by combining all fields that participate in equality into the hash function.

5.9 Grouping Keys

Partition a collection into groups by key using a hash map that accumulates values into per-key lists or sets.

5.8 Counting Maps

Track frequency counts for keys using a hash map that increments a counter on each insertion of an existing key.

5.7 Maps

Build a hash-based map that associates keys with values and supports insert, lookup, delete, and update in expected constant time.

5.6 Sets

Implement a hash-based set for fast membership testing, insertion, and deletion without associated values.

5.5 Trade-offs in Abstraction

Understanding the benefits and costs of abstraction, and choosing the right level for mathematical work.

5.5 Limitations of First Order Logic

Expressive limitations of first order logic, including inexpressibility of finiteness and categoricity issues.

5.5 Rehashing

Rebuild a hash table's bucket array after resizing so that every stored key satisfies the placement invariant for the new capacity.

5.4 Meta-Mathematical Abstraction

Studying mathematical systems themselves through languages, axioms, models, proofs, and interpretations.

5.4 Nonstandard Models

Construction and properties of nonstandard models using compactness and Lowenheim Skolem.

5.4 Load Factor and Resizing

Control hash table performance by monitoring the load factor and growing the bucket array before collisions accumulate.

5.3 Categorical Abstraction

Raising abstraction from objects and operations to maps, composition, and universal properties.

5.3 Applications to Algebra

Applications of compactness and Lowenheim Skolem to algebraic structures and existence results.

5.3 Collision Handling

Resolve hash collisions using separate chaining or open addressing, with trade-offs in memory, locality, and load tolerance.

5.2 Algebraic Abstraction

Replacing concrete values with symbols and rules to express general patterns.

5.2 Lowenheim Skolem Theorems

Downward and upward Lowenheim Skolem theorems and their consequences for model sizes in first order logic.

5.2 Hash Functions

Design and evaluate hash functions that distribute keys uniformly across buckets while remaining fast to compute.

5.1 Concrete Computation

Working with explicit examples, calculations, and finite procedures as the base level of mathematical reasoning.

5.1 Compactness Theorem

Detailed development of the compactness theorem, its proof via completeness, and fundamental applications in model theory.

5.1 Hash Tables

A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.

Chapter 5. Levels of Abstraction

Overview of how mathematics moves from concrete computation to structural and higher-level reasoning.

Chapter 5. Compactness and Completeness

Compactness, completeness, Lowenheim-Skolem theorems, nonstandard models, and limitations of first order logic.

4.25 Common Pitfalls and Debugging

Rewriting failures in Lean usually come from a small set of recurring issues.

4.24 Rewriting Strategies and Heuristics

Rewriting is most effective when guided by a small set of consistent strategies.

4.23 Rewriting in Goals vs Hypotheses

Rewriting can target either the goal or the local context.

4.22 Rewriting with `conv`

The `conv` tactic provides fine-grained control over rewriting.

4.21 Rewriting in Pattern Matching

Pattern matching performs case analysis by selecting a branch based on the shape of a value.

4.20 Decidable Equality and Boolean Bridges

Reasoning often alternates between propositional equality `a = b` and boolean equality `a == b`.

4.19 Proof Irrelevance and Equality of Proofs

In Lean, propositions live in `Prop`, a universe where proof irrelevance holds.

4.18 Rewriting of Functions and Extensionality

Equality between functions requires a different treatment than equality between values.

4.17 Rewriting in Structures and Records

Structures package multiple fields into a single value.

4.16 Rewriting with Equivalences

Equalities are often too strict.

4.15 Avoiding Rewrite Loops and Nontermination

Rewriting systems can diverge if rules are poorly oriented or interact cyclically.

4.14 Dependent Rewriting and Transport

When types depend on values, rewriting affects both terms and their types.

4.13 Substitution and `subst`

Substitution is the direct elimination of equalities from the context.

4.12 Rewriting Under Binders

Rewriting becomes more subtle when the target term appears inside a binder.

4.11 Chained Rewriting and `calc`

Complex equalities are rarely achieved in a single step.

4.10 Rewriting with Lemmas

Lemmas provide reusable equalities that drive most rewriting.

4.9 Rewriting with Hypotheses

In most proofs, equalities come from the local context.

4.8 Case Analysis and Rewriting

Case analysis splits a goal according to the structure of a value.

4.7 Controlling the `simp` Set

The behavior of `simp` depends entirely on the set of rewrite rules it uses.

4.6 Simplification with `simp`

The tactic `simp` performs normalization by repeated rewriting using a curated set of lemmas.

4.5 Examples: Groups, Spaces, Graphs

Concrete examples showing structural thinking across algebra, topology, and graph theory.

4.5 Examples Across Algebra and Geometry

Examples of first order structures from algebra, order theory, graph theory, and geometry.

4.5 Directed Rewriting with `rw`

Rewriting is the primary way to apply propositional equalities in Lean.

4.4 Invariants and Classification

How preserved quantities and properties support comparison, classification, and structural reasoning.

4.4 Congruence and Contextual Rewriting

Equality becomes useful when it propagates through larger expressions.

4.3 Isomorphism as Sameness

How isomorphism formalizes structural sameness and separates equality from equivalence.

4.3 Elementary Equivalence

Elementary equivalence, theories of structures, and preservation of first order sentences.

4.3 Reflexivity, Symmetry, and Transitivity

Propositional equality in Lean is generated from a small set of core operations.

4.2 Morphisms and Mappings

Structure-preserving maps, their role in comparison, composition, and transport of mathematical information.

4.2 Propositional Equality

Propositional equality is the explicit notion of equality in Lean.

4.1 Structure vs Instance

Distinguishing abstract structures from their concrete instances, and using that distinction to reason across examples.

4.1 Languages and Signatures

Formal languages, signatures, and symbols used to describe structures in first order logic.

4.1 Definitional Equality

Definitional equality is the built-in notion of equality used by the kernel of Lean.

Chapter 4. Structural Thinking

Overview of structures, mappings, invariants, and classification in mathematics.

Chapter 4. Structures and Models

Basic model theoretic notions including languages, signatures, substructures, embeddings, elementary equivalence, isomorphism, and examples.

3.25 Case Studies

This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.

3.24 Complexity Analysis

Linked list algorithms are dominated by pointer traversal and constant-time link updates.

3.23 Testing Pointer Code

Pointer code should be tested by checking structure, not only values.

3.22 Edge Cases

Edge cases are inputs that sit near the boundary of an algorithm's assumptions.

3.21 LRU Cache Structure

An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.

3.20 Queue via List

A queue is a first-in, first-out structure.

3.19 Stack via List

A stack is a last-in, first-out (LIFO) structure.

3.18 Iterators

An iterator is an object or procedure that visits the nodes of a linked list one at a time.

3.17 Memory Ownership

Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.

3.16 Intrusive Lists

An intrusive list stores the linkage fields inside the objects being linked.

3.15 Skip Lists

A skip list augments a sorted linked list with multiple levels of forward pointers.

3.14 Persistent Lists

A persistent list is a list that preserves older versions after an update.

3.13 Pointer Aliasing

Pointer aliasing occurs when two or more references point to the same node.

3.12 Dummy Heads (Dummy Nodes)

A dummy head is a fixed node placed before the real head of a singly linked list.

3.11 Insertion Patterns

Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.

3.10 Deletion Patterns

Deletion removes one or more nodes from a linked list by changing links around them.

3.9 Merge Patterns

Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.

3.8 Split Patterns

Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.

3.7 Merge Two Sorted Lists

Merging combines two sorted singly linked lists into one sorted list by relinking nodes.

3.6 Fast and Slow Pointers

Fast and slow pointers are two references that traverse the same linked structure at different speeds.

3.5 Notation as an Interface

Viewing notation as a designed interface that exposes structure, supports composition, and enables efficient reasoning.

3.5 Cut Elimination

The cut rule, its elimination, and consequences for consistency and normalization.

3.5 Cycle Detection

A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.

3.4 Precision vs Readability

How mathematical writing balances exact statements with readable exposition.

3.4 Proof Transformations

Transformations of proofs, normalization, and structural properties of derivations.

3.4 Reversal

Reversal transforms a linked list so that the direction of all edges is flipped.

3.3 Definitions and Naming Conventions

How definitions introduce mathematical objects, fix meaning, and support reusable reasoning.

3.3 Hilbert Systems

Hilbert style proof systems, axioms, and derivations using a minimal set of inference rules.

3.3 Sentinel Nodes

A sentinel node is an artificial node placed at the boundary of a linked list.

3.2 Formal vs Informal Language

How formal precision and informal readability work together in mathematical writing.

3.2 Sequent Calculus

Sequents, structural rules, and introduction rules for logical connectives in the sequent calculus.

3.2 Doubly Linked Lists

A doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node.

3.1 Symbols and Notation Design

How mathematical symbols and notation are chosen, scoped, reused, and designed for precision and readability.

3.1 Natural Deduction

Introduction to natural deduction, inference rules, and structured proofs for propositional logic.

3.1 Singly Linked Lists

A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.

Chapter 3. Mathematical Language

Overview of symbols, notation, definitions, and the balance between precision and readability.

Chapter 3. Proof Systems

Formal systems for deriving logical conclusions including natural deduction, sequent calculus, Hilbert systems, and proof transformations.

2.25 Common Proof Mistakes and Debugging

Lean proofs fail in predictable ways.

2.25 Boundary Conditions

Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.

2.24 Simplification and Automation

Lean provides automation to reduce routine proof steps.

2.24 Common Patterns

Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.

2.23 Rewriting Strategies

Rewriting with equality is one of the most frequent operations in Lean.

2.23 Flood Fill

Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region.

2.22 Backward Reasoning

Backward reasoning starts from the goal and reduces it to simpler subgoals.

2.22 Spiral Traversal

Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column,...

2.21 Forward Reasoning

Forward reasoning starts from the assumptions in the local context and derives new facts until the goal becomes immediate.

2.21 Matrix Traversal

Matrix traversal processes a two-dimensional array in a defined order.

2.20 Using Assumptions Effectively

An assumption is a local term that Lean may use to solve the current goal or produce another proof.

2.20 Tries

A trie is a tree structure for storing a set of strings so that common prefixes are shared.

2.19 Local Context Management

The local context is the list of variables, hypotheses, instances, and intermediate facts available at a point in a proof.

2.19 Parsing Expressions

Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.

2.18 Naming Conventions

Names in Lean carry meaning.

2.18 String Comparison

String comparison determines the ordering or equality of two strings.

2.17 Proof Structuring Patterns

A Lean proof should expose the shape of the argument.

2.17 Rolling Hashes

Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.

2.16 Introduction and Elimination Rules

Every logical connective in Lean has two sides.

2.16 Run-Length Encoding

Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.

2.15 Case Analysis

Case analysis is the proof pattern for using data that has more than one possible constructor.

2.15 Frequency Tables

A frequency table records how many times each value appears in an array, string, or stream.

2.14 Proof by Contradiction

Proof by contradiction is a classical proof pattern.

2.14 Anagrams

Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.

2.13 Classical vs Constructive Logic

Lean is constructive by default.

2.13 Palindromes

A palindrome is a sequence that reads the same forward and backward.

2.12 Universal Quantifiers

A universal statement asserts that a property holds for every element of a type.

2.12 Substring Search

Substring search locates occurrences of a pattern `p` inside a text `s`.

2.11 Existential Quantifiers

An existential statement says that some object exists with a given property.

2.11 Tokenization

Tokenization converts a string into a sequence of meaningful units called tokens.

2.10 Symmetry and Transitivity

Equality supports two structural operations: reversing direction (symmetry) and chaining steps (transitivity).

2.10 String Scanning

String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.

2.9 Rewriting with Equality

Rewriting is the main way to use equality in Lean.

2.9 Deduplication

Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.

2.8 Equality Basics

Equality expresses that two terms are identical.

2.8 In-Place Modification

In-place modification changes an array without allocating another array of the same size.

2.7 True and Trivial Proofs

`True` is the proposition that always has a proof.

2.7 Rotation

Array rotation moves elements by a fixed offset while preserving their relative circular order.

2.6 False and Contradiction

`False` is the proposition with no constructors.

2.6 Partitioning

Partitioning rearranges an array so that elements are grouped by a predicate.

2.5 Examples Across Fields

How truth, provability, consistency, completeness, and independence appear across major branches of mathematics.

2.5 Validity and Entailment

Validity, semantic entailment, satisfiability, countermodels, and logical consequence in first order logic.

2.5 Negation

Negation represents "not".

2.5 Sliding Windows

Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.

2.4 Independence Phenomena

Statements that cannot be proved or refuted from a chosen axiom system, and what independence means in mathematical practice.

2.4 Satisfaction and Models

Satisfaction, truth in a structure, models of sentences, and theories in first order logic.

2.4 Disjunction

Disjunction represents "or".

2.4 Two Pointers

The two pointers technique uses two indices that move through an array or string in a controlled way.

2.3 Consistency and Completeness

Core meta-properties of formal systems: avoiding contradiction and deciding statements.

2.3 Structures and Interpretations

Structures, domains, and interpretations of symbols in first order logic.

2.3 Conjunction

Conjunction represents "and".

2.3 Difference Arrays

A difference array is the inverse pattern of a prefix sum.

2.2 Formal Systems and Semantics

Syntax, axioms, inference rules, and the semantic interpretation of mathematical languages.

2.2 Quantifiers and Scope

Universal and existential quantifiers, scope, free variables, bound variables, and variable capture.

2.2 Implication and Functions

Implication is the first logical connective to understand in Lean because it is also the ordinary function type.

2.2 Prefix Sums

Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.

2.1 Truth vs Provability

Distinction between semantic truth and syntactic provability, with examples and limits.

2.1 Terms, Predicates, Formulas

Syntax of first order logic including terms, predicate symbols, and the formation of formulas.

2.1 Propositions as Types

Lean identifies propositions with types and proofs with terms.

2.1 Array Traversal

Array traversal is the base operation for all algorithms over linear data.

Chapter 2. Mathematical Truth

Overview of truth, provability, formal systems, and independence in mathematics.

Chapter 2. First-Order Logic

Extension of propositional logic with terms, predicates, quantifiers, structures, satisfaction, models, validity, and entailment.

1.25 Minimal Working Examples

A minimal working example is the smallest complete Lean fragment that demonstrates a definition, theorem, error, or technique.

1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways.

1.24 Editor Integration

Lean is normally developed inside an editor with live feedback.

1.24 Benchmarking

Benchmarking measures how an implementation behaves on real inputs and real hardware.

1.23 Interactive Development Workflow

Lean development is interactive.

1.23 Stability and Determinism

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers.

1.22 Imports and Dependencies

Imports control what a Lean file can see.

1.22 Numerical Limits

Algorithms are usually described with mathematical integers and real numbers.

1.21 Error Messages and Debugging

Lean’s error messages report failed constraints during elaboration.

1.21 Data Representation

Data representation is the choice of concrete form used to store the objects in a problem.

1.20 Holes and Goals

Lean development is driven by goals.

1.20 Implementation Discipline

Implementation discipline means translating an algorithm into code without changing its meaning accidentally.

1.19 Term Mode vs Tactic Mode

Lean proofs are terms.

1.19 Pseudocode Style

Pseudocode is a bridge between the problem statement and an implementation.

1.18 Basic Tactic Mode

Tactic mode is an interactive way to build proofs.

1.18 Reductions

A reduction transforms one problem into another problem.

1.17 Structures and Records

A structure is a type whose values are built from named fields.

1.17 Amortized Analysis

Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive.

1.16 Inductive Types Introduction

Inductive types define data by listing its constructors.

1.16 Randomization

Randomized algorithms use random choices during execution.

1.15 Pattern Matching Basics

Pattern matching defines functions by cases on the shape of their inputs.

1.15 Dynamic Programming

Dynamic programming solves problems by storing answers to subproblems and reusing them.

1.14 Simple Rewriting

Rewriting replaces one expression with another using an equality.

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers.

1.13 Checking Types with `#check`

Type checking is the primary feedback mechanism in Lean.

1.13 Greedy Choices

A greedy algorithm builds a solution by making one locally best choice at a time.

1.12 Evaluation with `#eval`

Lean can execute many expressions during development.

1.12 Brute Force Baselines

A brute force baseline is the simplest correct algorithm you can write from the problem statement.

1.11 Comments and Documentation

Lean files serve two readers at once: the compiler and the human maintainer.

1.11 Testing Algorithms

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details.

1.10 Notation and Infix Operators

Lean notation is ordinary syntax attached to ordinary declarations.

1.10 Edge Cases

Edge cases are valid inputs that sit at the boundary of the specification.

1.9 Implicit and Explicit Arguments

Lean functions often contain arguments that the user does not write.

1.9 Lower Bounds

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation.

1.8 Functions and Lambda Abstraction

Functions are the main form of computation in Lean.

1.8 Big O Notation

Big O notation provides a formal way to describe how a function grows.

1.7 Types and Universes

Lean is a dependently typed system.

1.7 Space Complexity

Space complexity measures how much memory an algorithm uses as a function of input size.

1.6 Theorems with `theorem` and `lemma`

Lean treats a theorem as a named proof.

1.6 Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows.

1.5 Constructive vs Classical Viewpoints

Comparison of constructive and classical mathematics, including existence, proof, logic, and computation.

1.5 Soundness and Completeness

Soundness, completeness, and the relationship between semantic validity and formal provability.

1.5 Definitions with `def`

A definition introduces a named term together with its type.

1.5 Recursion Invariants

Recursive algorithms replace loop structure with self-reference.

1.4 Finite vs Infinite Objects

Distinction between finite and infinite objects, methods of reasoning, and consequences across mathematics.

1.4 Normal Forms

Conjunctive normal form, disjunctive normal form, and systematic conversion of propositional formulas.

1.4 Basic Syntax and Expressions

Lean code is built from expressions.

1.4 Loop Invariants

Loop invariants are the primary tool for reasoning about iterative algorithms.

1.3 Equality, Identity, and Equivalence

Different notions of sameness in mathematics: strict equality, structural identity, and equivalence relations.

1.3 Logical Equivalence

Logical equivalence, truth preserving transformations, and basic laws for rewriting propositional formulas.

1.3 Files, Namespaces, and Modules

Lean organizes code as a hierarchy of modules.

1.3 Correctness Arguments

A correctness argument explains why an algorithm returns an acceptable output for every valid input.

1.2 Sets, Types, and Universes

Three ways to organize a domain of discourse for mathematics: sets, types, and universes — and how they relate.

1.2 Emergence of Number Concepts

How numbers move from concrete counting to abstract ideas.

1.2 Semantics: Truth Tables

Truth values, valuations, and evaluation of propositional formulas using truth tables.

1.2 Project Structure with Lean and Lake

Lean development is organized around projects.

1.2 Input and Output Models

An algorithm does not operate on an abstract idea of data.

1.1 Abstract Objects and Structures

How mathematics treats objects through the rules they satisfy, the relations they support, and the transformations that preserve them.

1.1 Tally Systems and Artifacts

Early counting through marks, objects, and physical recording systems.

1.1 Syntax: Variables, Connectives

Definition of propositional variables, logical connectives, and formation rules for well formed formulas.

1.1 Installation and Toolchain

Lean is distributed as a small toolchain rather than as a single editor plugin.

1.1 Problem Statements

An algorithm begins with a precise statement of the problem.

Chapter 1. Nature of Mathematical Objects

Overview of abstract objects, structures, equality, finiteness, and viewpoints in mathematics.

Chapter 1. Prehistoric and Early Counting

How early humans developed counting, measurement, and basic mathematical thinking before formal notation.

Chapter 1. Propositional Logic

Foundations of propositional logic including syntax, semantics, equivalence, normal forms, and proof systems.

Cheatsheet

Quick reference with live previews for Markdown, shortcodes, and front matter.

gopy objects misc

Port of the remaining cpython/Objects/ files. weakref, memoryview, file, picklebuffer, typevar / TypeAliasType, union, GenericAlias, Interpolation / Template, plus the obmalloc stub.

gopy module and misc

Port of cpython/Objects/moduleobject.c, namespaceobject.c, structseq.c, capsule.c, iterobject.c, and enumobject.c. Module, SimpleNamespace, structseq, Capsule, the generic iterator wrappers, and enumerate / reversed.

gopy code, frame, generator

Port of cpython/Objects/codeobject.c, frameobject.c, genobject.c, and cellobject.c. The four objects the VM thinks in: bytecode, execution frame, generator state machine, and closure cells.

gopy exceptions

Port of cpython/Objects/exceptions.c. The full BaseException hierarchy with the args slot byte-equal to CPython for every constructor.

gopy descriptor and method

Port of cpython/Objects/descrobject.c, methodobject.c, classobject.c, and funcobject.c. The descriptor protocol (data and non-data), bound methods, builtin function objects, and Python function objects.

gopy call

Port of cpython/Objects/call.c. Vectorcall fast path, generic call dispatch, argument tuple construction, and the kwargs handling rules.

gopy abstract

Port of cpython/Objects/abstract.c. Cross-type protocol dispatch (PyObject_*, PyNumber_*, PySequence_*, PyMapping_*, PyIter_*) that the bytecode interpreter calls into.

gopy slice and range

Port of cpython/Objects/sliceobject.c and rangeobject.c. The slice and range builtins, plus the Ellipsis singleton.

gopy set

Port of cpython/Objects/setobject.c. set and frozenset on the same open-addressing layout as dict, sharing the probing sequence.

gopy dict

Port of cpython/Objects/dictobject.c and odictobject.c. Insertion-ordered open-addressing hash table with the CPython probing sequence.

gopy list

Port of cpython/Objects/listobject.c. Mutable variable-length sequence with the CPython list_resize growth curve and Timsort.

gopy tuple

Port of cpython/Objects/tupleobject.c. Immutable sequence with the empty-tuple singleton and the CPython tuple hash.

gopy unicode

Port of cpython/Objects/unicodeobject.c and unicodectype.c. PEP 393 kind-tagged str with the full method surface and Unicode classification tables.

gopy bytes

Port of cpython/Objects/bytesobject.c, bytearrayobject.c, and bytes_methods.c. Immutable bytes plus mutable bytearray with the full string-like method panel.

gopy bool and singletons

Port of cpython/Objects/boolobject.c plus the None and NotImplemented singletons. bool is a subtype of int.

gopy float and complex

Port of cpython/Objects/floatobject.c and complexobject.c. IEEE-754 binary64 float with shortest-roundtrip repr, plus the complex builtin used by cmath.

gopy long

Port of cpython/Objects/longobject.c. Arbitrary-precision int with the small-int cache, base-2/8/10/16 parsing, hash, and the full numeric protocol.

gopy myreadline

Port of cpython/Parser/myreadline.c. Cross-platform readline shim used by the interactive REPL. Mostly a thin wrapper over the host readline library; gopy substitutes Go-native line editing.

gopy type

Type, slots, MRO, lookup. Mirrors PyTypeObject from cpython/Include/cpython/typeobject.h.

gopy object protocol

Object interface, Header, VarHeader, refcount, and identity. Mirrors PyObject and PyVarObject in cpython/Include/object.h.

gopy compile pipeline

AST, future flags, symbol table, codegen, flowgraph, assemble. Ports asdl.c, Python-ast.c, ast.c, ast_preprocess.c, ast_unparse.c, future.c, symtable.c, instruction_sequence.c, codegen.c, flowgraph.c, assemble.c, compile.c.

gopy compile golden tests

Disassembly-golden corpus for the v05test gate. Each fixture is a Go-built AST plus a checked-in .golden file with the expected dis.dis output. Refresh via `go test -update`.

gopy file map

One-line per CPython source file, with the target Go package path and a short purpose note. Canonical lookup table for porters.

gopy codegen

Detailed port plan for cpython/Python/codegen.c (~6500 lines) to compile/codegen.go. Statement and expression visitors, frame block stack, pattern matching panel, with-statement state machine, deferred annotations, PEP 695 type-parameter codegen, comprehensive test plan.

gopy assemble

Detailed port plan for cpython/Python/assemble.c (~800 lines) to compile/assemble.go. Sequence-to-Code conversion, line table varint format, exception table varint format, co_consts/names/varnames/freevars/cellvars layout, fastlocalskinds, comprehensive test plan.

gopy flowgraph

Detailed port plan for cpython/Python/flowgraph.c (~4200 lines) to compile/flowgraph.go. CFG construction, optimization passes (jump threading, dead-code, const fold, swaptimize, super-instructions), stackdepth, exception handler labelling, comprehensive test plan.

Memory Safety in Zig

Dangling Pointers

Efficient Text Processing

Data-Oriented Design

Stack vs Heap

Building Dynamic Strings

Modeling State Machines

Type Reflection Basics

Sentinel-Terminated Arrays

UTF-8 Processing

Union Safety

Type Coercion

Static Dispatch

`@bitCast`

Alignment

Mutable Strings

Tagged Unions

Error Union Internals

Building Generic Data Structures

`@ptrCast`

Allocation Failure Handling

Pointer Arithmetic

String Literals

Enums

`anytype`

Reflection with `@typeInfo`

`@typeInfo`

Custom Allocators

Appendix E. Memory Safety Checklist

Slice Lifetimes

Optional Pointers

Anonymous Structs

Opaque Types

Generating Code at Compile Time

`@Type`

Page Allocator

The Basic Difference

Appendix D. Important Standard Library APIs

Debug Builds

Semantic Analysis

Slices in Detail

Slices

Packed Structs

Vectors

How Parsing Works

Compile-Time Loops

`@alignOf`

Fixed Buffer Allocator

Fuzz Testing

Using C Structs

Why Linked Lists Exist

Appendix C. Common Compiler Errors

Terminal Programming

Build Options

Embedded Development

Why SIMD Matters

WebAssembly

Many Item Pointers

Multidimensional Arrays

Default Field Values

Understanding Stage2

Nullable Pointers

Inline Branching

`@sizeOf`

Table-Driven Tests

Why StringHashMap Exists

Arena Allocator

Calling C Functions

Appendix B. Zig Cheat Sheet

Working with the OS

The Basic Idea

Plugin Architectures

Atomics

Writing Files

macOS Support

Adding Dependencies

Build a Static File Server

Single Item Pointers

Array Literals

Struct Methods