Static Array
Store a fixed number of elements in contiguous memory with constant-time indexing.
Tag
Arrays
67 notes
Array Alignment
Place array elements at memory addresses that satisfy hardware and type alignment requirements.
Array Bounds Checking
Validate array indices before access to prevent invalid reads and writes.
Array Union
Combine elements from two arrays into one collection without duplicates.
Array Intersection
Compute the common elements between two arrays.
Difference Array
Represent range updates compactly by storing changes between adjacent values.
Prefix Sum Array
Precompute cumulative sums to answer range sum queries in constant time.
Array Padding
Insert unused space between array elements or groups to control alignment and reduce interference.
Array Vectorization
Process multiple array elements per instruction using SIMD-friendly layout and loops.
Array Tiling
Process multidimensional arrays in small rectangular regions to improve locality.
Array Blocking
Process an array in fixed-size blocks to improve cache locality and batch behavior.
Array Stride Access
Access array elements at regular intervals and understand the effect on locality.
Array Index Mapping
Map logical array positions to physical storage positions.
Array Buffering
Use temporary array storage to stage data before writing it to its final location.
Array Copying
Copy array elements into a new storage block using shallow or deep copy semantics.
Array Memory Layout
Understand how arrays are stored in memory and how layout affects performance.
Array Merge
Merge two sorted arrays into a single sorted array.
Array Deduplication
Remove duplicate values from an array while keeping one representative of each value.
Array Compaction
Remove elements in-place based on a predicate while preserving the remaining elements.
Array Scan
Traverse an array sequentially to compute an aggregate or apply a function.
Array Shuffle
Generate a uniform random permutation of an array in-place.
Array Reversal
Reverse the order of elements in an array in-place using symmetric swaps.
Stable Partition
Partition an array while preserving the relative order of elements inside each group.
Array Partition
Rearrange elements so that those satisfying a predicate appear before others.
Amortized Analysis
Analyze the average cost per operation over a sequence of dynamic array operations.
Capacity Reservation
Preallocate array capacity to reduce reallocations and copying during growth.
Bit-Packed Array
Store small integers or booleans using compact bit-level representation.
Sparse Array
Store only non-default values from a large logical array.
Sliding Window Array
Maintain a contiguous window over an array while moving its left and right boundaries.
Array Rotation
Rotate elements of an array by a given offset in-place or using auxiliary space.
Array Slicing
Represent a contiguous subrange of an array as either a view or a copied array.
Jagged Array
Store rows of different lengths as an array of arrays.
1.1 Arrays and Dynamic Arrays
Fixed and dynamic arrays, resizing strategies, memory layout, cache effects, vectorization, and in-place operations.
Multidimensional Array
Store values indexed by two or more dimensions using a linear memory layout.
Circular Array
Array that wraps indices modulo capacity to support efficient cyclic access.
Dynamic Array
Resizable array that grows and shrinks automatically while preserving contiguous storage.
Insertion Sort
Build a sorted sequence by inserting each element into its correct position.
Selection Sort
Repeatedly select the minimum element from the unsorted portion and place it at the beginning.
Bubble Sort
Repeatedly swap adjacent elements that are out of order until the sequence becomes sorted.
Binary Search
Search a sorted array by repeatedly halving the search interval.
Linear Search
Scan a sequence from left to right until the target value is found or the sequence ends.
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.