Arrays and Strings

ARRAYS & STRINGS DSA · 02 — the contiguous foundation, and the two techniques that turn O(n²) into O(n) an array is a contiguous block of same-size slots. that one fact gives O(1) indexing, cache-friendliness (l.05), and the base every other structure is compared against. two patterns — two-pointer & sliding window — ride on it. 1 · THE ARRAY & THE DYNAMIC ARRAY contiguous slots, same size each. element i lives at base + i × size → O(1) random access by pure arithmetic. 5 2 9 7 1 [0] [1] [2] [3] [4] → arr[3] = base + 3×size. no scan. this is WHY arrays are the most cache-friendly structure (l.05): neighbours are physically adjacent, prefetched. DYNAMIC ARRAY (Python list, Go slice, vector, ArrayList): a static array + capacity that GROWS. 5 2 9 7 full → 2×, copy 5 2 9 7 append is amortized O(1) (rare doubling, l.01). the operation-cost table is the thing to memorise → index / update O(1) just arithmetic append (end) O(1)* amortized; * = occasional O(n) doubling insert / delete mid O(n) must SHIFT everything after it insert / delete front O(n) shift ALL of it search (unsorted) O(n) linear scan search (sorted) O(log n) binary search → 2 · STRINGS = arrays of characters a string is just an array of characters — bytes / code points (l.01: ASCII is 1 byte, UTF-8 is 1-4). h e l l o indexable like any array; but beware: IMMUTABILITY (Python, Java, JS): a string can't be changed in place — every edit makes a NEW string. so building a string by += in a loop is a classic O(n²) TRAP: s = '' s = ''.join(parts) # O(n) for p in parts: s += p # each += copies all of s so far → O(n^2) fix: collect parts in a list and join once, or use a StringBuilder / bytes buffer. other string staples you'll meet: substring search (naive O(nm) vs KMP O(n+m)), anagrams (sort or count), palindromes (two-pointer →), char-frequency maps (hashing, l.03). the mental model: 'string problem' = 'array-of-chars problem' + an encoding agreement. everything below applies. and mutation cost: prefer one pass + a buffer over repeated concatenation. this bites real backend code. 3 · TWO-POINTER — two indices instead of a nested loop (O(n²) → O(n)) OPPOSITE ENDS (converging): two-sum on a SORTED array. target = 14. 1 3 4 6 8 10 L R L+R = 1+10 = 11 < 14 → move L right (need bigger). keep going: 4 + 10 = 14 ✓. each element visited once → O(n), O(1) space. the sorted order tells you WHICH pointer to move — that's the trick. SAME DIRECTION (fast / slow): remove duplicates in place, detect a cycle (Floyd's tortoise & hare), partition an array. one pointer scouts ahead, the other marks the write position. when to reach for it: a sorted array, a palindrome, pairs/triplets summing to a target, in-place compaction. it replaces a nested O(n²) scan with a single O(n) sweep — the highest-leverage array pattern there is. 4 · SLIDING WINDOW & PREFIX SUMS a window [L..R] over the array that GROWS and SHRINKS. answers 'best subarray/substring satisfying X' in O(n) instead of O(n²). example: max sum of a size-3 window over [2,1,5,1,3,2]. 2 1 5 1 3 2 window (sum 8) slide → drop 2, add 1: sum -1 FIXED window (size k): slide by 1, add the new, drop the old — O(1) per step. VARIABLE window: grow R while valid; when it breaks (e.g. a repeat char), shrink L until valid again. classic: longest substring without repeating characters → O(n) with a window + a seen-set. PREFIX SUMS (space for time): precompute cumulative sums once → sum(i..j) = prefix[j+1] - prefix[i] // O(1) per range query turns repeated range-sum queries from O(n) each into O(1) each after an O(n) precompute. two-pointer, sliding window, prefix sums = the three patterns that solve most array problems. know them cold. JARGON, DECODED array = contiguous same-size slots (O(1) index) · dynamic array = auto-growing array (amortized O(1) append, l.01) · capacity vs length = allocated vs used · in-place = O(1) extra space string = array of characters/code points (l.01 encoding) · immutable = can't edit in place (→ += in a loop is O(n²)) · StringBuilder / join = the O(n) fix · KMP = O(n+m) substring search two-pointer = two indices sweeping (converging or fast/slow) → O(n) instead of nested O(n²) · Floyd's cycle detection = fast/slow pointers · sliding window = a growing/shrinking [L..R] range fixed vs variable window = constant size vs condition-driven · prefix sum = cumulative array for O(1) range queries · these three patterns cover the majority of array/string problems