4.2 — Arrays & Strings

An array is the only data structure the hardware actually has. Everything else in Part 4 — lists, trees, hash tables, heaps, graphs — is built on top of it, or on top of pointers, and pointers point into memory that is itself addressed like one giant array.

That is worth taking literally. Chapter 1.6 showed that memory is a numbered sequence of bytes. An array is nothing more than a promise that a group of values sits at consecutive numbers, plus the arithmetic that turns an index into an address:

\text{address}(i) = \text{base} + i \times \text{size of one element}

One multiply and one add. That is why arr[500000] costs the same as arr[0] — the CPU does not walk to element 500,000, it computes where it is. This single formula is the source of every property arrays have, good and bad.

1. What the formula gives you and what it costs you

Random access is O(1). Straight from the formula. Give me any index and I hand you the value in fixed time.

Elements must be the same size. The formula multiplies by "size of one element", so that has to be one number. This is why a C array of int works and a C array of "either an int or a string" does not. In JavaScript and Python the elements are all the same size because the array stores references (pointers) of a fixed width, and the actual objects live elsewhere — which is also why iterating a JS array of objects touches memory in two places per element, and iterating an array of small integers touches one. V8 tracks this distinction as elements kinds (Chapter 3.6.9): an array holding only small integers gets a compact, unboxed representation, and the moment you put a string in it, V8 gives up and switches to the general boxed form.

Insertion and deletion in the middle are O(n). The promise is "consecutive". If you want a new value at index 3 of a 10-element array, elements 3 through 9 must each move one slot right so the promise still holds. That is seven copies now, and n copies on a big array.

The same structure, two very different costs. Insertion in the middle must preserve the "consecutive" promise, so every element to the right moves. Appending at the end has nothing to its right, which is why push is cheap and unshift is not.

This is the whole reason push is the fast one and unshift is the slow one, and it explains a bug people write constantly: building a list in reverse with unshift in a loop is O(n^2), while push followed by one reverse() is O(n).

2. The dynamic array: how a fixed block pretends to grow

A raw array has a fixed size chosen when it was allocated. JavaScript's Array, Python's list, Java's ArrayList, C++'s vector and Go's slice are all the same idea layered on top: a fixed block, plus a length, plus a rule for what to do when the block fills up.

class DynamicArray<T> {                                  // (1)
  private buffer: (T | undefined)[] = new Array(1);      // (2)
  private length = 0;                                    // (3)

  push(value: T): void {
    if (this.length === this.buffer.length) this.grow(); // (4)
    this.buffer[this.length] = value;                    // (5)
    this.length++;
  }

  private grow(): void {
    const bigger = new Array(this.buffer.length * 2);    // (6)  ← doubling, not +1
    for (let i = 0; i < this.length; i++) bigger[i] = this.buffer[i];  // (7)
    this.buffer = bigger;
  }

  get(i: number): T {
    if (i < 0 || i >= this.length) throw new RangeError(`index ${i} out of range`);  // (8)
    return this.buffer[i] as T;
  }
}

1. This is what your language's list class does under the covers, with the details removed.
2. buffer is the fixed block. Its size is the capacity.
3. length is how many slots are actually in use. Capacity and length are two different numbers, and confusing them is the source of many off-by-one bugs.
4. Only when the block is full do we pay anything unusual.
5. Otherwise a push is one assignment. That is the O(1) case, and it is the overwhelmingly common one.
6. Doubling is the essential line. Chapter 4.1 section 7 proved why: doubling makes the total copying across n pushes sum to about n, so each push averages one copy. Growing by a fixed amount instead makes the total quadratic.
7. The copy itself is O(current length) — this is the occasional expensive push.
8. Bounds checking. C does not do this and that is where buffer overflows come from (Chapter 8.5); managed languages do it on every access, which is a real but small constant cost that JIT compilers often prove unnecessary and remove (Chapter 3.2).

Growth factors in the real world. Java's ArrayList grows by 1.5×, Python's list uses a pattern that works out to roughly 1.125× for large lists, C++ implementations use 1.5× or 2×, and V8 uses a scheme close to 1.5×. The trade is memory waste against resize frequency, plus a subtler point: with a factor of exactly 2, the freed blocks are always smaller than the next block you need, so the allocator can never reuse them; with a factor below the golden ratio (about 1.618), the sum of all previously freed blocks eventually exceeds the next request, so memory can be recycled. That is the actual argument for 1.5.

Shrinking. Most implementations do not shrink when you remove elements, because a list that hovers around its capacity would then thrash between grow and shrink on every push/pop pair. Those that do shrink use hysteresis: shrink only when the length falls below one quarter of capacity, so a shrink is followed by many pushes before the next grow.

3. Two dimensions, and why the loop order changes the speed

A 2-D array is a lie the language tells you. Memory is one-dimensional, so a grid has to be flattened.

// A 3×4 grid stored row-major: element (r, c) lives at index r * 4 + c
const WIDTH = 4;
const grid = new Int32Array(3 * WIDTH);                 // (1)
const at = (r: number, c: number) => r * WIDTH + c;     // (2)

grid[at(1, 2)] = 99;                                    // (3)  row 1, column 2 → index 6

1. One flat block of 12 integers. Int32Array is a typed array — unlike a normal JS array it holds raw 32-bit integers packed tightly, with no boxing and no per-element object header.
2. The index formula: skip r whole rows, then walk c columns. This is called row-major order, used by C, C++, Java, Python's NumPy by default and every language you are likely to touch. Fortran and MATLAB use column-major, where the column index is the one that skips whole blocks.
3. Row 1, column 2 → 1 * 4 + 2 = index 6.

Now the practical consequence, which is a real interview question and a real performance fix:

// Version A — row by row
for (let r = 0; r < rows; r++)
  for (let c = 0; c < cols; c++)
    total += grid[r * cols + c];      // indexes 0, 1, 2, 3, 4, … — adjacent

// Version B — column by column
for (let c = 0; c < cols; c++)
  for (let r = 0; r < rows; r++)
    total += grid[r * cols + c];      // indexes 0, cols, 2*cols, … — jumping

Both are O(rows \times cols). Big-O says they are identical. On a large grid, version A can be several times faster, and the reason is Chapter 1.6: the CPU loads memory in cache lines of 64 bytes, so touching one integer pulls in the next 15 for free. Version A uses all 16. Version B uses one from each line and then throws the line away before coming back to it. This is the clearest everyday example of the gap between the complexity model and the machine, and it is why "iterate in memory order" is a rule worth having in your fingers.

4. Strings: arrays with two extra problems

A string is an array of characters, plus two complications that generate most string bugs.

Complication one: immutability. In JavaScript, Python, Java and C#, a string cannot be modified after it is created. s[0] = 'X' either silently does nothing or throws. Every "modification" allocates a new string.

This is a deliberate design choice with real benefits — an immutable string can be shared freely between threads with no locking, can be used as a hash-map key whose hash is computed once and cached, and can be interned so that identical literals share one object in memory (Chapter 3.9 covers Java's string pool). The cost is the O(n^2) concatenation trap from Chapter 4.1 section 5, which is why every one of these languages ships a mutable builder: StringBuilder in Java and C#, ''.join(parts) in Python, parts.join('') in JavaScript, strings.Builder in Go.

Complication two: a character is not a byte, and often not even one code unit. Chapter 1.4 built the Unicode story and Chapter 3.6.7 covers the JavaScript specifics. The short version you need for algorithms:

const s = 'café';
s.length;                    // → 4        (four UTF-16 code units)

const e = '👨‍👩‍👧';           // family emoji
e.length;                    // → 8        ← not 1
[...e].length;               // → 5        (code points, still not 1)

.length counts UTF-16 code units, not characters. A character outside the Basic Multilingual Plane — emoji, many CJK extensions, historic scripts — takes two code units (a surrogate pair), so .length over-counts it. Spreading with [...s] iterates code points and fixes the surrogate problem, but still splits an emoji built from several joined code points. What a human calls "one character" is a grapheme cluster, and getting those needs Intl.Segmenter.

For DSA problems this almost never matters, because the problems say "lowercase English letters". For production code it matters constantly: truncating a user's display name at 20 .length units can cut a surrogate pair in half and produce a broken character, and reversing a string with [...s].reverse().join('') mangles any accent written as a combining mark. The rule: in interviews assume ASCII unless told otherwise, and say out loud that you are assuming it; in production, never index into a string you did not create.

5. The character-count array, the single most useful string trick

When a problem restricts you to lowercase English letters, you can replace a hash map with a 26-slot array, and it is worth knowing exactly why that is not just a micro-optimisation.

function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;              // (1)
  const counts = new Int32Array(26);                    // (2)
  const base = 'a'.charCodeAt(0);                       // (3)  → 97
  for (let i = 0; i < a.length; i++) {
    counts[a.charCodeAt(i) - base]++;                    // (4)
    counts[b.charCodeAt(i) - base]--;                    // (5)
  }
  return counts.every(c => c === 0);                     // (6)
}

1. Different lengths can never be anagrams, and checking first saves the whole loop.
2. Twenty-six integer slots, one per letter. Fixed size, so this is O(1) space no matter how long the strings are.
3. charCodeAt gives the numeric code of a character; 'a' is 97, 'z' is 122. Subtracting 97 maps the letters onto 0–25, which are exactly our array indices.
4. Count up for every letter of a.
5. Count down for every letter of b, in the same pass. Doing both in one loop rather than two is not a complexity win, but it is the version that generalises to the sliding-window problems in Chapter 4.6.
6. If the two strings had identical letter counts, every slot cancelled to zero.

Time O(n), space O(1). Compare the sorting solution — sort both strings and compare — which is O(n \log n) time and, in JavaScript, O(n) space because you have to split into an array first. The counting version is strictly better, and being able to say why in one sentence ("sorting orders things I only need to count") is the kind of reasoning the problem chapters train.

The same trick with a Map<string, number> handles the unrestricted-alphabet version at O(k) space where k is the number of distinct characters. The array version is the special case where you know the alphabet in advance; the map version is the general one. Both appear constantly in Chapters 4.4 and 4.16.

6. In-place work and the two-pointer reflex

"In place" means using O(1) extra space by rearranging the input rather than building a new structure. Arrays are where this lives, and the mechanism is almost always two indices moving through the same array.

function reverseInPlace(chars: string[]): void {
  let left = 0, right = chars.length - 1;               // (1)
  while (left < right) {                                // (2)
    [chars[left], chars[right]] = [chars[right], chars[left]];  // (3)
    left++; right--;                                    // (4)
  }
}

1. One index at each end.
2. Stop when they meet or cross. If the length is odd the middle element is already in the right place, and left < right handles that with no special case.
3. Swap. The destructuring form is the readable spelling; a temporary variable is the same thing.
4. Walk both inward.

n/2 iterations, so O(n) time, O(1) space. That shape — two indices, a loop condition comparing them, a rule for which one moves — is the two pointers pattern, and Chapter 4.5 is devoted to it because it solves a whole family of problems (pair sums in a sorted array, palindrome checks, removing duplicates, container-with-most-water, three-sum).

The second in-place shape you need is the write pointer, sometimes called the slow/fast pattern:

function removeValue(nums: number[], target: number): number {
  let write = 0;                                         // (1)
  for (let read = 0; read < nums.length; read++) {       // (2)
    if (nums[read] !== target) {                         // (3)
      nums[write] = nums[read];                          // (4)
      write++;
    }
  }
  return write;                                          // (5)
}

1. write marks where the next keeper goes.
2. read visits every element exactly once.
3. The filter condition — the only part that changes between problems in this family.
4. Keepers get compacted toward the front. write never runs ahead of read, so you can never overwrite something you have not read yet, which is why this is safe in place.
5. Everything before write is the answer; everything from write onward is garbage the caller ignores. Returning the new length rather than resizing is the convention because it avoids an allocation.

O(n) time, O(1) space, and it generalises directly to "remove duplicates from a sorted array", "move zeroes to the end" and "partition around a pivot" — which is the core of quicksort in Chapter 4.10.

7. Prefix sums: paying once so every range query is free

If you will be asked "what is the sum of elements from i to j" many times, computing each answer by looping is O(n) per query. A prefix sum array turns that into O(1) per query after one O(n) setup.

function buildPrefix(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);     // (1)
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];                 // (2)
  }
  return prefix;
}

// sum of nums[i .. j] inclusive:
const rangeSum = (prefix: number[], i: number, j: number) => prefix[j + 1] - prefix[i];  // (3)

1. Length n+1, with a leading zero. That extra slot is what removes every special case — without it, rangeSum(0, j) needs an if.
2. prefix[k] ends up holding the sum of the first k elements. Each step reuses the previous answer, so the build is one pass.
3. The sum from i to j is "everything up to j" minus "everything before i". Subtracting two numbers, in constant time, regardless of how wide the range is.

Worked on [3, 1, 4, 1, 5]: the prefix array is [0, 3, 4, 8, 9, 14]. Sum of indices 1 through 3 is prefix[4] - prefix[1] = 9 - 3 = 6, and indeed 1 + 4 + 1 = 6.

This is the array version of an idea you will meet again and again: precompute a cumulative quantity so that any range becomes a difference. The same shape gives 2-D prefix sums for rectangle queries, difference arrays for range updates, and it is the starting point that Chapter 4.13's segment tree generalises to the case where the underlying values also change.

What the interviewer will push on

"Why is unshift slower than push? Both are one call." They are checking whether you can reason from the memory layout rather than from the API surface. The answer is the consecutive-addresses promise: appending has nothing to its right, prepending has everything. The follow-up is "so how would you build a list front-to-back efficiently?" — push then reverse, or use a deque (Chapter 4.7).

"You said push is O(1). Is it always?" No, and saying so unprompted is the tell. It is O(1) amortized, O(n) on the resize. The good follow-up answer names the fix for latency-sensitive code: pre-allocate the capacity you expect.

"This code iterates a matrix column by column. Any concern?" The wrong answer is "no, it is the same complexity". The right one names cache lines and row-major layout, then says the fix is to swap the loop order or to transpose once if the access pattern is fixed.

"What is the space complexity of your string solution?" In JavaScript, s.split(''), [...s], s.slice() and s.substring() all allocate. A solution that claims O(1) space while calling substring inside a loop is claiming something false. The tell for a strong candidate is tracking index pairs (start, end) into the original string instead of cutting substrings out of it — that is what makes the sliding-window solutions in Chapter 4.6 genuinely O(1) space.

"Your solution assumes lowercase letters. What changes for full Unicode?" They want to hear three things: .length counts UTF-16 code units so it over-counts astral characters, a fixed 26-slot array becomes a hash map, and "reverse the string" stops being well-defined because combining marks must stay attached to their base character.

One thing to volunteer: when you use a fixed-size counting array, say the sentence "this is O(1) space because the alphabet is bounded, and it becomes O(k) with a map if it is not". Naming the assumption that makes your bound true is the single clearest signal that you derived the complexity instead of recalling it.

Recall

• An array is a promise that elements sit at consecutive addresses; address(i) = base + i × size gives O(1) random access and forces O(n) middle insertion.
• A dynamic array is a fixed block plus a length plus a doubling (or 1.5×) growth rule; the multiplier is what makes push O(1) amortized.
• 2-D arrays are flattened row-major, so iterating rows-then-columns uses full cache lines and column-first order wastes them — same big-O, very different speed.
• Strings are immutable in JS/Python/Java/C#, so building one with += in a loop is O(n^2); collect parts and join once. .length counts UTF-16 code units, not characters.
• The two in-place shapes to have in your fingers: two pointers moving inward, and a write pointer compacting keepers toward the front — both O(n) time, O(1) space.
• A prefix sum array turns every range-sum query into one subtraction; the leading zero slot is what removes the edge cases.

Self-test: Why does growing an array by a fixed 100 slots make n pushes O(n^2)? · What does '👨‍👩‍👧'.length return and why is it not 1? · Write the write-pointer loop for "move all zeroes to the end, keeping the order of the rest" · Why is prefix built with length n+1? · Which is faster on a 4096×4096 grid, row-major or column-major iteration, and what would big-O say?

Next: 4.3 explains the structure that turns "have I seen this before" from a scan into a single lookup — hash tables, including what "O(1) average" is actually assuming and what an attacker who chooses your keys can do about it.