Arrays, strings and hashing

Arrays and dynamic arrays

Also called list, ArrayList, vector, resizable array, dynamic array

What

An array stores items side by side in memory, so reading or writing index i is O(1). A dynamic array grows by allocating a bigger block and copying, so appending is O(1) amortised, while inserting or removing in the middle is O(n).

Why

It is the default container for sequences and the backing store for strings, stacks and heaps. Its contiguous layout also makes it fast in practice thanks to the CPU cache.

const nums = [3, 1, 4];
nums.push(1);      // amortised O(1)
nums[0] = 9;       // O(1)
nums.unshift(2);   // O(n): shifts every item
nums.pop();        // O(1) at the end
nums.shift();      // O(n) at the front

Strings

What

A string is a sequence of characters. In Python, Java and JavaScript strings are immutable, so every change builds a new string; C++ std::string is mutable. Taking a substring or slice copies it, costing O(k) for k characters.

Why

String problems are array problems with extra costs hidden in concatenation, slicing and comparison, and those costs decide whether a solution is O(n) or O(n^2).

const parts = [];
for (const word of words) parts.push(word.toUpperCase());
const result = parts.join(' ');
const chars = [...s];          // mutable copy
chars[0] = 'X';
const s2 = chars.join('');

Hash maps

Also called hash table, dictionary, dict, HashMap, unordered_map, Map

What

A hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete. Collisions are handled by chaining or probing, and the table resizes as it fills.

Why

It is the first tool for counting, grouping, caching and checking whether you have seen something before in one pass, often turning an O(n^2) search into O(n).

const counts = new Map();
for (const w of words) {
  counts.set(w, (counts.get(w) ?? 0) + 1);
}
const apples = counts.get('apple') ?? 0;
const byLen = Map.groupBy(words, (w) => w.length);  // ES2024

Hash sets

Also called set, HashSet, unordered_set, Set

What

A hash set stores unique keys without values, with O(1) average add, remove and membership check.

Why

Use it for de-duplication, visited markers and membership checks. Checking membership in a list is O(n); in a set it is O(1) on average.

function hasDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Composite and custom keys

Also called tuple key, pair key, composite key

What

When a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value. Each language has a safe choice: tuples, records, packed integers or joined strings.

Why

Visited sets on grids and grouping anagrams depend on it, and a wrong key type fails silently by never matching.

const visited = new Set();
visited.add(r * cols + c);         // numbers compare by value
visited.has([r, c]);               // always false: new array
const groups = new Map();
const key = [...word].sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);

Prefix sums

Also called cumulative sum, running total

What

A prefix sum array stores running totals, so prefix[i] is the sum of the first i items. The sum of any range i..j is prefix[j + 1] - prefix[i]: O(1) per query after an O(n) build.

Why

It answers many range-sum queries fast, and combined with a hash map of earlier prefix values it counts subarrays with a given sum in O(n), even with negative numbers.

const prefix = [0];
for (const x of nums) prefix.push(prefix.at(-1) + x);
const rangeSum = prefix[j + 1] - prefix[i];  // nums[i..j]

Integer limits and overflow

Also called overflow, MAX_SAFE_INTEGER, INT_MAX, integer overflow

What

Java and C++ int holds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour. JavaScript numbers are exact integers only up to 2^53 - 1. Python integers grow without limit.

Why

Sums, products and midpoints of large values overflow quietly and give wrong answers with no error, a common cause of failing hidden tests.

Number.MAX_SAFE_INTEGER;          // 2^53 - 1
const mid = Math.floor((lo + hi) / 2);
const half = (lo + hi) >> 1;      // only below 2^31
const big = 2n ** 64n;            // BigInt: exact huge values
const q = Math.trunc(-7 / 2);     // -3
const r = ((-7 % 2) + 2) % 2;     // 1, while -7 % 2 is -1

JavaScript built-in collections

Also called Map, Set

What

Arrays are dynamic arrays with O(1) push and pop at the end. Map and Set are hash tables that keep insertion order and accept any key type. There is no built-in heap, deque or sorted map.

Why

Knowing the gaps tells you when to write a small heap or use a head index instead of shift(). Prefer Map to plain objects for counting, since object keys are always turned into strings.

const stack = [];          // push and pop are O(1)
const queue = [];          // push, then read queue[head++]
let head = 0;
const counts = new Map();  // keeps insertion order
const seen = new Set();
const grid = Array.from({ length: rows }, () =>
  new Array(cols).fill(0));