LeetCode
LeetCode practice notes exported from ChatGPT lessons.
Tag
Algorithms
538 notes
LeetCode 09xx
LeetCode practice notes for problems 900 through 999, including A clear explanation of designing an iterator over a run-length encoded sequence without expanding it.
LeetCode 08xx
LeetCode practice notes for problems 800 through 899, including A clear explanation of finding the closest shorthand RGB color by rounding each color channel to the nearest repeated hexadecimal pair.
LeetCode 10xx
LeetCode practice notes for problems 1000 through 1000, including A clear explanation of merging consecutive stone piles with minimum cost using interval dynamic programming.
LeetCode 07xx
LeetCode practice notes for problems 700 through 799, including Search for a target value in a binary search tree and return the subtree rooted at the matching node.
LeetCode 00xx
LeetCode practice notes for problems 1 through 99, including A clear explanation of the Two Sum problem using brute force first, then an optimized hash map solution.
LeetCode 02xx
LeetCode practice notes for problems 200 through 299, including A clear explanation of counting connected groups of land cells in a grid using DFS or BFS.
LeetCode 01xx
LeetCode practice notes for problems 100 through 199, including A detailed guide to solving Same Tree with recursive DFS and structural comparison.
LeetCode 06xx
LeetCode practice notes for problems 600 through 699, including A clear digit dynamic programming solution for counting numbers whose binary representation does not contain consecutive ones.
LeetCode 05xx
LeetCode practice notes for problems 500 through 599, including A clear explanation of filtering words that can be typed using only one row of an American keyboard.
LeetCode 04xx
LeetCode practice notes for problems 400 through 499, including A clear explanation of finding the nth digit in the infinite integer sequence using digit groups and arithmetic.
LeetCode 03xx
LeetCode practice notes for problems 300 through 399, including A dynamic programming and patience sorting solution for finding the longest strictly increasing subsequence in an array.
Practice
Programming practice notes and algorithm problem explanations.
Algorithm Cookbook
A practical cookbook of algorithmic patterns, correctness arguments, and implementation techniques.
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.
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.
3.7 Probabilistic Data Structures
Bloom filters, cuckoo filters, count-min sketch, HyperLogLog, MinHash, reservoir sampling, skip lists, and treaps as probabilistic structures.
2.7 Order Statistic Structures
Balanced trees augmented with subtree sizes, implicit treaps, wavelet-based order statistics, skip lists, median maintenance, and rank-select structures.
3.6 External-Memory and Database Structures
B-tree indexes, LSM trees, SSTables, write-ahead logs, compaction strategies, cache-oblivious structures, inverted indexes, and external sort/merge.
2.6 Tries and Prefix Structures
Trie variants including compressed, Patricia, ternary, XOR, suffix trees, Aho-Corasick, DAWG, HAMT, and concurrent prefix structures.
3.5 Concurrent and Lock-Free Structures
Mutex-protected structures, lock-free stacks, queues, hash tables, skip lists, CAS primitives, hazard pointers, epoch reclamation, and RCU.
2.5 Disjoint Set Union Variants
Union-find with path compression and union by rank, rollback, parity, weighted, offline, and concurrent DSU designs.
3.4 Geometric Data Structures
KD-trees, R-trees, quadtrees, octrees, Delaunay triangulation, Voronoi diagrams, HNSW, range trees, and sweep line structures.
1.4 Queues and Deques
Array and linked queues, deques, monotonic queues, priority buckets, delay queues, and concurrent queue designs.
3.3 Succinct and Compressed Structures
Bit vectors, rank-select, succinct trees, FM-index, wavelet trees, Huffman and arithmetic coding, roaring bitmaps, and compressed range queries.
3. Specialized, Persistent, Concurrent, and External Structures
Persistence, functional structures, succinct and compressed encodings, geometric indexing, concurrent and lock-free designs, external-memory structures, and probabilistic data structures.
1.3 Stacks
Array and linked stack implementations covering push, pop, monotonic stacks, expression evaluation, and thread-safe variants.
3.2 Functional Data Structures
Immutable lists, stacks, queues, heaps, HAMTs, functional BSTs, lazy evaluation, structural sharing, and deforestation.
2. Advanced Data Structures and Operations
Augmented and self-balancing trees, range query structures, Fenwick and segment tree variants, union-find, tries, and order statistic structures.
1.2 Linked Lists
Singly, doubly, and circular linked lists with operations for insertion, reversal, cycle detection, sorting, and memory pooling.
02. Data Structures
Three-book reference covering core, advanced, and specialized data structures from arrays to concurrent and persistent designs.
3.1 Persistent Data Structures
Path copying, fat nodes, persistent arrays, segment trees, treaps, heaps, union-find, functional queues, and distributed persistence models.
1.1 Arrays and Dynamic Arrays
Fixed and dynamic arrays, resizing strategies, memory layout, cache effects, vectorization, and in-place operations.
1. Core Data Structures and Operations
Memory layout, invariants, and implementation details for arrays, linked lists, stacks, queues, heaps, hash tables, binary search trees, and traversal operations.
1.8 Basic Tree Traversals and Operations
General tree traversal patterns including DFS, BFS, level-order, zigzag, boundary traversal, LCA, serialization, and iterative approaches.
1.7 Binary Search Trees
BST operations, traversals, augmentation, interval trees, order statistics, persistence, and thread-safe BST designs.
1.6 Hash Tables and Sets
Hash functions, collision resolution strategies, open addressing, chaining, dynamic resizing, perfect hashing, concurrent maps, and probabilistic filters.
1.5 Heaps and Priority Queues
Binary, d-ary, Fibonacci, pairing, soft heaps, double-ended structures, tournament trees, and concurrent priority queue designs.
2.4 Segment Tree Variants
Segment tree construction, lazy propagation, beats, 2D variants, persistent and dynamic trees, and hybrid structures combining multiple techniques.
2.3 Fenwick Tree Variants
Fenwick tree construction, point and range updates, multidimensional extensions, order statistics, inversion counting, and persistent variants.
2.2 Range Query Structures
Sparse tables, sqrt decomposition, Mo's algorithm, wavelet trees, merge sort trees, 2D range trees, and offline range query techniques.
2.1 Balanced Search Trees
AVL, red-black, splay, scapegoat, B-tree families, treaps, finger trees, persistent balanced trees, and cache-oblivious layouts.
12. Specialized Search and Sorted-Order Procedures
Cache-efficient and hardware-tuned search: branchless binary search, Eytzinger and vEB layouts, learned indexes, SIMD search, and galloping intersection.
11. Parallel, Distributed, and GPU Sorting
High-throughput sorting: parallel merge and quicksort, GPU bitonic and radix sort, SIMD sorting networks, and distributed partition-based sorts.
10. External Memory, Cache, and Database Sorting
Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.
9. Partial, Online, and Adaptive Sorting
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
8. Integer and Distribution Sorting
Non-comparison sorts: counting, radix, and bucket sort families, string sorting, and suffix array construction.
7. Divide and Conquer Sorting
Divide-and-conquer sorts: merge sort variants, quicksort family, heapsort, and comparison-based sorting networks.
6. Elementary Sorting
Elementary comparison-based sorts: bubble, selection, insertion, Shell, comb, cycle, and curiosity sorts.
5. Selection and Order Statistics
Selection and order-statistics: quickselect, median-of-medians, streaming top-k, heavy hitters, reservoir sampling, and quantile summaries.
4. Tree and Indexed Search
Tree-based and indexed search: BST, self-balancing trees, tries, suffix structures, segment and range trees, and spatial trees.
3. Hashing and Table Search
Hash table lookup strategies, open-addressing and chaining variants, probabilistic filters (Bloom, Cuckoo, XOR), and locality-sensitive similarity search.
2. Binary Search and Ordered Search
Binary search and its ordered-search relatives: interpolation, Fibonacci, rotated-array, matrix, parametric, and offline variants.
1. Linear and Sequential Search
Linear and sequential scan techniques including sentinel, bounded, recursive variants, duplicate detection, and majority vote.
01. Searching and Sorting
Searching and sorting techniques spanning sequential and parallel algorithms, from linear scan to GPU-based distribution sort.
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.
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.
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.
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.
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.
11.2 Computation Traces
Step-by-step evolution of Turing machine configurations and how computations are represented as traces.
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.
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 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 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 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 Selection Sort
Sort by repeatedly selecting the minimum element from the unsorted suffix and placing it into the next output position.
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.
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 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 Load Factor and Resizing
Control hash table performance by monitoring the load factor and growing the bucket array before collisions accumulate.
5.3 Collision Handling
Resolve hash collisions using separate chaining or open addressing, with trade-offs in memory, locality, and load tolerance.
5.2 Hash Functions
Design and evaluate hash functions that distribute keys uniformly across buckets while remaining fast to compute.
5.1 Hash Tables
A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.
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 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 Reversal
Reversal transforms a linked list so that the direction of all edges is flipped.
3.3 Sentinel Nodes
A sentinel node is an artificial node placed at the boundary of a linked list.
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 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. Linked Lists and Pointers
Linked lists are the first data structure in this book where the shape of the data matters as much as the values stored inside it.
2.25 Boundary Conditions
Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.
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 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 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 Matrix Traversal
Matrix traversal processes a two-dimensional array in a defined order.
2.20 Tries
A trie is a tree structure for storing a set of strings so that common prefixes are shared.
2.19 Parsing Expressions
Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.
2.18 String Comparison
String comparison determines the ordering or equality of two strings.
2.17 Rolling Hashes
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
2.16 Run-Length Encoding
Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.
2.15 Frequency Tables
A frequency table records how many times each value appears in an array, string, or stream.
2.14 Anagrams
Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.
2.13 Palindromes
A palindrome is a sequence that reads the same forward and backward.
2.12 Substring Search
Substring search locates occurrences of a pattern `p` inside a text `s`.
2.11 Tokenization
Tokenization converts a string into a sequence of meaningful units called tokens.
2.10 String Scanning
String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.
2.9 Deduplication
Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.
2.8 In-Place Modification
In-place modification changes an array without allocating another array of the same size.
2.7 Rotation
Array rotation moves elements by a fixed offset while preserving their relative circular order.
2.6 Partitioning
Partitioning rearranges an array so that elements are grouped by a predicate.
2.5 Sliding Windows
Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.
2.4 Two Pointers
The two pointers technique uses two indices that move through an array or string in a controlled way.
2.3 Difference Arrays
A difference array is the inverse pattern of a prefix sum.
2.2 Prefix Sums
Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.
2.1 Array Traversal
Array traversal is the base operation for all algorithms over linear data.
Chapter 2. Arrays and Strings
This chapter studies linear data as the primary substrate for algorithm design.
1.25 Common Failure Modes
Even when the algorithmic idea is correct, implementations fail in predictable ways.
1.24 Benchmarking
Benchmarking measures how an implementation behaves on real inputs and real hardware.
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 Numerical Limits
Algorithms are usually described with mathematical integers and real numbers.
1.21 Data Representation
Data representation is the choice of concrete form used to store the objects in a problem.
1.20 Implementation Discipline
Implementation discipline means translating an algorithm into code without changing its meaning accidentally.
1.19 Pseudocode Style
Pseudocode is a bridge between the problem statement and an implementation.
1.18 Reductions
A reduction transforms one problem into another problem.
1.17 Amortized Analysis
Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive.
1.16 Randomization
Randomized algorithms use random choices during execution.
1.15 Dynamic Programming
Dynamic programming solves problems by storing answers to subproblems and reusing them.
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 Greedy Choices
A greedy algorithm builds a solution by making one locally best choice at a time.
1.12 Brute Force Baselines
A brute force baseline is the simplest correct algorithm you can write from the problem statement.
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 Edge Cases
Edge cases are valid inputs that sit at the boundary of the specification.
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 Big O Notation
Big O notation provides a formal way to describe how a function grows.
1.7 Space Complexity
Space complexity measures how much memory an algorithm uses as a function of input size.
1.6 Time Complexity
Time complexity describes how the running time of an algorithm grows as the input size grows.
1.5 Recursion Invariants
Recursive algorithms replace loop structure with self-reference.
1.4 Loop Invariants
Loop invariants are the primary tool for reasoning about iterative algorithms.
1.3 Correctness Arguments
A correctness argument explains why an algorithm returns an acceptable output for every valid input.
1.2 Input and Output Models
An algorithm does not operate on an abstract idea of data.
1.1 Problem Statements
An algorithm begins with a precise statement of the problem.
Chapter 1. Foundations
This chapter defines how you think about algorithms before you write any code.
68. Computer Science
This volume studies theoretical and practical foundations of computation.
Chapter 6. Sorting
Sorting algorithms from fundamental contracts through comparison-based, linear-time, and specialized variants, with selection, external sorting, and correctness analysis.
Chapter 5. Hashing and Maps
Hash tables, hash functions, collision handling, probabilistic structures, and practical design for constant-time key-value access.