Array & String Memory & Algorithm Concepts
20 in-depth architectural topics from contiguous RAM pointers and 64-byte CPU cache lines to sliding windows and KMP pattern matching.
Contiguous Physical RAM Layout & O(1) Address Arithmetic
An array stores elements in adjacent, unbroken physical memory bytes. Finding any index i takes strictly O(1) time via the pointer arithmetic formula: Address(A[i]) = BaseAddress + i * sizeof(Type).
CPU Cache Lines (64-Byte) & Spatial Locality of Reference
CPUs fetch memory in 64-byte chunks called Cache Lines into ultra-fast L1/L2/L3 caches. Traversing arrays sequentially triggers automatic hardware prefetching, achieving 100x faster execution than random pointer chasing.
Dynamic Array Resizing & Amortized O(1) Complexity
Dynamic arrays (std::vector, ArrayList, Python list, JS Array) automatically double their backing storage capacity (2 -> 4 -> 8 -> 16) when full, reallocating memory and copying elements in amortized O(1) time.
Two-Pointer Technique: Opposite Ends & In-Place Convergence
Two pointers starting at opposite ends (left = 0, right = N - 1) converge toward the center, eliminating nested loops from O(N^2) down to O(N) by exploiting monotonicity in sorted arrays.
Fast and Slow Pointers (Floyd's Cycle Finding Algorithm)
Two pointers moving at different speeds (slow by 1 step, fast by 2 steps) detect cycles and find middle elements in linear O(N) time with O(1) space.
Sliding Window Technique: Fixed vs Dynamic Windows
A sliding window maintains a contiguous subarray [left, right], incrementally adding elements at the right boundary and removing elements at the left boundary in linear O(N) time.
Prefix Sums & O(1) Range Queries
A Prefix Sum array precomputes cumulative totals: P[i] = P[i-1] + arr[i]. Any range sum query sum(L, R) is answered in O(1) time via P[R] - P[L-1].
Kadane's Algorithm: Maximum Subarray Sum in Linear Time
Kadane's algorithm finds the contiguous subarray with maximum sum in O(N) time by making a greedy dynamic programming choice at each element: currMax = max(arr[i], currMax + arr[i]).
Dutch National Flag: In-Place 3-Way Partitioning
Dijkstra's Dutch National Flag algorithm partitions an array into three buckets (e.g. 0s, 1s, 2s or < pivot, == pivot, > pivot) in-place in a single pass with 3 pointers (low, mid, high).
Monotonic Stack: Next Greater Element & Range Minimums
A Monotonic Stack maintains elements in strictly increasing or decreasing order, solving Next Greater Element, Trapping Rain Water, and Largest Rectangle in Histogram in linear O(N) time.
String Memory: UTF-8 vs UTF-16, Code Points & Graphemes
Strings in modern systems use variable-length encodings: UTF-8 (1 to 4 bytes per code point) vs UTF-16 (2 or 4 bytes via surrogate pairs). Indexing by byte length != indexing by visual character glyphs.
Knuth-Morris-Pratt (KMP) String Pattern Matching & LPS Array
KMP eliminates backtracking in naive string matching (O(N * M)) down to linear O(N + M) by precomputing the Longest Prefix Suffix (LPS) table to skip redundant character comparisons.
Rabin-Karp Rolling Hash & Modular String Matching
Rabin-Karp computes a polynomial rolling hash over sliding string windows, enabling O(1) hash updates by shifting the window: Hash_new = ((Hash_old - OutChar * Base^(M-1)) * Base + InChar) % Modulo.
Z-Algorithm: Linear Pattern Matching via Z-Array
The Z-Algorithm constructs a Z-array in O(N) time where Z[i] is the length of the longest substring starting from s[i] that is also a prefix of s, maintaining a rightmost matching window [L, R].
Manacher's Algorithm: Longest Palindromic Substring in O(N)
Manacher's algorithm finds the longest palindromic substring in strictly linear O(N) time by inserting virtual delimiters to unify odd/even lengths and exploiting palindromic symmetry around a center.
Boyer-Moore Search: Bad Character & Good Suffix Rules
Boyer-Moore searches strings by matching pattern characters right-to-left, skipping up to M characters in a single jump to achieve sublinear O(N/M) average search speed (used in GNU grep).
Trie (Prefix Tree) & Autocomplete Dictionaries
A Trie is a multi-way tree structure where each node represents a character. Searching, inserting, and prefix matching ("app", "apple", "apply") executes in O(L) time where L is word length.
Suffix Arrays & Kasai's Longest Common Prefix (LCP)
A Suffix Array contains sorted indices of all string suffixes. Paired with Kasai's LCP array in O(N) time, it enables instantaneous full-text substring search, counting, and repeat detection.
Aho-Corasick Multi-Pattern Dictionary Matching
Aho-Corasick constructs a Finite State Machine combining a Trie with KMP-style failure transitions, finding all occurrences of K dictionary keywords in a text in O(N + M + Z) time.
Lossless String Compression: RLE, Huffman & Burrows-Wheeler
Lossless compression algorithms reduce string storage: Run-Length Encoding (RLE) compresses contiguous repeats, Huffman Coding assigns variable-length prefix codes based on entropy, and BWT groups identical characters together.