brain
tamnd's digital brain — notes, problems, research
43815 notes
A clear explanation of converting an integer into its base 7 string representation using repeated division.
A clear explanation of finding the next greater element in a circular array using a monotonic stack.
A clear explanation of solving Three Equal Parts by counting ones, locating the three binary patterns, and comparing them in one pass.
A clear explanation of sorting squared values from a sorted array using two pointers.
A clear explanation of solving Largest Component Size by Common Factor using prime factorization and union find.
A clear explanation of the Stone Game problem using game theory and interval dynamic programming.
A clear explanation of counting numbers less than or equal to N using digit-by-digit construction and combinatorics.
A clear explanation of finding the peak index in a mountain array using binary search.
A clear explanation of the Making A Large Island problem using connected component labeling and island size lookup.
A graph traversal solution for finding all nodes that cannot reach a directed cycle.
A clear explanation of validating string transformation using two pointers and movement constraints.
A clear explanation of solving Open the Lock using breadth-first search over lock states.
Find the shortest substring of s1 that contains s2 as a subsequence using dynamic programming.
A clear explanation of finding the largest valid triangle perimeter using sorting and a greedy scan.
A clear explanation of checking whether two binary trees are equivalent after swapping left and right children at any number of nodes.
A clear explanation of solving Flip String to Monotone Increasing with a one-pass dynamic programming approach.
A clear explanation of Online Stock Span using a monotonic decreasing stack with accumulated spans.
A clear explanation of finding the middle node of a singly linked list using slow and fast pointers.
A clear explanation of Loud and Rich using graph traversal, DFS, and memoization.
A clear explanation of the Most Profit Assigning Work problem using sorting, greedy choice, and two pointers.
A dynamic programming solution for finding the minimum number of same-index swaps needed to make two arrays strictly increasing.
A clear explanation of splitting a binary search tree into two BSTs using recursion and pointer rewiring.
A clear explanation of converting a range of IPv4 addresses into the shortest list of CIDR blocks using greedy bit manipulation.
Parse a chemical formula with nested parentheses, atom names, and multipliers using recursive descent.
A clear explanation of inserting a value into a binary search tree using recursive and iterative traversal.
Design a dictionary that can check whether a word can match a stored word after changing exactly one character.
A clear explanation of finding duplicate binary tree subtrees using postorder traversal, serialization, and a hash map.
A SQL guide for counting friendships from both requester and accepter sides, then returning the user with the most friends.
A clear explanation of maximizing capital by selecting at most k projects using sorting and a max heap.
A clear explanation of multiplying complex numbers represented as strings using algebraic expansion.
A clear SQL guide for finding the customer who placed the most orders.
A clear explanation of Array Partition using sorting and adjacent pairing to maximize the sum of pair minimums.
A dynamic programming solution for maximizing the number of A characters printed with a limited number of keyboard operations.
A SQL solution for swapping every pair of adjacent student seats while leaving the final seat unchanged when the row count is odd.
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.
A clear explanation of finding the most frequent value or values in a binary search tree using inorder traversal.
A clear explanation of parsing a parenthesized string recursively to construct a binary tree.
A clear SQL guide for summing 2016 investments for policies with repeated 2015 investment values and unique locations.
A clear explanation of Subarray Sum Equals K using prefix sums and a hash map to count matching subarrays in linear time.
A clear explanation of designing a simple URL encoder and decoder using a hash map and generated keys.
A clear explanation of computing cumulative games played per player and date using SQL window functions.
A clear SQL guide for selecting customers who were not referred by customer 2, including customers with no referee.
A clear explanation of Maximum Depth of N-ary Tree using recursive depth-first search.
A clear dynamic programming solution for finding the minimum deletions needed to make two strings equal.
A clear explanation of merging two quad-trees using recursive logical OR operations.
A clear explanation of counting black lonely pixels using row counts, column counts, and duplicate row patterns.
A clear explanation of Reverse Words in a String III using two-pointer scanning and string reversal.
A clear explanation of counting unique pairs whose absolute difference is k using frequency counting.
A clear graph traversal solution for finding all processes terminated when killing a target process.
A clear linear-time solution for finding the shortest subarray that must be sorted to make the whole array sorted.
A clear explanation of Next Greater Element III using the next permutation algorithm on the digits of an integer.
A clear explanation of counting black pixels that are alone in both their row and column.
A clear explanation of Split Concatenated Strings using string reversal choices and enumeration of every possible cut point.
A clear SQL guide for counting students in every department, including departments with zero students.
A clear explanation of finding the minimum difference between two BST node values using inorder traversal.
A clear SQL guide for computing each employee's 3-month cumulative salary while excluding their most recent month.
A clear explanation of Brick Wall using prefix sums and a hash map to find the best vertical cut position.
A clear explanation of updating a Minesweeper board using DFS flood fill and adjacent mine counting.
A clear explanation of Optimal Division using the structure of division expressions to build the maximum-value expression.
A clear SQL guide for finding the question with the highest answer rate from survey logs.
A clear explanation of weighted random sampling using prefix sums and binary search.
A clear explanation of Student Attendance Record II using dynamic programming over absence count and late streak.
A clear SQL guide for finding employees whose bonus is less than 1000 or missing.
A clear explanation of generating minimal unique word abbreviations using grouping and trie prefixes.
A clear dynamic programming solution for counting paths that move a ball out of a grid boundary.
A clear explanation of Student Attendance Record I using simple string checks and a one-pass counter solution.
A clear explanation of counting beautiful arrangements using backtracking and divisibility pruning.
Arithmetic geometry studies solutions of polynomial equations by combining algebra, geometry, and number theory. Its basic objects are spaces defined by polynomial equations....
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...
The harmonic series is the infinite series
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...
Division of integers does not always produce an integer. For example,
The idea of number arose long before formal mathematics. Early civilizations used numbers for counting objects, measuring land, recording trade, and tracking time.
The integers extend infinitely in both directions:
Many mathematical objects are defined recursively. A recursive definition specifies:
Ordinary induction proves a statement $Pn$ by showing that truth passes from one case to the next:
Many statements in number theory concern all natural numbers. For example, one may wish to prove that
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
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...
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.
The natural numbers are sufficient for counting and addition, but they are not sufficient for subtraction. For example,
The natural numbers arise from the basic act of counting. When we count objects in a collection, we assign successive numbers:
Automatic differentiation works naturally on pure mathematical functions:
Automatic differentiation works naturally on pure mathematical functions:
Automatic differentiation works naturally on pure mathematical functions:
A minimal automatic differentiation engine can compute correct gradients on small programs. A production system must survive long-running workloads, large tensors, distributed...
Automatic differentiation began as a numerical technique for computing gradients of scalar functions.
Sparse and structured differentiation studies how to compute derivatives without materializing dense derivative objects. Many real systems have enormous Jacobians and...
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...
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...
Automatic differentiation can be performed before a program runs, while it runs, or in a staged phase between the two.
This section studies reverse mode automatic differentiation through concrete examples. Each case has the same structure:
Forward mode automatic differentiation computes derivatives by propagating tangent values alongside ordinary values. The ordinary value is called the primal. The derivative...
Differentiation describes how a function changes locally. A Taylor expansion extends this idea by approximating a function with a polynomial around a point.
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...
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...
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...
The preceding sections described automatic differentiation through algebraic, categorical, logical, and denotational models. These viewpoints converge on one central idea:
Automatic differentiation systems are usually trusted because they implement mathematically established rules such as the chain rule, product rule, and linearization of...
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,...