Arrays & Strings

Size is how many elements are stored; capacity is how many slots the underlying block can hold. Appending when size equals capacity forces allocating a larger block, copying every stored element into it, and releasing the old one.

In-place compaction never shrinks the array, so survivors occupy only a prefix and stale values still sit in the tail. The returned write count is the only signal of how many entries are valid.

Each swap places two elements at once, so n/2 swaps fix all n positions. Looping over every index instead swaps each pair twice, which undoes the reversal and hands back the original array.

A flat row-major buffer stores each row as width consecutive slots, so the cell at column x, row y lives at ywidth+x. Writing xwidth+y addresses the transposed cell: harmless-looking on square images, corrupting or overrunning everything else.

Transposing mirrors the grid across its main diagonal, which puts every element in its correct destination row but with the columns running backwards. Reversing each row fixes that order. Two mirrors at 45 degrees to each other compose into one quarter turn.

Each concatenation on an immutable string allocates a brand-new string and copies every character accumulated so far. Copying 1 + 2 + ... + n characters sums to about n^2/2, so the loop is quadratic, not linear.

UTF-8 is variable-width: one code point takes one to four bytes. Unaccented Latin letters cost one byte, accented letters two, most emoji four. So ten characters can weigh anywhere from ten to forty bytes.

Immutable means an existing string's characters never change: operations that look like edits return a new string. Because the value cannot change under anyone holding it, it can be shared without defensive copies, hashed once, and read concurrently.

Memory moves in fixed-size blocks, so one fetch of a contiguous array delivers many neighbouring readings at once and the hardware can run ahead and fetch the next block early. Scattered references pay a separate, unpredictable trip per value.

An array stores equal-size elements contiguously, so the address of element i is base + i × element-size. That is one multiply and one add no matter how large i is, so element 5,000,000 costs the same as element 3.

An index names a position, so the array reaches that element in one step without examining anything else. A stored field names no position, so an unsorted array must examine elements one by one — up to n of them.

Naive search retries the pattern at every offset, so each of the roughly n offsets can cost up to m comparisons. On ordinary text most offsets mismatch within a symbol or two, so the scan behaves near-linearly.

Walking one index from each end inward compares mirrored characters directly, uses O(1) extra space, and can stop at the first mismatch. Reversing first is also O(n) time but allocates a whole second copy of the input.

A fixed chunk means one reallocation every 4096 appends, and each of those copies the entire prefix stored so far. Total copy work therefore grows with n squared. A bigger chunk lowers the constant but never changes the quadratic order.

The write index advances only on a keep while the read index advances every step, so write never overtakes read. Every slot written was therefore already read, and the region below write holds exactly the survivors so far, in order.

Reverse the whole array, then its first k elements and its last n-k. The full reverse brings the last k entries to the front but backwards; the two partial reverses repair each block's order, using no extra array.

Code points beyond the Basic Multilingual Plane are stored as two UTF-16 code units, a surrogate pair. Cutting between them leaves an unpaired surrogate, which is not a valid character and renders or serializes as a replacement symbol.

Identity comparison asks whether two references point at one object; content comparison asks whether the characters match. Equal contents can live in two separately allocated strings, so identity is false while content is true. Compare contents unless every value was canonicalized.

The address formula base + i × element-size works for any i, valid or not; index equal to the length lands one element past the array, on whatever is stored next. Unchecked runtimes just write there; checked runtimes compare the index against the stored length first and raise an error.

An array's slots are fixed positions, so making room at index 0 means moving every existing element one slot right — n moves. Appending writes into the first free slot and moves nothing, so it costs one write.

KMP never moves its text pointer backward. On a mismatch it shrinks the matched pattern length using the precomputed table instead of restarting the text one position later, so the scan costs O(n) after an O(m) table build.

A rolling hash derives the next window's hash from the current one in constant time: drop the leading symbol's weighted term, shift the rest, add the trailing symbol. Hashing each window from scratch would cost O(m) per position.

Sorting both inputs and comparing produces a canonical form in O(L log L); tallying character frequencies produces one in O(L). Counting wins asymptotically, but only if the tally covers the real alphabet rather than a fixed table of 26 lowercase letters.

For each prefix of the pattern, the failure function stores the length of the longest proper prefix of that prefix which is also a suffix of it. It is derived from the pattern alone and says nothing about the text.

An append past capacity allocates a larger block, copies the elements over and releases the old one. A reference captured into the old block then names freed storage. Indices survive the move; handles into the buffer do not.

The high-side swap pulls a value out of the still-unexamined region and drops it under the scan index. That value has not been classified yet, so the scan index must stay and inspect it next iteration.

Both loops touch the same number of cells, but row-major storage puts a row's cells next to each other. A row-order scan walks memory one slot at a time; a column-order scan jumps a full row width per step, so each access lands in a different region.

Nothing changes. Each off-diagonal pair gets swapped twice, once as (i, j) and again as (j, i), so the second swap undoes the first, and diagonal swaps are no-ops. The inner loop must start at j = i + 1.

A lap can exhaust the region halfway through. Once the top row and right column are consumed, what remains may be a single row or column, and without rechecking the bounds the return passes walk it twice.