brain

A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.

Rebuild a hash table's bucket array after resizing so that every stored key satisfies the placement invariant for the new capacity.

Design and evaluate hash functions that distribute keys uniformly across buckets while remaining fast to compute.

Equality becomes useful when it propagates through larger expressions.

Rewriting becomes more subtle when the target term appears inside a binder.

In most proofs, equalities come from the local context.

The behavior of `simp` depends entirely on the set of rewrite rules it uses.

Propositional equality in Lean is generated from a small set of core operations.

Propositional equality is the explicit notion of equality in Lean.

When types depend on values, rewriting affects both terms and their types.

Complex equalities are rarely achieved in a single step.

The tactic `simp` performs normalization by repeated rewriting using a curated set of lemmas.

Rewriting is the primary way to apply propositional equalities in Lean.

Equality between functions requires a different treatment than equality between values.

Case analysis splits a goal according to the structure of a value.

Rewriting systems can diverge if rules are poorly oriented or interact cyclically.

Structures package multiple fields into a single value.

Lemmas provide reusable equalities that drive most rewriting.

Equalities are often too strict.

Substitution is the direct elimination of equalities from the context.

Definitional equality is the built-in notion of equality used by the kernel of Lean.

Rewriting failures in Lean usually come from a small set of recurring issues.

Rewriting can target either the goal or the local context.

The `conv` tactic provides fine-grained control over rewriting.

In Lean, propositions live in `Prop`, a universe where proof irrelevance holds.

Rewriting is most effective when guided by a small set of consistent strategies.

Pattern matching performs case analysis by selecting a branch based on the shape of a value.

Reasoning often alternates between propositional equality `a = b` and boolean equality `a == b`.

Even when the algorithmic idea is correct, implementations fail in predictable ways.

Implementation discipline means translating an algorithm into code without changing its meaning accidentally.

Benchmarking measures how an implementation behaves on real inputs and real hardware.

Data representation is the choice of concrete form used to store the objects in a problem.

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers.

Algorithms are usually described with mathematical integers and real numbers.

Dynamic programming solves problems by storing answers to subproblems and reusing them.

A reduction transforms one problem into another problem.

Randomized algorithms use random choices during execution.

Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive.

Pseudocode is a bridge between the problem statement and an implementation.

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details.

A greedy algorithm builds a solution by making one locally best choice at a time.

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers.

A brute force baseline is the simplest correct algorithm you can write from the problem statement.

Edge cases are valid inputs that sit at the boundary of the specification.

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation.

Space complexity measures how much memory an algorithm uses as a function of input size.

Big O notation provides a formal way to describe how a function grows.

Time complexity describes how the running time of an algorithm grows as the input size grows.

Recursive algorithms replace loop structure with self-reference.

An algorithm does not operate on an abstract idea of data.

Loop invariants are the primary tool for reasoning about iterative algorithms.

A correctness argument explains why an algorithm returns an acceptable output for every valid input.

An algorithm begins with a precise statement of the problem.

This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.

Linked list algorithms are dominated by pointer traversal and constant-time link updates.

A skip list augments a sorted linked list with multiple levels of forward pointers.

Pointer code should be tested by checking structure, not only values.

Edge cases are inputs that sit near the boundary of an algorithm's assumptions.

A dummy head is a fixed node placed before the real head of a singly linked list.

A queue is a first-in, first-out structure.

An intrusive list stores the linkage fields inside the objects being linked.

Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.

A stack is a last-in, first-out (LIFO) structure.

Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.

An iterator is an object or procedure that visits the nodes of a linked list one at a time.

A persistent list is a list that preserves older versions after an update.

An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.

Pointer aliasing occurs when two or more references point to the same node.

Deletion removes one or more nodes from a linked list by changing links around them.

Reversal transforms a linked list so that the direction of all edges is flipped.

A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.

Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.

A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.

Fast and slow pointers are two references that traverse the same linked structure at different speeds.

Merging combines two sorted singly linked lists into one sorted list by relinking nodes.

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.

A sentinel node is an artificial node placed at the boundary of a linked list.

Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.

Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.

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.

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,...

Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.

Matrix traversal processes a two-dimensional array in a defined order.

Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.

A trie is a tree structure for storing a set of strings so that common prefixes are shared.

Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.

String comparison determines the ordering or equality of two strings.

A palindrome is a sequence that reads the same forward and backward.

Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.

Substring search locates occurrences of a pattern `p` inside a text `s`.

Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.

A frequency table records how many times each value appears in an array, string, or stream.

Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.

Partitioning rearranges an array so that elements are grouped by a predicate.

In-place modification changes an array without allocating another array of the same size.

String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.

Array rotation moves elements by a fixed offset while preserving their relative circular order.

Tokenization converts a string into a sequence of meaningful units called tokens.

The two pointers technique uses two indices that move through an array or string in a controlled way.

Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.