Arrays & strings

What "beginner" means for this chapter

If arrays and strings already feel completely automatic to you, skim this one — but don't skip it. The interview traps in this chapter (accidental O(n²) string building, unshift's hidden cost, the shared-reference 2D array bug) are some of the most common ways strong candidates lose points on otherwise-correct solutions.

An array is a promise about memory

A JS array is really a resizable list, but the mental model interviewers expect comes from the lower-level version: a contiguous block of memory where index math replaces searching. Because every slot is the same fixed size apart, the address of index i is just base + i × size — no walking, no scanning. That's the whole reason arr[i] is O(1): it's arithmetic, not a lookup.

What's actually O(1) vs O(n) on an array

Strings are arrays with one extra rule

In JS, strings are immutable — str[0] = "x" silently does nothing. Every "mutation" (slice, +, replace) actually builds a brand new string. That has a real cost: repeatedly concatenating inside a loop is O(n) per concatenation, so a naive loop that builds a string character by character is O(n²), not O(n).

// O(n²) — each += allocates a new string of growing length
function buildSlow(chars) {
  let out = "";
  for (const c of chars) out += c;
  return out;
}

// O(n) — push to an array (O(1) amortized), join once at the end
function buildFast(chars) {
  const parts = [];
  for (const c of chars) parts.push(c);
  return parts.join("");
}

The in-place pattern

A huge share of array interview questions ask for O(1) extra space, which means mutating the input instead of allocating a new array. The standard tool is swap-and-shrink: walk with two indices, overwrite in place, and treat everything past a "write pointer" as garbage.

// remove all occurrences of val, in place, return new length
function removeElement(nums, val) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write; // [0, write) is the real answer
}

This "read pointer scans everything, write pointer only advances on a keep" shape reappears constantly — it's the seed of the two-pointers chapter next.

Prefix sums — turn O(n) range queries into O(1)

If you're going to ask "what's the sum of elements from index i to j?" more than once on the same array, recomputing each sum by scanning is wasteful. Precompute a running total once — O(n) — and every range sum after that is a subtraction, O(1).

function buildPrefixSums(nums) {
  const prefix = new Array(nums.length);
  prefix[0] = nums[0];
  for (let i = 1; i < nums.length; i++) {
    prefix[i] = prefix[i - 1] + nums[i];
  }
  return prefix;
}

// sum of nums[left..right] inclusive, O(1) after O(n) preprocessing
function rangeSum(prefix, left, right) {
  return left === 0 ? prefix[right] : prefix[right] - prefix[left - 1];
}

This is the single highest-leverage array trick for "answer many range queries" problems — it turns what looks like it needs O(n) per query (O(n·q) for q queries) into O(n) total preprocessing plus O(1) per query. The same idea extends to 2D (a prefix-sum matrix for rectangle sums) and to counting problems (prefix counts of a condition).

Kadane's algorithm — the maximum subarray, in one pass

"Find the contiguous subarray with the largest sum" looks like it needs checking every subarray — O(n²). Kadane's insight: at each position, the best subarray ending here is either "extend the previous best" or "start fresh from here" — whichever is bigger — because a negative running sum can only ever hurt what comes after it.

function maxSubArray(nums) {
  let bestSoFar = nums[0];
  let bestEndingHere = nums[0];

  for (let i = 1; i < nums.length; i++) {
    bestEndingHere = Math.max(nums[i], bestEndingHere + nums[i]);
    bestSoFar = Math.max(bestSoFar, bestEndingHere);
  }
  return bestSoFar;
}

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Answer: 6, from subarray [4, -1, 2, 1]. This is O(n) time, O(1) space — and it's the template for a whole family of "best contiguous X" problems (max product subarray, circular array variants).

Rotating an array in O(1) space — the triple-reversal trick

Rotating right by k with a new array is easy but O(n) space. The in-place version uses a neat property: reversing the whole array, then reversing each of the two pieces that should end up in the "wrong" order, produces a correct rotation.

function rotate(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);  // reverse everything
  reverse(nums, 0, k - 1);            // un-reverse the first k
  reverse(nums, k, nums.length - 1);  // un-reverse the rest
}

function reverse(arr, lo, hi) {
  while (lo < hi) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
    lo++; hi--;
  }
}
// [1,2,3,4,5,6,7], k=3
   reverse all    → [7,6,5,4,3,2,1]
   reverse [0,k)  → [5,6,7,4,3,2,1]
   reverse [k,n)  → [5,6,7,1,2,3,4]  ← correctly rotated right by 3

Three O(n) reversals is still O(n) total, but O(1) extra space instead of O(n) — the kind of tradeoff interviewers specifically probe for with "can you do it without the extra array?"

2D arrays — same rules, one more dimension

A 2D array in JS is really an array of arrays — each row is its own separate array object, stored at scattered locations (unlike a true contiguous 2D block in lower-level languages). grid[i][j] is still O(1): it's two index lookups chained, each O(1).

// row-major traversal — the standard order, matches memory/cache-friendly access
function traverse2D(grid) {
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[row].length; col++) {
      console.log(grid[row][col]);
    }
  }
}

const grid = Array.from({ length: n }, () => Array(m).fill(0));

Common gotchas worth knowing cold

• Sparse arrays — new Array(5) creates 5 empty slots, not zeros; .map() skips them.
• Copying — const b = a copies the reference, not the array. Use [...a] or a.slice() for a shallow copy.
• sort() mutates the original array and defaults to string comparison — [10, 2, 1].sort() gives [1, 10, 2] unless you pass a comparator.
• Dynamic array growth is covered in depth in the complexity chapter's amortized-analysis section — the short version: push() is amortized O(1) because the underlying buffer doubles instead of growing by one each time.