Static Array
Store a fixed number of elements in contiguous memory with constant-time indexing.
67 notes
Store a fixed number of elements in contiguous memory with constant-time indexing.
Place array elements at memory addresses that satisfy hardware and type alignment requirements.
Validate array indices before access to prevent invalid reads and writes.
Combine elements from two arrays into one collection without duplicates.
Compute the common elements between two arrays.
Represent range updates compactly by storing changes between adjacent values.
Precompute cumulative sums to answer range sum queries in constant time.
Insert unused space between array elements or groups to control alignment and reduce interference.
Process multiple array elements per instruction using SIMD-friendly layout and loops.
Process multidimensional arrays in small rectangular regions to improve locality.
Process an array in fixed-size blocks to improve cache locality and batch behavior.
Access array elements at regular intervals and understand the effect on locality.
Map logical array positions to physical storage positions.
Use temporary array storage to stage data before writing it to its final location.
Copy array elements into a new storage block using shallow or deep copy semantics.
Understand how arrays are stored in memory and how layout affects performance.
Merge two sorted arrays into a single sorted array.
Remove duplicate values from an array while keeping one representative of each value.
Remove elements in-place based on a predicate while preserving the remaining elements.
Traverse an array sequentially to compute an aggregate or apply a function.
Generate a uniform random permutation of an array in-place.
Reverse the order of elements in an array in-place using symmetric swaps.
Partition an array while preserving the relative order of elements inside each group.
Rearrange elements so that those satisfying a predicate appear before others.
Analyze the average cost per operation over a sequence of dynamic array operations.
Preallocate array capacity to reduce reallocations and copying during growth.
Store small integers or booleans using compact bit-level representation.
Store only non-default values from a large logical array.
Maintain a contiguous window over an array while moving its left and right boundaries.
Rotate elements of an array by a given offset in-place or using auxiliary space.
Represent a contiguous subrange of an array as either a view or a copied array.
Store rows of different lengths as an array of arrays.
Fixed and dynamic arrays, resizing strategies, memory layout, cache effects, vectorization, and in-place operations.
Store values indexed by two or more dimensions using a linear memory layout.
Array that wraps indices modulo capacity to support efficient cyclic access.
Resizable array that grows and shrinks automatically while preserving contiguous storage.
Build a sorted sequence by inserting each element into its correct position.
Repeatedly select the minimum element from the unsorted portion and place it at the beginning.
Repeatedly swap adjacent elements that are out of order until the sequence becomes sorted.
Search a sorted array by repeatedly halving the search interval.
Scan a sequence from left to right until the target value is found or the sequence ends.
Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.
Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.
Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region.
Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column,...
Matrix traversal processes a two-dimensional array in a defined order.
A trie is a tree structure for storing a set of strings so that common prefixes are shared.
Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.
String comparison determines the ordering or equality of two strings.
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.
A frequency table records how many times each value appears in an array, string, or stream.
Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.
A palindrome is a sequence that reads the same forward and backward.
Substring search locates occurrences of a pattern `p` inside a text `s`.
Tokenization converts a string into a sequence of meaningful units called tokens.
String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.
Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.
In-place modification changes an array without allocating another array of the same size.
Array rotation moves elements by a fixed offset while preserving their relative circular order.
Partitioning rearranges an array so that elements are grouped by a predicate.
Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.
The two pointers technique uses two indices that move through an array or string in a controlled way.
A difference array is the inverse pattern of a prefix sum.
Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.
Array traversal is the base operation for all algorithms over linear data.
This chapter studies linear data as the primary substrate for algorithm design.