#data-structures
CF 2222D - Permutation Construction
CF 2222D - Permutation Construction Rating: - Tags: constructive algorithms, data structures, sortings Solve time: 4m 9s Verified: no Solution Problem Understanding We are given an array $a$ of length $n$. We must construct a permutation $p$ of indices $1$ to $n$. For any pair of positions $i<j$, the pair contributes to the score only if it is an inversion in $p$, meaning $p_i>p_j$. Each such inversion contributes the interval...
CF 241B - Friends
CF 241B - Friends Rating: 2700 Tags: binary search, bitmasks, data structures, math Solve time: 2m 23s Verified: no Solution Problem Understanding We have an array of friend attractiveness values. Every unordered pair of distinct friends produces one possible picture, and the value of that picture is the xor of the two attractiveness values. Among all possible pairs, we want to choose exactly m distinct pairs whose xor values have...
CF 38G - Queue
CF 38G - Queue Rating: 2300 Tags: data structures Solve time: 1m 1s Verified: yes Solution Problem Understanding We are asked to simulate a queue of people where each person has two properties: an importance value a[i] and a patience limit c[i] . People arrive in order, and when the last person (number n ) joins, he can move forward in the queue by swapping with the person directly in...
CF 46E - Comb
CF 46E - Comb Rating: 1900 Tags: data structures, dp Solve time: 1m 52s Verified: yes Solution Problem Understanding Each row of the table contains integers, and from every row we must take a positive-length prefix. If we choose c[i] cells from row i , then the selected cells in that row are exactly the first c[i] entries. The total reward is the sum of all selected numbers. The restriction...
CF 46D - Parking Lot
CF 46D - Parking Lot Rating: 1800 Tags: data structures, implementation Solve time: 1m 54s Verified: yes Solution Problem Understanding We have a parking segment represented by the interval [0, L] . Cars arrive one at a time, always driving from left to right, and each driver wants to park at the earliest possible position. If a car of length x parks with its back at coordinate p , then...
3.5 Concurrent and Lock-Free Structures
3.5 Concurrent and lock-free structures, 35 index slug name 1 concurrent-data-structure Concurrent Data Structure 2 thread-safe-wrapper Thread Safe Wrapper 3 mutex-protected-map Mutex Protected Map 4 read-write-lock-map Read Write Lock Map 5 striped-locking Striped Locking 6 concurrent-queue Concurrent Queue 7 mpsc-queue MPSC Queue 8 spmc-queue SPMC Queue 9 mpmc-queue MPMC Queue 10 bounded-concurrent-queue Bounded Concurrent Queue 11 unbounded-concurrent-queue Unbounded Concurrent Queue 12 lock-free-stack Lock Free Stack 13 lock-free-queue Lock Free Queue...
Static Array
Static Array A static array stores a fixed number of elements in contiguous memory. Each element has the same type and size, so the address of any index can be computed directly. You use it when the number of elements is known in advance and fast indexed access matters. Problem Given an array $A$ of length $n$, support reading or writing an element at index $i$ where $$ 0 \le...
Dynamic Array
Dynamic Array A dynamic array maintains contiguous storage while allowing the number of elements to grow or shrink. When capacity is exhausted, it allocates a larger block and copies existing elements. You use it when the size is not known in advance but fast indexed access and cache locality still matter. Problem Maintain a sequence $A$ that supports: append an element read or write at index $i$ grow automatically when...
Prefix Sum Array
Prefix Sum Array A prefix sum array stores cumulative sums so that any range sum can be computed in constant time. You use it when many range sum queries are performed on static data. Problem Given an array $A$ of length $n$, support queries of the form: $$ \sum_{i=l}^{r} A[i] $$ where $$ 0 \le l \le r < n $$ Structure Define a prefix array $P$ such that: $$...
3.2 Functional Data Structures
3.2 Functional data structures, 35 index slug name 1 functional-data-structure Functional Data Structure 2 persistent-list Persistent List 3 functional-stack Functional Stack 4 functional-queue Functional Queue 5 banker's-queue Bankers Queue 6 real-time-queue Real Time Queue 7 functional-deque Functional Deque 8 finger-tree-functional Finger Tree 9 functional-heap Functional Heap 10 binomial-heap-functional Functional Binomial Heap 11 pairing-heap-functional Functional Pairing Heap 12 skew-binomial-heap Skew Binomial Heap 13 functional-set Functional Set 14 functional-map Functional Map 15...
Sparse Array
Sparse Array A sparse array represents a large logical array by storing only positions whose values differ from a default value. Most entries are implicit. You use it when the index space is large but only a small number of positions contain meaningful data. Problem Given a logical array $A$ of length $n$, support reading and writing index $i$ where: $$ 0 \le i < n $$ Most values are...
Array Merge
Array Merge Array merge combines two sorted arrays into one sorted sequence. It is a fundamental operation in merge sort and external sorting. You use it when two ordered sequences must be combined while preserving order. Problem Given two sorted arrays $A$ and $B$ of lengths $n$ and $m$, produce a sorted array $C$ containing all elements: $$ C = \text{merge}(A, B) $$ Algorithm Use two pointers and repeatedly select...
3.3 Succinct and Compressed Structures
3.3 Succinct and compressed structures, 45 index slug name 1 succinct-data-structure Succinct Structure 2 bit-vector Bit Vector 3 rank-select Rank Select 4 succinct-rank Succinct Rank 5 succinct-select Succinct Select 6 wavelet-tree-succinct Succinct Wavelet Tree 7 wavelet-matrix-succinct Succinct Wavelet Matrix 8 compressed-trie-succinct Succinct Trie 9 compressed-suffix-array Compressed Suffix Array 10 fm-index FM Index 11 burrows-wheeler-transform BWT 12 run-length-encoding RLE 13 delta-encoding Delta Encoding 14 gamma-coding Gamma Coding 15 elias-delta-coding Elias Delta...
Capacity Reservation
Capacity Reservation Capacity reservation allocates enough storage before elements are inserted. It separates allocated capacity from logical size so that append operations can use existing memory. You use it when the approximate final size is known and repeated resizing would waste time. Problem Given a dynamic array $A$, reserve enough capacity for at least $m$ elements while preserving existing elements. The invariant is: $$ size(A) \le capacity(A) $$ After reservation:...
Stable Partition
Stable Partition Stable partition rearranges an array so that elements satisfying a predicate appear before the others, while preserving relative order inside both groups. You use it when grouping is required but original order still carries meaning. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that: all elements satisfying $P$ appear first all elements not satisfying $P$ appear after them relative order...
Padding
Array Padding Array padding inserts unused bytes between elements or groups of elements. It adjusts layout to satisfy alignment constraints or to avoid contention such as false sharing. You use it when memory layout affects performance or correctness in concurrent settings. Problem Given elements of size $s$ and required alignment or spacing $p$, place elements so that consecutive elements are separated by a stride: $$ stride \ge s $$ and...
3.4 Geometric Data Structures
3.4 Geometric data structures, 40 index slug name 1 geometric-data-structure Geometric Data Structure 2 point-set Point Set 3 line-segment-set Line Segment Set 4 interval-tree-geometric Interval Tree 5 segment-tree-geometric Geometric Segment Tree 6 range-tree-geometric Range Tree 7 two-dimensional-range-tree-geometric 2D Range Tree 8 kd-tree KD Tree 9 kd-tree-nearest-neighbor KD Tree Nearest Neighbor 10 ball-tree Ball Tree 11 vp-tree Vantage Point Tree 12 cover-tree Cover Tree 13 quadtree Quadtree 14 octree Octree 15...
3.1 Persistent Data Structures
3.1 Persistent data structures, 45 index slug name 1 persistent-data-structure Persistent Data Structure 2 partial-persistence Partial Persistence 3 full-persistence Full Persistence 4 confluent-persistence Confluent Persistence 5 path-copying Path Copying 6 fat-node Fat Node 7 persistent-array Persistent Array 8 persistent-segment-tree Persistent Segment Tree 9 persistent-fenwick Persistent Fenwick Tree 10 persistent-bst Persistent BST 11 persistent-treap Persistent Treap 12 persistent-heap Persistent Heap 13 persistent-union-find Persistent Union Find 14 persistent-stack Persistent Stack 15 persistent-queue...
3.6 External-Memory and Database Structures
3.6 External-memory and database structures, 35 index slug name 1 external-memory-structure External Memory Structure 2 block-model Block Model 3 buffer-pool Buffer Pool 4 page-cache Page Cache 5 slotted-page Slotted Page 6 heap-file Heap File 7 sorted-file Sorted File 8 clustered-index Clustered Index 9 secondary-index Secondary Index 10 b-tree-index B Tree Index 11 b-plus-tree-index B Plus Tree Index 12 lsm-tree LSM Tree 13 memtable Memtable 14 sstable SSTable 15 bloom-filter-index Bloom...
Tiling
Array Tiling Array tiling divides a multidimensional array into small rectangular regions called tiles. Each tile is processed before moving to the next tile. You use it when matrix or grid operations touch nearby elements repeatedly and cache locality affects performance. Problem Given a matrix $A$ with $r$ rows and $c$ columns, process all elements in tiles of size: $$ t_r \times t_c $$ where $t_r$ is the tile height...
Array Copying
Array Copying Array copying creates another array with the same elements. The copy may duplicate only the element references, or it may recursively duplicate the objects stored inside the array. You use it when a later mutation should not change the original array storage. Problem Given an array $A$ of length $n$, create a new array $B$ such that: $$ B[i] = A[i] $$ for every valid index $i$. Algorithm...
Array Partition
Array Partition Array partition rearranges elements so that all elements satisfying a predicate come before those that do not. The operation runs in-place and does not require additional storage. You use it as a primitive in selection, quicksort, filtering, and grouping tasks. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that: for all indices $i < k$, $P(A[i])$ holds for all indices...
Alignment
Array Alignment Array alignment controls where elements begin in memory. Many processors access aligned values more efficiently because the value fits cleanly inside one memory word, cache line, or vector register. You use it when low-level performance, SIMD instructions, or binary layout compatibility matters. Problem Given an array $A$ whose element type requires alignment $a$, ensure that every element address satisfies: $$ address(A[i]) \bmod a = 0 $$ for every...
Jagged Array
Jagged Array A jagged array stores a collection of rows where each row can have a different length. It is usually represented as an array of arrays. You use it when the data is grouped by row, but each group may contain a different number of elements. Problem Given a jagged array $A$, support reading and writing an element at row $i$ and column $j$ where: $$ 0 \le i...
Vectorization
Array Vectorization Array vectorization processes multiple elements at once using wide CPU instructions. Instead of applying an operation to one value per instruction, the CPU applies it to a vector of values. You use it when arrays are large, element types are uniform, and the same operation applies to many consecutive elements. Problem Given arrays $A$ and $B$ of length $n$, compute an output array $C$ such that: $$ C[i]...
Index Mapping
Array Index Mapping Array index mapping converts a logical index into the physical position where the value is stored. The logical order seen by the algorithm may differ from the storage order used in memory. You use it when arrays are sliced, rotated, circular, strided, blocked, or stored in multidimensional layouts. Problem Given a logical index $i$, compute the physical index $p$ used to access the backing array. For a...
Memory Layout
Array Memory Layout Array memory layout describes how elements are arranged in physical memory. The layout determines how efficiently the CPU can access data due to cache behavior and alignment. You use this knowledge to write code that is fast in practice, not only in asymptotic terms. Problem Given an array $A$ of length $n$, understand how its storage layout affects: access time cache utilization traversal performance Structure A standard...
Multidimensional Array
Multidimensional Array A multidimensional array stores values using two or more indices. Although it is written as a grid, matrix, or tensor, memory is still linear. The indexing formula maps each logical position to one physical offset. You use it when data has natural row, column, plane, or tensor structure. Problem Given a two-dimensional array $A$ with $r$ rows and $c$ columns, support reading and writing an element at position...
3.7 Probabilistic Data Structures
3.7 Probabilistic data structures, 15 index slug name 1 probabilistic-data-structure Probabilistic Data Structure 2 bloom-filter-probabilistic Bloom Filter 3 counting-bloom-filter-probabilistic Counting Bloom Filter 4 cuckoo-filter-probabilistic Cuckoo Filter 5 quotient-filter-probabilistic Quotient Filter 6 xor-filter-probabilistic XOR Filter 7 count-min-sketch Count Min Sketch 8 count-sketch Count Sketch 9 hyperloglog HyperLogLog 10 minhash MinHash 11 reservoir-sampling Reservoir Sampling 12 skip-list Skip List 13 treap-probabilistic Treap 14 randomized-meldable-heap Randomized Meldable Heap 15 probabilistic-invariant-check Probabilistic Invariant Check
Bounds Checking
Array Bounds Checking Array bounds checking verifies that an index lies inside the valid range before reading or writing an array element. It prevents invalid memory access and makes failures explicit. You use it whenever array access may receive an index from input, another computation, or an unsafe source. Problem Given an array $A$ of length $n$ and an index $i$, determine whether: $$ 0 \le i < n $$...
Array Union
Array Union Array union combines elements from two arrays and returns all distinct values. It can also be defined as a multiset union that preserves counts. You use it when merging datasets while eliminating duplicates. Problem Given arrays $A$ and $B$, compute: $$ A \cup B $$ Two common variants: distinct union: each value appears once multiset union: each value appears $\max(count_A, count_B)$ times Algorithm For distinct union, use a...
Amortized Analysis
Amortized Analysis Amortized analysis studies the total cost of a sequence of operations and divides it across the sequence. For dynamic arrays, a single append may be expensive when it triggers resizing, but many appends remain cheap on average. You use it when occasional costly operations are balanced by many cheap operations. Problem Given a dynamic array that doubles capacity when full, show that appending $n$ elements takes total time:...
Blocking
Array Blocking Array blocking divides an array into contiguous chunks and processes one chunk at a time. This can improve cache locality because nearby elements are reused before moving to the next block. You use it when large arrays exceed cache capacity or when work should be processed in batches. Problem Given an array $A$ of length $n$ and a block size $b$, process the array in ranges: $$ [0,...
Circular Array
Circular Array A circular array treats a fixed-size array as if it wraps around. Indices advance modulo the capacity, so the structure forms a logical ring. You use it when you need constant-time insertions and removals at both ends within a bounded buffer. Problem Maintain a sequence $A$ of capacity $n$ that supports: insert at front and back remove from front and back wrap indices without shifting elements Structure A...
Array Buffering
Array Buffering Array buffering uses temporary storage while processing data. The buffer holds intermediate values before they are copied, merged, flushed, or written back. You use it when in-place updates would overwrite values that are still needed. Problem Given an input array $A$, produce an output array $B$ using temporary storage so that reads from $A$ are not corrupted by writes. For many algorithms, the buffer has length: $$ n...
Array Reversal
Array Reversal Array reversal rearranges elements so that the first becomes the last, the second becomes the second last, and so on. You use it as a basic primitive in many algorithms, including rotation, palindrome checks, and two-pointer techniques. Problem Given an array $A$ of length $n$, transform it into: $$ A' = [a_{n-1}, a_{n-2}, \dots, a_0] $$ Algorithm Use two pointers from both ends and swap elements until they...
Array Slicing
Array Slicing Array slicing selects a contiguous subrange from an array. A slice may be a view into the original storage, or it may be a new copied array. You use it when an algorithm should operate on part of an array without manually passing start and end indices everywhere. Problem Given an array $A$ of length $n$, create a slice from index $l$ up to but not including index...
Array Deduplication
Array Deduplication Array deduplication removes repeated values from an array. The usual method keeps a set of values already seen and writes each new value once. You use it when the array may contain repeated elements and downstream work needs only distinct values. Problem Given an array $A$ of length $n$, produce an array containing each distinct value once. For stable deduplication, preserve the first occurrence order. Algorithm Use a...
Sliding Window Array
Sliding Window Array A sliding window tracks a contiguous subarray while moving its boundaries through the array. Instead of recomputing each subarray from scratch, it updates the current state when elements enter or leave the window. You use it when the problem asks about contiguous ranges, especially fixed-size windows or variable-size windows with a constraint. Problem Given an array $A$ of length $n$ and a window size $k$, find the...
Array Compaction
Array Compaction Array compaction removes elements that do not satisfy a predicate by overwriting them with elements that do. It operates in-place and preserves the relative order of retained elements. You use it when filtering data without allocating additional memory. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, remove all elements that do not satisfy $P$, and return the new length. After compaction: for all $i...
Array Rotation
Array Rotation Array rotation shifts all elements by a fixed offset. Elements that move past one end reappear at the other end. You use it when cyclic structure matters, such as scheduling, buffering, or rearranging data without changing relative order. Problem Given an array $A$ of length $n$ and an integer $k$, rotate the array to the right by $k$ steps. Each element moves from index $i$ to: $$ (i...
Stride Access
Array Stride Access Array stride access visits elements with a fixed step between consecutive indices. A stride of $1$ scans every element. Larger strides skip elements and may reduce cache locality. You use it when data is sampled, stored in interleaved form, or traversed by columns in row-major storage. Problem Given an array $A$ of length $n$ and a stride $s$, process indices: $$ 0, s, 2s, 3s, \dots $$...
Array Shuffle
Array Shuffle Array shuffle rearranges elements into a random order such that every permutation is equally likely. You use it when unbiased randomization is required, such as sampling, randomized algorithms, or testing. Problem Given an array $A$ of length $n$, produce a permutation where each of the $n!$ possible orderings occurs with equal probability. Algorithm Use the Fisher–Yates shuffle. Iterate from the end and swap each position with a random...
Array Intersection
Array Intersection Array intersection returns the elements that appear in both input arrays. The result can be defined as a set of distinct values or as a multiset that preserves counts. You use it when you need to find overlap between datasets. Problem Given arrays $A$ and $B$, compute: $$ A \cap B $$ Two common variants: distinct intersection: each value appears once multiset intersection: each value appears $\min(count_A, count_B)$...
Difference Array
Difference Array A difference array stores how each element changes from the previous element. It lets you apply range additions in constant time and reconstruct the final array with a prefix sum. You use it when many range updates are applied before the final values are needed. Problem Given an array $A$ of length $n$, support range updates of the form: $$ A[i] = A[i] + x $$ for every...
Array Scan
Array Scan Array scan processes elements sequentially from left to right (or right to left). It forms the basis of many algorithms, including aggregation, filtering, searching, and transformations. You use it when every element must be inspected at least once. Problem Given an array $A$ of length $n$, compute an aggregate value such as: $$ \sum_{i=0}^{n-1} A[i] $$ or apply a function to each element. Algorithm Sequential scan: scan(A, f,...
Bit-Packed Array
Bit-Packed Array A bit-packed array stores values using a fixed number of bits per element. Instead of allocating a full machine word for each entry, it packs multiple elements into a single word. You use it when values have small ranges and memory footprint matters. Problem Given an array $A$ of length $n$ where each value fits in $b$ bits, support: read element at index $i$ write element at index...