Arrays and Strings

Table of Contents

1. Memory Layout: Why Index Access Is Fast
2. JavaScript Arrays in Real Life
3. What Each Operation Costs
4. Seeing the Costs: push, pop, shift, unshift
5. splice, slice, and Copies
6. Strings Are Arrays of Characters (Almost)
7. Technique 1: Two Pointers
8. Technique 2: Sliding Window
9. Technique 3: Prefix Sums
10. Interview Problems
11. Recipe: The arrays Module
12. Try It Yourself

1. Memory Layout: Why Index Access Is Fast

Computer memory is a long row of numbered boxes. A classic array asks the system for a block of boxes sitting right next to each other and puts one item in each. If the block starts at address 1000 and each item takes 8 bytes, then:

index:    0      1      2      3      4
address:  1000   1008   1016   1024   1032
value:    [ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]

To read item 3 the computer does one piece of arithmetic: 1000 + 3 * 8 = 1024, then reads that box. It does not matter whether the array has five items or five million. That is why reading or writing arr[i] is O(1).

The same layout explains the weak spots:

• Inserting in the middle means every item after the gap must slide over to make room: up to n moves.
• Removing from the middle leaves a hole, so every item after it slides back: up to n moves.
• Growing past the end may need a bigger free block, so the whole array gets copied to a new place.

Remember this picture. Almost every cost in this chapter comes from "contiguous boxes with arithmetic addressing".

2. JavaScript Arrays in Real Life

JavaScript hides most of the details. A JavaScript Array is a resizable list: you can push as much as you like without choosing a size. Under the hood the engine keeps a real block of memory for it, and when you outgrow the block it allocates a bigger one (typically a bit larger than the old one) and copies the items across.

The copying looks expensive but the engine only does it rarely, because each new block is much bigger than the last. Spread over many pushes, the average cost of one push is still O(1). This idea is called amortized cost: an occasional expensive step, paid for by many cheap ones.

Some honest details about JavaScript specifically:

• Arrays can hold mixed types: [1, "two", { three: 3 }]. The engine is fastest when all items are the same kind of value (all small integers, say), because it can pack them tightly.
• Writing far past the end, such as arr[1000000] = 1 on a short array, creates a sparse array with holes. Engines switch to a slower representation for those. Avoid it.
• For numbers-only work there are typed arrays such as Float64Array and Uint8Array: fixed size, one number type, really compact. You see them in graphics, audio, and binary file parsing.
• arr.length is a stored value. Reading it is O(1), so there is no need to cache it in a variable "for speed".

For this series, think of a JavaScript array as "a dynamic array": reading by index is O(1), adding or removing at the end is O(1), and anything at the front or middle is O(n).

3. What Each Operation Costs

Here are the operations you use most, with their Big-O cost:

Practical rules that fall out of the table:

• Working at the end of an array is cheap; working at the front is not. If you need a "first in, first out" line, an array with shift is a trap for large data. We fix that in Chapter 5.
• Chaining map, filter, and reduce is fine: each is one pass, and three passes is still O(n). A loop inside a loop, or a search method inside a loop, is what turns O(n) into O(n^2).

4. Seeing the Costs: push, pop, shift, unshift

Let us measure. This script does 100,000 operations of each kind. (Make a scratch file, for instance scratch.ts, and run it with npx tsx scratch.ts.)

function timeIt(label: string, fn: () => void) {
  const start = performance.now();
  fn();
  console.log(label.padEnd(8), (performance.now() - start).toFixed(1), "ms");
}

const N = 100_000;

const a: number[] = [];
timeIt("push", () => {
  for (let i = 0; i < N; i++) a.push(i);
});

const b: number[] = [];
timeIt("unshift", () => {
  for (let i = 0; i < N; i++) b.unshift(i);
});

const c = Array.from({ length: N }, (_, i) => i);
timeIt("pop", () => {
  while (c.length > 0) c.pop();
});

const d = Array.from({ length: N }, (_, i) => i);
timeIt("shift", () => {
  while (d.length > 0) d.shift();
});

On one laptop the output was:

push     2.0 ms
unshift  633.8 ms
pop      0.6 ms
shift    672.8 ms

Your numbers will differ, but the pattern will not: the two end operations take a couple of milliseconds, and the two front operations take hundreds of times longer. Each unshift and shift moves up to 100,000 items, so 100,000 of them cost about 100,000 * 100,000 / 2 item moves. That is O(n^2) for the whole loop.

(Modern engines have clever tricks that sometimes make shift cheaper on small arrays. Do not count on them. Assume O(n).)

A classic way this bites in real code is a work queue written with an array:

const queue: string[] = ["job1", "job2", "job3"];
queue.push("job4");        // add to the back: cheap
const next = queue.shift(); // take from the front: O(n)!
console.log(next, queue);   // job1 [ 'job2', 'job3', 'job4' ]

With three jobs it is fine. With a million queued jobs every shift moves a million items. Keep this in mind until Chapter 5.

5. splice, slice, and Copies

splice is the Swiss Army knife for changing the middle of an array. It mutates the array: it removes items and optionally inserts new ones in their place, and it returns the removed items.

const arr: (number | string)[] = [1, 2, 3, 4, 5];
const removed = arr.splice(1, 2, "a", "b", "c");
//                         ^  ^   items to insert
//                         |  how many to remove
//                         start index
console.log(removed); // [ 2, 3 ]
console.log(arr);     // [ 1, 'a', 'b', 'c', 4, 5 ]

The cost is O(n) because the tail (4, 5 here) must slide to a new position. Deleting by index, arr.splice(i, 1), is the same.

slice does not mutate. It copies a range into a new array:

const nums = [10, 20, 30, 40, 50];
console.log(nums.slice(1, 3));  // [ 20, 30 ]   (end index is excluded)
console.log(nums.slice(-2));    // [ 40, 50 ]   (last two)
console.log(nums);              // [ 10, 20, 30, 40, 50 ] unchanged

slice is O(k) where k is the number of items copied. The spread [...nums] copies the whole array in O(n).

A common accident: copying inside a loop. This looks harmless:

function sumOfSuffixes(nums: number[]): number {
  let total = 0;
  for (let i = 0; i < nums.length; i++) {
    const rest = nums.slice(i);            // O(n) copy every time
    total += rest.reduce((a, b) => a + b, 0);
  }
  return total;
}

It has two passes of work inside a loop, so it is O(n^2). When you see slice, concat, [...arr], or includes inside a loop body, stop and count.

Also remember that arrays are objects, so assignment copies the reference, not the contents:

const original = [1, 2, 3];
const alias = original;       // same array, two names
const copy = [...original];   // a real copy

alias.push(4);
console.log(original); // [ 1, 2, 3, 4 ]
console.log(copy);     // [ 1, 2, 3 ]

6. Strings Are Arrays of Characters (Almost)

A string looks like an array of characters: it has a length, and text[0] gives the first character. Reading by index is O(1) too. But there are important differences.

Strings are immutable. You cannot change a character in place:

let word = "cat";
word[0] = "b";        // silently does nothing (an error in strict mode)
console.log(word);    // cat
word = "b" + word.slice(1); // build a new string instead
console.log(word);    // bat

Every "change" creates a new string and costs O(n) to copy. That makes building a long string with += in a loop potentially O(n^2) in theory (modern engines optimize simple cases, but you cannot count on it for every pattern). The safe habit: collect pieces in an array and join once at the end.

const parts: string[] = [];
for (let i = 0; i < 5; i++) parts.push(`row${i}`);
console.log(parts.join(",")); // row0,row1,row2,row3,row4

Splitting a string into an array of characters, working on the array, and joining back is the usual way to "edit" text:

console.log("a-b-c".split("-"));        // [ 'a', 'b', 'c' ]
console.log("hello".split("").reverse().join("")); // olleh

Characters are not always one position. JavaScript strings are sequences of 16-bit units (UTF-16). Most letters take one unit, but emoji and some other symbols take two, which breaks naive code:

console.log("hello".length);   // 5
console.log("😀".length);       // 2   (one visible symbol, two units)
console.log([..."héllo😀"].length); // 6  (spread iterates whole symbols)

For interview problems, "assume lowercase English letters" is the usual rule and .length is fine. For real user text, such as names in Khmer or text with emoji, use the spread [...text] or Intl.Segmenter to count what the user actually sees. Do not reverse or truncate such text with index arithmetic.

7. Technique 1: Two Pointers

A two-pointer algorithm keeps two indexes into the same array and moves them according to simple rules, replacing a nested loop with a single pass. There are two main shapes:

• Opposite ends: left starts at 0, right at the last index, and they move toward each other.
• Same direction: a fast read pointer scans, and a slow write pointer marks where the next good item goes.

Opposite ends: reverse in place

function reverseInPlace<T>(items: T[]): T[] {
  let left = 0;
  let right = items.length - 1;
  while (left < right) {
    [items[left], items[right]] = [items[right], items[left]];
    left++;
    right--;
  }
  return items;
}

console.log(reverseInPlace([1, 2, 3, 4, 5])); // [ 5, 4, 3, 2, 1 ]

This is O(n) time and O(1) extra space: it swaps pairs from the outside in and never allocates a second array.

Opposite ends: palindrome

A palindrome reads the same both ways. Ignoring punctuation and case:

function isPalindrome(text: string): boolean {
  const clean = text.toLowerCase().replace(/[^a-z0-9]/g, "");
  let left = 0;
  let right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("hello"));                          // false

Opposite ends: two sum in a sorted array

Given a sorted array, find two items that add up to target. The brute force checks every pair: O(n^2). Because the array is sorted we can do better. Look at the smallest and largest items:

• If their sum is too small, the only way to grow it is to move left right (a bigger small number).
• If their sum is too big, the only way to shrink it is to move right left.

function twoSumSorted(
  sorted: number[],
  target: number
): [number, number] | null {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10)); // [ 2, 3 ]  (4 + 6)
console.log(twoSumSorted([1, 2], 10));              // null

Trace the first call: 1 + 11 = 12 is too big, so right moves to 8. 1 + 8 = 9 is too small, so left moves to 3. 3 + 8 = 11 is too big, so right moves to 6. 3 + 6 = 9 is too small, so left moves to 4. 4 + 6 = 10: found, at indexes 2 and 3. Each step discards a candidate for good, so the whole thing is O(n).

Same direction: remove duplicates from a sorted array

Sorted data keeps duplicates next to each other. A slow write pointer marks the end of the unique prefix, and a fast read pointer scans:

function removeDuplicatesSorted(sorted: number[]): number {
  if (sorted.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < sorted.length; read++) {
    if (sorted[read] !== sorted[write - 1]) {
      sorted[write] = sorted[read];
      write++;
    }
  }
  return write; // the count of unique items
}

const data = [1, 1, 2, 2, 2, 3];
const count = removeDuplicatesSorted(data);
console.log(count, data.slice(0, count)); // 3 [ 1, 2, 3 ]

It modifies the array in place, in O(n) time and O(1) space. This "overwrite as you scan" idea comes back in sorting and partitioning.

8. Technique 2: Sliding Window

Many problems ask about a contiguous range (a subarray or substring) that meets some condition. The brute force examines every range. A sliding window keeps one range and moves it forward, adding the new item at the right edge and dropping the old one at the left, updating the answer incrementally.

Fixed-size window: the best sum of k items

Find the largest sum of any k consecutive numbers. The slow way adds k numbers for each starting spot: O(n * k). The window way adds the entering item and subtracts the leaving item:

function maxSumWindow(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) throw new RangeError("k out of range");
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]; // add the new item, drop the old one
    if (sum > best) best = sum;
  }
  return best;
}

console.log(maxSumWindow([2, 1, 5, 1, 3, 2], 3)); // 9  (5 + 1 + 3)

Walk through it: the first window [2, 1, 5] sums to 8. Sliding to [1, 5, 1] gives 8 + 1 - 2 = 7. Then [5, 1, 3] gives 7 + 3 - 1 = 9. Then [1, 3, 2] gives 9 + 2 - 5 = 6. The best is 9. Each step is O(1), so the total is O(n) no matter how large k is.

Variable-size window: longest substring without repeats

Find the length of the longest substring with no repeated character. The window grows on the right every step. When it would contain a repeat, the left edge jumps forward past the earlier copy of that character. A Map remembers the last index of each character (Chapter 3 explains Map fully):

function longestUniqueSubstring(text: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0;
  let best = 0;
  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= start) start = prev + 1;
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

console.log(longestUniqueSubstring("abcabcbb")); // 3  ("abc")
console.log(longestUniqueSubstring("bbbbb"));    // 1
console.log(longestUniqueSubstring("pwwkew"));   // 3  ("wke")
console.log(longestUniqueSubstring("abba"));     // 2

The prev >= start check matters. In "abba", when we reach the final a, its last position (0) is already outside the window, so the start must not move backward. Without that check you would get a wrong answer of 3 for this input. Each character enters and leaves the window at most once, so the cost is O(n).

When to reach for a sliding window: the question says "subarray" or "substring", asks for a longest, shortest, or best one, and the condition can be checked by updating a few counters when an item enters or leaves.

9. Technique 3: Prefix Sums

Suppose you answer thousands of questions of the form "what is the sum of items from index i to index j?" on the same array. Re-adding the range each time costs O(n) per question.

A prefix sum array does the adding once. prefix[k] stores the sum of the first k items. Then any range sum is one subtraction:

nums:    [ 3, 1, 4, 1, 5, 9, 2, 6 ]
prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
          ^                       ^
          prefix[0] = 0 (empty)   prefix[8] = sum of all 8 items

The sum of nums[from..to] (both included) is prefix[to + 1] - prefix[from]:

function buildPrefix(nums: number[]): number[] {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return prefix;
}

function rangeSum(prefix: number[], from: number, to: number): number {
  return prefix[to + 1] - prefix[from];
}

const prefix = buildPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(prefix);                  // [ 0, 3, 4, 8, 9, 14, 23, 25, 31 ]
console.log(rangeSum(prefix, 2, 5));  // 19  (4 + 1 + 5 + 9)
console.log(rangeSum(prefix, 0, 7));  // 31  (everything)

Building costs O(n) once. After that, every query is O(1). This is the time-for-memory trade from Chapter 1: one extra array of n + 1 numbers.

The leading 0 is not a trick for show. It lets a range starting at index 0 work with the same formula, with no special case. Off-by-one slips happen constantly with ranges, so keep the convention fixed: prefix[k] is the sum of the first k items.

Where do you meet this at work? Analytics dashboards ("revenue between two dates", when the data is a daily array), image processing ("sum of pixels in a rectangle", the 2D version), and any "running total" column in a spreadsheet. The same idea works with counts, products, and XORs.

10. Interview Problems

Move zeroes

Given an array, move all zeros to the end while keeping the order of the other items, in place. Example: [0, 1, 0, 3, 12] becomes [1, 3, 12, 0, 0].

Same-direction two pointers: read scans every item, write marks where the next non-zero item goes. Swapping a non-zero item into place sends the zero it replaces toward the back:

function moveZeroes(nums: number[]): number[] {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

console.log(moveZeroes([0, 1, 0, 3, 12])); // [ 1, 3, 12, 0, 0 ]

This is O(n) time, O(1) space. The wrong answer to avoid is splice-ing each zero out and push-ing a new zero in, which costs O(n) per zero and O(n^2) overall.

How to talk about it

For each problem, practice saying the complexity out loud:

11. Recipe: The arrays Module

Add src/arrays.ts to algolab with everything from this chapter:

// src/arrays.ts

// ---- two pointers ----

export function reverseInPlace<T>(items: T[]): T[] {
  let left = 0;
  let right = items.length - 1;
  while (left < right) {
    [items[left], items[right]] = [items[right], items[left]];
    left++;
    right--;
  }
  return items;
}

export function isPalindrome(text: string): boolean {
  const clean = text.toLowerCase().replace(/[^a-z0-9]/g, "");
  let left = 0;
  let right = clean.length - 1;
  while (left < right) {
    if (clean[left] !== clean[right]) return false;
    left++;
    right--;
  }
  return true;
}

export function twoSumSorted(
  sorted: number[],
  target: number
): [number, number] | null {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

export function removeDuplicatesSorted(sorted: number[]): number {
  if (sorted.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < sorted.length; read++) {
    if (sorted[read] !== sorted[write - 1]) {
      sorted[write] = sorted[read];
      write++;
    }
  }
  return write;
}

export function moveZeroes(nums: number[]): number[] {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

// ---- sliding window ----

export function maxSumWindow(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) throw new RangeError("k out of range");
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];
    if (sum > best) best = sum;
  }
  return best;
}

export function longestUniqueSubstring(text: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0;
  let best = 0;
  for (let end = 0; end < text.length; end++) {
    const ch = text[end];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= start) start = prev + 1;
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

// ---- prefix sums ----

export function buildPrefix(nums: number[]): number[] {
  const prefix = [0];
  for (const n of nums) prefix.push(prefix[prefix.length - 1] + n);
  return prefix;
}

export function rangeSum(
  prefix: number[],
  from: number,
  to: number
): number {
  return prefix[to + 1] - prefix[from];
}

Now the tests in src/arrays.test.ts:

// src/arrays.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  reverseInPlace,
  isPalindrome,
  twoSumSorted,
  removeDuplicatesSorted,
  moveZeroes,
  maxSumWindow,
  longestUniqueSubstring,
  buildPrefix,
  rangeSum,
} from "./arrays.ts";

test("two pointers", () => {
  assert.deepEqual(reverseInPlace([1, 2, 3]), [3, 2, 1]);
  assert.equal(isPalindrome("A man, a plan, a canal: Panama"), true);
  assert.equal(isPalindrome("hello"), false);
  assert.deepEqual(twoSumSorted([1, 3, 4, 6, 8, 11], 10), [2, 3]);
  assert.equal(twoSumSorted([1, 2], 10), null);
  const d = [1, 1, 2, 2, 3];
  assert.equal(removeDuplicatesSorted(d), 3);
  assert.deepEqual(d.slice(0, 3), [1, 2, 3]);
  assert.deepEqual(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0]);
});

test("sliding window", () => {
  assert.equal(maxSumWindow([2, 1, 5, 1, 3, 2], 3), 9);
  assert.throws(() => maxSumWindow([1], 2), RangeError);
  assert.equal(longestUniqueSubstring("abcabcbb"), 3);
  assert.equal(longestUniqueSubstring("abba"), 2);
});

test("prefix sums", () => {
  const p = buildPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
  assert.equal(rangeSum(p, 2, 5), 19);
  assert.equal(rangeSum(p, 0, 7), 31);
});

Run npm test. You should now see 6 passing tests (3 from Chapter 1 and 3 new ones) and # fail 0.

Create a new file demo2.ts to see the window beat the brute force:

import { time } from "./src/bench.ts";
import { maxSumWindow } from "./src/arrays.ts";

const big = Array.from({ length: 50_000 }, (_, i) => (i * 37) % 101);
const k = 1000;

const brute = time(() => {
  let best = -Infinity;
  for (let i = 0; i + k <= big.length; i++) {
    let s = 0;
    for (let j = i; j < i + k; j++) s += big[j];
    if (s > best) best = s;
  }
  return best;
}, "brute force");

const windowed = time(() => maxSumWindow(big, k), "sliding window");

console.log(brute.label.padEnd(16), brute.ms.toFixed(1), "ms"); // about 30 ms
console.log(windowed.label.padEnd(16), windowed.ms.toFixed(2), "ms"); // about 0.6 ms
console.log("same answer:", brute.result === windowed.result); // true

The two answers are always equal. The window version is typically dozens of times faster, and the gap grows with k.

12. Try It Yourself

1. Cost the operations. For each, write the Big-O: (a) arr.at(-1); (b) arr.unshift(0); (c) arr.splice(0, 1); (d) [...arr, x] inside a loop that runs n times; (e) str.split("").reverse().join("").
2. Merge two sorted arrays. Write mergeSorted(a, b) that returns one sorted array, using one pointer per input. It should take O(n + m) time. (This is also the heart of merge sort in Chapter 8.)
3. Squares of a sorted array. Given a sorted array that may hold negative numbers, such as [-4, -1, 0, 3, 10], return the squares in sorted order: [0, 1, 9, 16, 100]. Do it in O(n) with two pointers moving inward from both ends, filling the result from the back. Why does a plain map then sort cost more?
4. Shortest subarray with a big enough sum. Given positive numbers and a target, return the length of the shortest contiguous subarray whose sum is at least the target (or 0 if none). For [2, 3, 1, 2, 4, 3] and target 7 the answer is 2 (the subarray [4, 3]). Hint: a variable-size sliding window.
5. Interview-style: product of everything else. Given nums, return an array where item i is the product of all numbers except nums[i], without using division. For [1, 2, 3, 4] the answer is [24, 12, 8, 6]. Hint: build a prefix product and a suffix product.
6. Interview-style: subarray sum equals k. Count the contiguous subarrays that add up to k. For [1, 2, 3] with k = 3 the answer is 2 ([1, 2] and [3]). First do the O(n^2) version with rangeSum; then think about how a Map of earlier prefix sums (coming in Chapter 3) turns it into O(n).

Arrays give you speed by position, but they struggle with "find by value". For that, we need a structure that jumps straight to the answer. Next is Hash Maps and Sets, where you find out how Map and Set achieve O(1) lookups, and build your own HashMap class to see it with your own eyes.