Arrays

An array is a contiguous block of memory that stores elements of the same type at fixed-size offsets. This layout gives arrays a superpower: O(1) random access — any element can be read or written by computing base_address + index × element_size.

Memory Layout and Cache Locality

Because elements sit side by side, the CPU’s memory hierarchy rewards them. When a processor reads arr[0], it loads a full cache line (typically 64 bytes) into L1, and the next several elements arrive for free. Sequential forward scans run near memory-bandwidth speed — which is why “always iterate the array in order” is the cheapest optimization available. Pointer-chasing structures (linked lists, hash chains) pay a cache miss per node and can run 10-100x slower on the same logical work.

Static vs Dynamic Arrays

Static arrays (C int a[10], Rust [T; N]) have a fixed capacity decided at compile time. Dynamic arrays (std::vector, ArrayList, Python list, JS Array) hide a resize strategy: when the backing block is full, allocate a new one (commonly 2x) and copy. Each copy costs O(k), but it happens so rarely that the amortized cost of an append is O(1) — the doubling trick. This is why dynamic arrays, not linked lists, are the default growable container in almost every language.

Key Properties

• Contiguous memory: Elements are stored next to each other, enabling CPU cache prefetching.
• Fixed or dynamic size: Static arrays have a fixed capacity; dynamic arrays grow by allocating a new larger block and copying.
• Indexing: Zero-based in most modern languages.
• Slice/Subarray: O(k) to extract a contiguous range of k elements.

Common Array Patterns

Prefix Sum

The prefix sum technique transforms an array into a cumulative sum array where prefix[i] is the sum of all elements from index 0 to i. This allows computing sum(arr[l..r]) in O(1) time:

prefix[i] = arr[0] + arr[1] + ... + arr[i]
sum(l, r) = prefix[r] - prefix[l - 1]  // O(1) after O(n) preprocessing

Two Pointers and Sliding Windows

Two-pointer problems are the most common array pattern in interviews and in systems code (buffers, dedup, stream windows). The family splits into two shapes:

• Opposite-direction — pointers start at both ends and move inward (sorted two-sum, in-place reversal, palindrome checks).
• Same-direction — a fast pointer reads ahead while a slow pointer lags (remove duplicates, sliding-window max, substring problems).

Both are O(n), and they are not nested loops in disguise: each pointer visits each element once. The sliding-window variant keeps a window [left, right] that expands and contracts while maintaining an invariant. It gets its own studio unit — see Two Pointers & Sliding Window — where the full technique set is covered in depth.

Strings

A string is a sequence of characters. In most modern languages (JavaScript, Python, Java, C#, Swift), strings are immutable — once created, they cannot be modified. Any operation that appears to modify a string actually creates a new one.

String Immutability Implications

• Concatenation in a loop is O(n²): Each + creates a new copy of the entire string.
• Solution: Use a StringBuilder (Java), StringIO (Python), join (Python/JS), or an array of characters.
• Character access: O(1) in languages with indexed string access.

Common String Algorithms

The StringBuilder Pattern

Instead of:

let s = '';
for (let i = 0; i < n; i++) {
  s += arr[i];  // O(n²): new string allocated each iteration
}

Use:

const parts = [];
for (let i = 0; i < n; i++) {
  parts.push(arr[i]);
}
const s = parts.join('');  // O(n): single allocation

Worked Example

Sorted two-sum: given nums = [1, 3, 4, 6, 9, 12], find two numbers that sum to 10. Two pointers start at the ends and move inward — at most n steps total:

l=0 r=5  1+12 = 13 > 10 → r--    (too big: shrink from the right)
l=0 r=4  1+9  = 10  → found (1, 9) at indices 0 and 4

The prefix-sum trick is the same idea applied to ranges: with prefix = [1, 4, 8, 14, 23, 35], a range query becomes one subtraction — sum(2..4) = prefix[4] - prefix[1] = 23 - 4 = 19, which equals 4 + 6 + 9 without looping.

Arrays vs Linked Lists

Practice Trajectory

1. Implement in-place reversal and sorted two-sum, both with opposite-direction pointers.
2. Rewrite a nested-loop brute force as a sliding window and verify the runtime drops from O(n²) to O(n).
3. Build a prefix-sum array and answer 100 random range-sum queries against a brute-force oracle.
4. Implement the dynamic-array grow loop by hand and count element copies to confirm the O(1) amortized append.
5. Solve a palindrome and an anagram check with frequency maps, then restate both as two-pointer problems.

When It’s the Right Tool