Arrays

ComplexityCopy Anchor Link

Space is O(n).

An array stores items in one contiguous block of memory, so the position of item i is a single calculation. That is why reading arr[i] is O(1) and why almost every other structure is described by how it differs from an array.

Dynamic arraysCopy Anchor Link

A JavaScript array grows on demand. Under the hood a dynamic array keeps spare capacity and, when full, allocates a block about twice as large and copies. Doubling makes the copying cost average out to O(1) per push. See the code tab for a small implementation.

JavaScript specificsCopy Anchor Link

• arr.sort() with no comparator sorts as strings: [10, 2, 1].sort() gives [1, 10, 2]. Use arr.sort((a, b) => a - b).
• sort, reverse, splice, push, pop, shift and unshift mutate. map, filter, slice, concat and the newer toSorted, toReversed, with return new arrays.
• new Array(3).fill([]) makes three references to the same inner array. Use Array.from({ length: 3 }, () => []).
• arr.length = 0 empties the array in place.
• Copies are shallow: [...arr] copies the top level only.

Useful methodsCopy Anchor Link

Techniques that start with an arrayCopy Anchor Link

Most array problems are one of these patterns, each with its own page:

• Two pointers for sorted input or in-place edits.
• Sliding window for contiguous ranges.
• Prefix sums for many range queries.
• Sort first when order or neighbours matter.
• Hash map when you need "seen before?" in O(1).

Common mistakesCopy Anchor Link

• Using shift() in a loop as a queue. It is O(n) each time, so the loop is O(n²).
• Mutating an array while iterating over it.
• Off-by-one on the last index: it is length - 1.

CodeCopy Anchor Link

// A resizable array on top of a fixed-size block, to show why push is O(1) amortised.
export default class DynamicArray {
  constructor() {
    this.capacity = 2;
    this.length = 0;
    this.data = new Array(this.capacity);
  }

  get(i) {
    if (i < 0 || i >= this.length) throw new RangeError('index out of range');
    return this.data[i]; // O(1)
  }

  push(value) {
    if (this.length === this.capacity) this.#grow(); // rare, O(n)
    this.data[this.length++] = value; // usual case, O(1)
  }

  pop() {
    if (this.length === 0) return undefined;
    const value = this.data[--this.length];
    this.data[this.length] = undefined;
    return value;
  }

  insert(i, value) { // O(n): everything after i shifts right
    if (this.length === this.capacity) this.#grow();
    for (let k = this.length; k > i; k--) this.data[k] = this.data[k - 1];
    this.data[i] = value;
    this.length++;
  }

  remove(i) { // O(n): everything after i shifts left
    const value = this.data[i];
    for (let k = i; k < this.length - 1; k++) this.data[k] = this.data[k + 1];
    this.data[--this.length] = undefined;
    return value;
  }

  #grow() {
    this.capacity *= 2;
    const bigger = new Array(this.capacity);
    for (let i = 0; i < this.length; i++) bigger[i] = this.data[i];
    this.data = bigger;
  }
}