#arrays
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...
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 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...
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...
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...
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...
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...
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: $$...
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...
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 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...
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...
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...
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 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 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...
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:...
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...
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...
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...
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 $$...
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,...
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 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...
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...
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...
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...
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 $$...
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:...
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...
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...
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 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)$...
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,...