Arrays

const range = (n: number) =>
  Array.from({ length: n }, (_, i) => i);
range(4); // [0, 1, 2, 3]
 
const grid = Array.from({ length: 2 }, () =>
  new Array<number>(3).fill(0),
);
grid[0][0] = 1;
grid; // [[1, 0, 0], [0, 0, 0]]
 
const bad = new Array<number[]>(2).fill([0, 0, 0]);
bad[0][0] = 1;
bad; // [[1, 0, 0], [1, 0, 0]]: one row, twice

const holes = new Array<number>(3);
holes.length; // 3
Object.keys(holes.map(() => 7)); // []: map skipped holes
Array.from({ length: 3 }, () => 7); // [7, 7, 7]

const counts = new Int32Array(26); // all zeros
for (const ch of "banana") {
  counts[ch.charCodeAt(0) - 97]++;
}
counts[0]; // 3: the a's
counts[13]; // 2: the n's
 
new Int32Array([10, 9, 1, 2]).sort(); // [1, 2, 9, 10]
Int32Array.of(-1.9)[0]; // -1: truncates toward zero
Array.isArray(counts); // false
 
const xs = new Int32Array([1, 2, 3]);
xs.subarray(1)[0] = 9; // a view: shares memory
xs; // [1, 9, 3]
xs.slice(1)[0] = 7; // a copy
xs; // [1, 9, 3]

const xs = [10, 20, 30, 40, 50];
xs.at(-1); // 50
xs[-1]; // undefined
xs[7]; // undefined: no IndexError
xs.slice(1, 3); // [20, 30]
xs.slice(-2); // [40, 50]
 
const [first, ...rest] = xs;
first; // 10
rest; // [20, 30, 40, 50]
// no step slicing: filter by index
xs.filter((_, i) => i % 2 === 0); // [10, 30, 50]
xs.toReversed(); // [50, 40, 30, 20, 10]

const xs = ["a", "b", "c", "d"];
xs.splice(1, 2); // ["b", "c"]: the removed items
xs; // ["a", "d"]
xs.splice(1, 0, "x"); // []: insert at 1, nothing removed
xs; // ["a", "x", "d"]
xs.push("e", "f"); // 5: the new length
xs.pop(); // "f"
xs.toSpliced(0, 1); // ["x", "d", "e"]: xs is unchanged
 
const ys = [1, 2];
ys[4] = 5; // grows the array, leaving holes
ys.length; // 5

const xs = [1, NaN, 3];
xs.indexOf(NaN); // -1: NaN !== NaN
xs.includes(NaN); // true
 
type User = { id: number; admin: boolean };
const users: User[] = [
  { id: 7, admin: true },
  { id: 9, admin: false },
];
const u = users.find((u) => u.id === 7); // User | undefined
u?.admin; // true
users.findIndex((u) => u.id === 8); // -1
users.some((u) => u.admin); // true
[1, 2].every((n) => n > 5); // false
([] as number[]).every((n) => n > 5); // true: vacuous

function lowerBound(xs: readonly number[], x: number) {
  let lo = 0;
  let hi = xs.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (xs[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
 
function upperBound(xs: readonly number[], x: number) {
  let lo = 0;
  let hi = xs.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (xs[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
 
const xs = [1, 3, 3, 3, 7, 9];
lowerBound(xs, 3); // 1
upperBound(xs, 3); // 4
upperBound(xs, 3) - lowerBound(xs, 3); // 3: copies of 3
lowerBound(xs, 8); // 5: where 8 would go
lowerBound(xs, 10); // 6: past the end

/** Smallest n in [lo, hi) with ok(n); hi if none. */
function firstTrue(
  lo: number,
  hi: number,
  ok: (n: number) => boolean,
) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}
 
firstTrue(0, 100, (m) => m * m >= 50); // 8
firstTrue(0, 2 ** 50, (m) => m >= 3e12); // 3000000000000

const n = [10, 9, 1, 2];
n.toSorted(); // [1, 10, 2, 9]: as strings
n.toSorted((a, b) => a - b); // [1, 2, 9, 10]
n.toSorted((a, b) => b - a); // [10, 9, 2, 1]
[3, NaN, 1, 2].toSorted((a, b) => a - b); // [3, NaN, 1, 2]
 
// @ts-expect-error: a comparator must return a number
n.toSorted((a, b) => a > b);
 
const big = [3n, 1n, 2n];
big.toSorted((a, b) => (a < b ? -1 : a > b ? 1 : 0));
// [1n, 2n, 3n]

type P = { name: string; age: number };
const people: P[] = [
  { name: "cy", age: 31 },
  { name: "ann", age: 31 },
  { name: "bo", age: 25 },
];
const byAgeDesc = (a: P, b: P) =>
  b.age - a.age || a.name.localeCompare(b.name);
people.toSorted(byAgeDesc).map((p) => p.name);
// ["ann", "cy", "bo"]
 
// stable: equal keys keep their input order
const rows = [["b", 2], ["a", 1], ["c", 2]] as const;
rows.toSorted((x, y) => x[1] - y[1]).map((r) => r[0]);
// ["a", "b", "c"]
 
// argsort: indexes in value order, best first
const scores = [70, 95, 80];
[...scores.keys()].sort((i, j) => scores[j] - scores[i]);
// [1, 2, 0]

["é", "z", "a"].toSorted(); // ["a", "z", "é"]
["é", "z", "a"].toSorted((a, b) => a.localeCompare(b));
// ["a", "é", "z"]
 
const coll = new Intl.Collator("en", { numeric: true });
["v10", "v9", "v1"].toSorted(coll.compare);
// ["v1", "v9", "v10"]

const words = ["a b", "c"];
words.map((w) => w.length); // [3, 1]
words.flatMap((w) => w.split(" ")); // ["a", "b", "c"]
[1, [2, [3, [4]]]].flat(2); // [1, 2, 3, [4]]
 
// flatMap as filter + map in one pass
const nums = ["1", "x", "3"].flatMap((s) => {
  const n = Number(s);
  return Number.isNaN(n) ? [] : [n];
});
nums; // [1, 3]

const xs = [1, 2, 2, 3];
for (let i = 0; i < xs.length; i++) {
  if (xs[i] === 2) xs.splice(i, 1); // ❌ skips the next item
}
xs; // [1, 2, 3]
 
const ys = [1, 2, 2, 3];
for (let i = ys.length - 1; i >= 0; i--) {
  if (ys[i] === 2) ys.splice(i, 1); // ✅ walk backward
}
ys; // [1, 3]
[1, 2, 2, 3].filter((x) => x !== 2); // ✅ [1, 3], a copy

const prices = [3, 4.5, 10];
prices.reduce((sum, p) => sum + p, 0); // 17.5
([] as number[]).reduce((a, b) => a + b, 0); // 0
 
type Counts = Record<string, number>;
const counts = ["a", "b", "a"].reduce<Counts>(
  (acc, k) => {
    acc[k] = (acc[k] ?? 0) + 1;
    return acc;
  },
  {},
);
counts; // { a: 2, b: 1 }
 
Math.max(...prices); // 10
prices.reduce((m, p) => Math.max(m, p), -Infinity); // 10

const stock = [
  { name: "apple", qty: 0 },
  { name: "pear", qty: 4 },
];
const g = Object.groupBy(stock, (i) =>
  i.qty > 0 ? "inStock" : "soldOut",
);
g.inStock?.map((i) => i.name); // ["pear"]
 
const m = Map.groupBy(stock, (i) => i.qty > 0);
m.get(false)?.map((i) => i.name); // ["apple"]

const a = [[1, 2], [3]];
const b = a; // an alias
const c = [...a]; // new outer array, same inner arrays
const d = structuredClone(a); // nothing shared
a[0].push(99);
a.push([4]);
b; // [[1, 2, 99], [3], [4]]
c; // [[1, 2, 99], [3]]
d; // [[1, 2], [3]]
 
function tag(items: string[]) {
  items.push("seen"); // mutates the caller's array
}
const names = ["ann"];
tag(names);
names; // ["ann", "seen"]

const frozen: readonly number[] = [3, 1, 2];
frozen.toSorted(); // [1, 2, 3]: a new number[]
// @ts-expect-error: sort does not exist on readonly number[]
frozen.sort();
frozen; // [1, 2, 3]: readonly is erased, so it still ran
 
const locked = Object.freeze([3, 1, 2]); // readonly number[]
let err = "";
try {
  // @ts-expect-error: and at runtime, sort throws
  locked.sort();
} catch (e) {
  err = (e as Error).name;
}
err; // "TypeError"

const st: number[] = [];
st.push(1);
st.push(2);
st.at(-1); // 2: peek
st.pop(); // 2
st.pop(); // 1
st.pop(); // undefined: no error on empty
st.length === 0; // true

const q = [10, 20, 30, 40, 50];
let head = 0;
q[head++]; // 10: dequeue in O(1)
q[head++]; // 20
q.push(60); // enqueue
q.length - head; // 4: still queued
q.slice(head); // [30, 40, 50, 60]

class Deque<T> {
  private buf: (T | undefined)[] = new Array(8);
  private head = 0;
  private n = 0;
 
  get size() {
    return this.n;
  }
  pushBack(x: T) {
    this.grow();
    this.buf[this.at(this.n++)] = x;
  }
  pushFront(x: T) {
    this.grow();
    this.head = this.at(-1);
    this.buf[this.head] = x;
    this.n++;
  }
  popFront(): T | undefined {
    if (this.n === 0) return undefined;
    const x = this.buf[this.head];
    this.buf[this.head] = undefined; // let GC take it
    this.head = this.at(1);
    this.n--;
    return x;
  }
  popBack(): T | undefined {
    if (this.n === 0) return undefined;
    const i = this.at(--this.n);
    const x = this.buf[i];
    this.buf[i] = undefined;
    return x;
  }
  peekFront(): T | undefined {
    return this.n ? this.buf[this.head] : undefined;
  }
  peekBack(): T | undefined {
    if (this.n === 0) return undefined;
    return this.buf[this.at(this.n - 1)];
  }
  private at(k: number) {
    return (this.head + k) & (this.buf.length - 1);
  }
  private grow() {
    if (this.n < this.buf.length) return;
    const old = this.buf;
    const mask = old.length - 1;
    this.buf = new Array(old.length * 2);
    for (let k = 0; k < this.n; k++) {
      this.buf[k] = old[(this.head + k) & mask];
    }
    this.head = 0;
  }
}
 
const d = new Deque<number>();
d.pushBack(1);
d.pushBack(2);
d.pushFront(0);
d.popBack(); // 2
d.popFront(); // 0
d.peekFront(); // 1
d.size; // 1

const xs = [1, 2, 3]; // PACKED_SMI_ELEMENTS
xs.push(4.5); // PACKED_DOUBLE_ELEMENTS
xs[3] = 4; // still PACKED_DOUBLE: kinds never go back
 
const ws: (number | string)[] = [1, 2];
ws.push("x"); // PACKED_ELEMENTS: stores pointers
 
const ys = [1, 2, 3];
ys[5] = 6; // HOLEY_SMI_ELEMENTS
ys[3] = 4;
ys[4] = 5; // still HOLEY, though no hole is left

function* naturals() {
  let n = 0;
  while (true) yield n++;
}
 
naturals()
  .filter((n) => n % 2 === 0)
  .map((n) => n * 10)
  .take(3)
  .toArray(); // [0, 20, 40]
 
const ages = new Map([["ann", 31], ["bo", 17]]);
ages
  .entries()
  .filter(([, age]) => age >= 18)
  .map(([name]) => name)
  .toArray(); // ["ann"]
 
Iterator.from(new Set([1, 50, 200])).find((n) => n > 10);
// 50

const xs = [2, 4, 1, 5];
const pre = new Array<number>(xs.length + 1).fill(0);
for (let i = 0; i < xs.length; i++) {
  pre[i + 1] = pre[i] + xs[i];
}
pre; // [0, 2, 6, 7, 12]
pre[3] - pre[1]; // 5: xs[1] + xs[2] in O(1)
 
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
const grid = ["..#", "...", "#.."];
const [r, c] = [0, 0];
const nbrs: [number, number][] = [];
for (const [dr, dc] of DIRS) {
  const nr = r + dr;
  const nc = c + dc;
  if (nr < 0 || nr >= grid.length) continue;
  if (nc < 0 || nc >= grid[0].length) continue;
  if (grid[nr][nc] === ".") nbrs.push([nr, nc]);
}
nbrs; // [[1, 0], [0, 1]]
 
function subsets(nums: readonly number[]): number[][] {
  const out: number[][] = [];
  const path: number[] = [];
  const go = (i: number): void => {
    if (i === nums.length) {
      out.push([...path]); // copy: path keeps changing
      return;
    }
    go(i + 1); // skip nums[i]
    path.push(nums[i]); // take nums[i]
    go(i + 1);
    path.pop(); // undo
  };
  go(0);
  return out;
}
subsets([1, 2]); // [[], [2], [1], [1, 2]]

type Point = readonly [x: number, y: number];
const p: Point = [1, 2];
const [px, py] = p;
px + py; // 3
 
type Row = [id: string, ...scores: number[]];
const r: Row = ["ann", 9, 7];
r.length; // 3
 
const dirs = ["n", "e", "s", "w"] as const;
type Dir = (typeof dirs)[number]; // "n" | "e" | "s" | "w"
const turn = (d: Dir): Dir =>
  dirs[(dirs.indexOf(d) + 1) % 4];
turn("w"); // "n"
 
function sum(xs: readonly number[]) {
  return xs.reduce((a, b) => a + b, 0);
}
sum([1, 2, 3]); // 6: number[] fits readonly number[]

const xs = [5, 7, 9];
let total = 0;
for (let i = 0; i < xs.length; i++) {
  total += xs[i]!; // `!` keeps this compiling with the flag
}
total; // 21
const last = xs[xs.length - 1] ?? 0;
last; // 9
xs.at(5) ?? -1; // -1

const maybe = [1, undefined, 3];
const nums = maybe.filter((n) => n !== undefined);
nums; // [1, 3], typed number[]
 
const mixed = ["a", null, "b"];
const strs = mixed.filter((s) => s != null);
strs; // ["a", "b"], typed string[]

function twoSumSorted(
  xs: readonly number[],
  target: number,
): [number, number] | undefined {
  let i = 0;
  let j = xs.length - 1;
  while (i < j) {
    const s = xs[i] + xs[j];
    if (s === target) return [i, j];
    if (s < target) i++;
    else j--;
  }
  return undefined;
}
 
twoSumSorted([1, 3, 4, 6, 9], 10); // [0, 4]
twoSumSorted([1, 2], 7); // undefined

type Interval = [start: number, end: number];
 
function merge(ivs: readonly Interval[]): Interval[] {
  const sorted = ivs.toSorted((a, b) => a[0] - b[0]);
  const out: Interval[] = [];
  for (const [s, e] of sorted) {
    const last = out.at(-1);
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s, e]);
  }
  return out;
}
 
merge([[8, 10], [1, 3], [2, 6], [15, 18]]);
// [[1, 6], [8, 10], [15, 18]]

function productExceptSelf(xs: readonly number[]) {
  const n = xs.length;
  const out = new Array<number>(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {
    out[i] = left;
    left *= xs[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;
    right *= xs[i];
  }
  return out;
}
 
productExceptSelf([1, 2, 3, 4]); // [24, 12, 8, 6]

function reverse(xs: number[], i: number, j: number) {
  for (; i < j; i++, j--) [xs[i], xs[j]] = [xs[j], xs[i]];
}
 
function rotate(xs: number[], k: number) {
  const n = xs.length;
  if (n === 0) return;
  k = ((k % n) + n) % n; // also handles k < 0
  reverse(xs, 0, n - 1);
  reverse(xs, 0, k - 1);
  reverse(xs, k, n - 1);
}
 
const xs = [1, 2, 3, 4, 5, 6, 7];
rotate(xs, 3);
xs; // [5, 6, 7, 1, 2, 3, 4]

function moveZeros(xs: number[]) {
  let w = 0; // next write position
  for (const x of xs) if (x !== 0) xs[w++] = x;
  xs.fill(0, w);
}
 
const xs = [0, 1, 0, 3, 12];
moveZeros(xs);
xs; // [1, 3, 12, 0, 0]

function maxSubarray(xs: readonly number[]) {
  let best = -Infinity;
  let cur = 0;
  for (const x of xs) {
    cur = Math.max(x, cur + x); // extend, or start over
    best = Math.max(best, cur);
  }
  return best;
}
 
maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6
maxSubarray([-3, -1]); // -1

function nextWarmer(temps: readonly number[]) {
  const out = new Array<number>(temps.length).fill(0);
  const st: number[] = []; // indexes, temps decreasing
  temps.forEach((t, i) => {
    while (st.length && temps[st.at(-1)!] < t) {
      const j = st.pop()!;
      out[j] = i - j;
    }
    st.push(i);
  });
  return out;
}
 
nextWarmer([73, 74, 75, 71, 69, 72, 76, 73]);
// [1, 1, 4, 2, 1, 1, 0, 0]

function windowMax(xs: readonly number[], k: number) {
  const dq: number[] = []; // indexes, values decreasing
  let head = 0;
  const out: number[] = [];
  xs.forEach((x, i) => {
    if (dq[head] === i - k) head++; // left the window
    while (dq.length > head && xs[dq.at(-1)!] <= x) {
      dq.pop();
    }
    dq.push(i);
    if (i >= k - 1) out.push(xs[dq[head]]);
  });
  return out;
}
 
windowMax([1, 3, -1, -3, 5, 3, 6, 7], 3);
// [3, 3, 5, 5, 6, 7]