Arrays and Strings¶

Arrays are the most fundamental data structure in computing — not because they’re the most powerful, but because everything else is built on top of or in contrast to them. You already use arrays constantly. The goal here is to understand them at the level where you can predict when they’ll be fast, when they’ll hurt you, and what algorithmic patterns they naturally support.

1. Static Arrays¶

A static array is a contiguous block of memory holding elements of the same type. “Contiguous” is the operative word — elements are stored back-to-back with no gaps.

Index:   0    1    2    3    4
Value: [ 10 | 20 | 30 | 40 | 50 ]
Addr:  1000 1004 1008 1012 1016   (assuming 4-byte int)

Access — O(1): Given index i, the address is base_addr + i * element_size. One arithmetic operation. This is why random access is O(1) — it’s a formula, not a search.

Insertion/Deletion — O(n): Inserting at index k requires shifting elements k..n-1 one position right. In the worst case (inserting at index 0), you shift all n elements. Deletion is symmetric.

Fixed size: Once allocated, you can’t grow a static array. You need to allocate a new, larger block and copy everything — O(n).

2. Dynamic Arrays (ArrayList / std::vector)¶

A dynamic array wraps a static array and handles resizing automatically. The key design decision is the doubling strategy: when the internal array fills up, allocate a new array of 2× the capacity and copy everything.

Why double and not add a fixed amount?¶

If you add +10 slots each time and you’re inserting n elements:

You resize at 10, 20, 30, … — about n/10 resizes
Each resize copies 10, 20, 30, … elements
Total copy work: 10 + 20 + … + n ≈ n²/20 = O(n²) for n insertions

If you double instead:

You resize at 1, 2, 4, 8, …, n — about log₂(n) resizes
Each resize copies 1, 2, 4, …, n elements
Total copy work: 1 + 2 + 4 + … + n = 2n - 1 (geometric series) = O(n)
Per-insertion amortized cost: O(n) / n insertions = O(1) amortized

This is the same amortized analysis from Phase 0 — the doubling invariant guarantees that each element is copied at most O(log n) times, and the geometric series collapses.

Memory overhead¶

A dynamic array can be up to 2× over-allocated (right after a resize). This is the space cost you pay for amortized O(1) push.

3. Cache Locality¶

This is the performance difference you won’t see in Big-O but will feel in practice.

Modern CPUs don’t fetch individual bytes from RAM. They fetch cache lines — typically 64 bytes. When you access arr[0], the CPU fetches arr[0] through approximately arr[15] (for 4-byte ints) into L1 cache simultaneously. The next 15 accesses are essentially free.

Arrays exploit this perfectly. Sequential iteration over an array of n elements causes ≈ n/16 cache misses.

Linked lists destroy it. Each node is allocated separately on the heap. Traversing a linked list of n nodes causes up to n cache misses — each pointer dereference may point to a completely different memory region.

The practical implication: for traversal-heavy workloads, an O(n) array scan can be 5–10× faster than an O(n) linked list traversal despite identical Big-O. This is why std::vector almost always beats std::list in C++ benchmarks.

4. Two-Pointer Technique¶

Two-pointer is the most important array pattern. It appears in ~15% of LeetCode medium problems involving arrays and strings.

The core idea: instead of nested loops (O(n²)), use two indices that move toward each other or in tandem to reduce the problem to O(n).

Left/Right Pointers (Opposite Ends)¶

arr = [sorted array]
left = 0, right = n-1

while left < right:
    if condition(arr[left], arr[right]):
        process()
    elif need_larger_sum:
        left++
    else:
        right--

Canonical problem: Two Sum II (sorted array) — find two indices where arr[i] + arr[j] == target.

Why it works: the array is sorted. If the current sum is too small, moving left right increases it. If too large, moving right left decreases it. Each move eliminates one impossible pair. Total moves: at most n, so O(n).

Fast/Slow Pointers (Same Direction)¶

slow = 0
for fast in range(n):
    if condition(arr[fast]):
        arr[slow] = arr[fast]
        slow++

Canonical problem: Remove Duplicates from Sorted Array — remove duplicates in-place.

fast scans everything; slow tracks where the “result” array ends. Elements that pass the condition get written to slow’s position. One pass, O(n), O(1) space.

5. String Fundamentals¶

Strings are arrays of characters, but with language-specific behavior that bites engineers constantly.

Immutability (Java, Python)¶

In Java and Python, strings are immutable. str.concat() or s = s + "x" creates a new string object every time — it does not modify the original.

// This is O(n²) total, not O(n)
String result = "";
for (int i = 0; i < n; i++) {
    result += chars[i];  // creates a new string each time
}

// This is O(n)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append(chars[i]);
}
String result = sb.toString();

In C/C++, strings are mutable char arrays — no hidden copies. In C++, std::string has O(1) amortized append due to doubling (same as vector).

Substring Operations¶

Operation	Java	C++	Python
`s[i..j]` substring	O(j-i) — copies	O(j-i) — copies	O(j-i) — copies
`indexOf(pattern)`	O(n·m) naive	O(n·m) naive	O(n·m) naive
Character access	O(1) `charAt(i)`	O(1) `s[i]`	O(1) `s[i]`

Naive substring creation is O(length) — it copies. If you’re creating many substrings inside a loop, you can accidentally build an O(n²) algorithm.

6. Common Array Patterns¶

Prefix Sums¶

The prefix sum array pre[i] = arr[0] + arr[1] + ... + arr[i-1] enables O(1) range sum queries after O(n) preprocessing.

arr  = [3, 1, 4, 1, 5, 9]
pre  = [0, 3, 4, 8, 9, 14, 23]   (pre[0] = 0 sentinel)

sum(l, r) = pre[r+1] - pre[l]     // O(1)

Without prefix sums, each range sum query costs O(r-l). With them, preprocessing is O(n) and each query is O(1).

Difference Arrays¶

For range update problems: “add v to all elements in range [l, r]”. Naively O(n) per update. With a difference array:

diff[l] += v
diff[r+1] -= v

Then prefix-sum the diff array once at the end to recover the result. Each update is O(1); final reconstruction is O(n).

Sliding Window (Preview)¶

A window of size k slides across the array. Instead of recomputing the window sum from scratch each step (O(k) per step → O(nk) total), subtract the element leaving and add the element entering: O(1) per step → O(n) total. Deep dive in Phase 2.

7. Off-By-One Errors: The Mental Model¶

Off-by-one errors happen when the loop boundary and the invariant don’t match. The fix is to state your invariant explicitly before writing the loop.

Rule: Before writing for i in range(...) or while left < right, write one sentence: “At the start of each iteration, [what is true about the state]?”

Example: binary search. Before coding, write: “At the start of each iteration, the target is in arr[left..right] inclusive.” Now your loop condition is while left <= right (not <), and your update is left = mid + 1 (not mid). The invariant forces the correct boundaries.

If you can’t state the invariant, you’re not ready to write the loop.

8. Practice Problems¶

Warmup (Easy)¶

LeetCode #1 — Two Sum (hash map, but worth knowing the two-pointer variant on sorted input)
LeetCode #26 — Remove Duplicates from Sorted Array (fast/slow pointer)
LeetCode #121 — Best Time to Buy and Sell Stock (single-pass, track minimum)

Two-Pointer (Medium)¶

LeetCode #167 — Two Sum II (left/right pointers on sorted array)
LeetCode #15 — 3Sum (sort + two-pointer; watch out for deduplication)
LeetCode #11 — Container With Most Water (prove the greedy left/right move is correct)

Prefix Sum Application (Hard)¶

LeetCode #560 — Subarray Sum Equals K (prefix sum + hash map; O(n) solution requires insight)
LeetCode #42 — Trapping Rain Water (prefix max from left + right; or two-pointer O(1) space)

For problems 7 and 8: try the brute force first, derive its complexity, then optimize. Don’t jump to the O(n) solution immediately.

What Most Engineers Get Wrong¶

Off-by-one errors are not careless mistakes — they are invariant violations. You write while left < right instead of while left <= right because you never stated what your loop invariant is. The fix is not “be more careful” — it’s “write the invariant first.” Every time you hit an off-by-one error, it is a signal that you didn’t state what was supposed to be true at each step. Fix the process, not the symptom.

Secondary mistake: assuming string concatenation in Java/Python is O(1). It’s O(n) per concat, making naive string building O(n²). Always use StringBuilder in Java or "".join(list) in Python when building strings in a loop.

Return to README.md · Next: 02_linked_lists.md