Templates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Form 1: exact match. Inclusive bounds, <= in the condition.
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);      // no overflow, floors correctly
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;   // both branches EXCLUDE mid
    else hi = mid - 1;
  }
  return -1;
}

// Form 2: leftmost index where nums[i] >= target. The one to know cold.
function lowerBound(nums, target) {
  let lo = 0, hi = nums.length;             // hi is EXCLUSIVE here
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;                          // keep mid as a candidate
  }
  return lo;                                 // insertion point if absent
}

// Rightmost: the first index where nums[i] > target.
function upperBound(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Form 3: binary search the ANSWER, not the input.
// feasible must be monotonic: false ... false true ... true.
function firstFeasible(lo, hi, feasible) {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;            // works: try smaller
    else lo = mid + 1;                       // fails: go bigger
  }
  return lo;
}

test('exact hit', search([1, 3, 5, 7], 5), 2);
test('exact miss', search([1, 3, 5, 7], 4), -1);
test('lowerBound on duplicates', lowerBound([1, 2, 2, 2, 3], 2), 1);
test('lowerBound insertion point', lowerBound([1, 3, 5], 4), 2);
test('upperBound on duplicates', upperBound([1, 2, 2, 2, 3], 2), 4);
test('count of a value', upperBound([1, 2, 2, 2, 3], 2) - lowerBound([1, 2, 2, 2, 3], 2), 3);
test('answer-space search', firstFeasible(1, 100, x => x * x >= 50), 8);
test('empty array', search([], 1), -1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Graph BFS with distances. Never use queue.shift() — it is O(n).
function bfs(start, neighboursOf) {
  const dist = new Map([[start, 0]]);
  const queue = [start];

  for (let head = 0; head < queue.length; head++) {   // head index, not shift()
    const node = queue[head];
    for (const next of neighboursOf(node)) {
      if (dist.has(next)) continue;                    // already reached
      dist.set(next, dist.get(node) + 1);              // mark on ENQUEUE
      queue.push(next);
    }
  }
  return dist;
}

// Level-by-level, for "fewest steps" questions.
function bfsLevels(start, neighboursOf, isGoal) {
  const seen = new Set([start]);
  let level = [start], steps = 0;

  while (level.length) {
    for (const node of level) if (isGoal(node)) return steps;

    const next = [];
    for (const node of level) {
      for (const n of neighboursOf(node)) {
        if (seen.has(n)) continue;
        seen.add(n);
        next.push(n);
      }
    }
    level = next;
    steps++;
  }
  return -1;
}

// Grid BFS, multi-source. Seed EVERY start before the loop.
function bfsGrid(grid, sources) {
  const rows = grid.length, cols = grid[0].length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [];

  for (const [r, c] of sources) { dist[r][c] = 0; queue.push([r, c]); }

  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1 || dist[nr][nc] !== -1) continue;   // wall or seen
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return dist;
}

const graph = { a: ['b', 'c'], b: ['d'], c: ['d'], d: [], e: [] };
const distances = bfs('a', n => graph[n] || []);
test('distance to d', distances.get('d'), 2);
test('unreachable node absent', distances.has('e'), false);
test('start is zero', distances.get('a'), 0);
test('level search', bfsLevels('a', n => graph[n] || [], n => n === 'd'), 2);
test('goal is the start', bfsLevels('a', n => graph[n] || [], n => n === 'a'), 0);
test('no path', bfsLevels('a', n => graph[n] || [], n => n === 'e'), -1);

const grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]];
test('grid distances', bfsGrid(grid, [[0, 0]])[2][2], 4);
test('wall stays unreached', bfsGrid(grid, [[0, 0]])[1][1], -1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Recursive. Mark on entry, or a cycle loops forever.
function dfs(start, neighboursOf, seen = new Set()) {
  if (seen.has(start)) return seen;
  seen.add(start);                                 // mark BEFORE recursing
  for (const next of neighboursOf(start)) dfs(next, neighboursOf, seen);
  return seen;
}

// Iterative, when recursion depth is a risk.
function dfsIterative(start, neighboursOf) {
  const seen = new Set();
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (seen.has(node)) continue;                  // may be queued twice; fine
    seen.add(node);
    for (const next of neighboursOf(node)) if (!seen.has(next)) stack.push(next);
  }
  return seen;
}

// Cycle detection in a DIRECTED graph needs three states, not two.
function hasCycle(nodes, neighboursOf) {
  const state = new Map();                          // unset | 'open' | 'done'

  function walk(node) {
    if (state.get(node) === 'open') return true;    // back edge: a cycle
    if (state.get(node) === 'done') return false;   // fully explored already

    state.set(node, 'open');
    for (const next of neighboursOf(node)) if (walk(next)) return true;
    state.set(node, 'done');
    return false;
  }

  return nodes.some(walk);
}

// Grid flood fill. Mutating the grid is the cheapest visited-set there is.
function floodFill(grid, r, c, target) {
  if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return 0;
  if (grid[r][c] !== target) return 0;
  grid[r][c] = 0;                                   // mark before recursing
  return 1 + floodFill(grid, r + 1, c, target) + floodFill(grid, r - 1, c, target)
           + floodFill(grid, r, c + 1, target) + floodFill(grid, r, c - 1, target);
}

const g = { a: ['b'], b: ['c'], c: [], d: ['d'] };
test('reaches everything', [...dfs('a', n => g[n] || [])].sort(), ['a', 'b', 'c']);
test('iterative agrees', [...dfsIterative('a', n => g[n] || [])].sort(), ['a', 'b', 'c']);
test('self loop is a cycle', hasCycle(['d'], n => g[n] || []), true);
test('a chain is not', hasCycle(['a', 'b', 'c'], n => g[n] || []), false);

const cyc = { x: ['y'], y: ['z'], z: ['x'] };
test('three-cycle detected', hasCycle(['x'], n => cyc[n] || []), true);

// A diamond is not a cycle, though a two-state check would wrongly say it is.
const diamond = { p: ['q', 'r'], q: ['s'], r: ['s'], s: [] };
test('diamond is acyclic', hasCycle(['p'], n => diamond[n] || []), false);

test('flood fill size', floodFill([[1, 1, 0], [1, 0, 0]], 0, 0, 1), 3);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

class Heap {
  // Pass (a, b) => b - a to get a max-heap instead.
  constructor(compare = (a, b) => a - b) { this.a = []; this.compare = compare; }

  get size() { return this.a.length; }
  peek() { return this.a[0]; }

  push(value) {
    this.a.push(value);
    let i = this.a.length - 1;
    while (i > 0) {                                  // sift up
      const parent = (i - 1) >> 1;
      if (this.compare(this.a[parent], this.a[i]) <= 0) break;
      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];
      i = parent;
    }
  }

  pop() {
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0;
      for (;;) {                                     // sift down
        const l = 2 * i + 1, r = l + 1;
        let best = i;
        if (l < this.a.length && this.compare(this.a[l], this.a[best]) < 0) best = l;
        if (r < this.a.length && this.compare(this.a[r], this.a[best]) < 0) best = r;
        if (best === i) break;
        [this.a[best], this.a[i]] = [this.a[i], this.a[best]];
        i = best;
      }
    }
    return top;
  }
}

// To keep the k LARGEST, cap a MIN-heap at k. The weakest survivor is on top.
function kLargest(nums, k) {
  const heap = new Heap();
  for (const n of nums) { heap.push(n); if (heap.size > k) heap.pop(); }
  const out = [];
  while (heap.size) out.push(heap.pop());
  return out.reverse();
}

const h = new Heap();
for (const v of [5, 1, 4, 1, 5, 9, 2, 6]) h.push(v);
test('min on top', h.peek(), 1);
const drained = [];
while (h.size) drained.push(h.pop());
test('pops in order', drained, [1, 1, 2, 4, 5, 5, 6, 9]);

const maxHeap = new Heap((a, b) => b - a);
for (const v of [3, 7, 1]) maxHeap.push(v);
test('max-heap on top', maxHeap.peek(), 7);

test('k largest', kLargest([3, 2, 1, 5, 6, 4], 2), [6, 5]);
test('k of one', kLargest([1], 1), [1]);

// Objects work too, with a comparator on a field.
const byCount = new Heap((a, b) => a.count - b.count);
byCount.push({ name: 'a', count: 5 });
byCount.push({ name: 'b', count: 2 });
test('object comparator', byCount.peek().name, 'b');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.groups = n;
  }

  find(x) {
    // Path compression: point everything on the way up at its grandparent.
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  // Returns false when they were already connected — which is a cycle.
  union(a, b) {
    let rootA = this.find(a), rootB = this.find(b);
    if (rootA === rootB) return false;

    // Union by size: hang the smaller tree under the larger.
    if (this.size[rootA] < this.size[rootB]) [rootA, rootB] = [rootB, rootA];
    this.parent[rootB] = rootA;
    this.size[rootA] += this.size[rootB];
    this.groups--;
    return true;
  }

  connected(a, b) { return this.find(a) === this.find(b); }
  groupSize(x) { return this.size[this.find(x)]; }
}

const uf = new UnionFind(6);
uf.union(0, 1); uf.union(1, 2); uf.union(4, 5);
test('transitively connected', uf.connected(0, 2), true);
test('separate groups', uf.connected(0, 4), false);
test('component count', uf.groups, 3);
test('group size', uf.groupSize(0), 3);
test('singleton size', uf.groupSize(3), 1);
test('re-union returns false', uf.union(0, 2), false);
test('count unchanged after a no-op union', uf.groups, 3);

// Cycle detection falls out of the return value.
function hasCycle(n, edges) {
  const find = new UnionFind(n);
  for (const [a, b] of edges) if (!find.union(a, b)) return true;
  return false;
}
test('triangle has a cycle', hasCycle(3, [[0, 1], [1, 2], [2, 0]]), true);
test('path does not', hasCycle(3, [[0, 1], [1, 2]]), false);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// The skeleton. Everything below is this with different details.
function subsets(nums) {
  const results = [];
  function walk(start, current) {
    results.push([...current]);                 // COPY, or all results alias
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);                    // choose
      walk(i + 1, current);                     // explore
      current.pop();                            // un-choose
    }
  }
  walk(0, []);
  return results;
}

// i + 1 -> no reuse.  i -> reuse allowed.  from 0 + used[] -> permutations.
function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const results = [];
  function walk(start, current, remaining) {
    if (remaining === 0) { results.push([...current]); return; }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break;         // sorted: prune the whole tail
      current.push(sorted[i]);
      walk(i, current, remaining - sorted[i]);  // i: reuse allowed
      current.pop();
    }
  }
  walk(0, [], target);
  return results;
}

function permutations(nums) {
  const results = [], used = new Array(nums.length).fill(false);
  function walk(current) {
    if (current.length === nums.length) { results.push([...current]); return; }
    for (let i = 0; i < nums.length; i++) {     // from 0 every time
      if (used[i]) continue;
      used[i] = true; current.push(nums[i]);
      walk(current);
      current.pop(); used[i] = false;           // undo BOTH pieces of state
    }
  }
  walk([]);
  return results;
}

// Duplicates: sort, then skip repeats at the SAME level. i > start, not i > 0.
function subsetsWithDup(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const results = [];
  function walk(start, current) {
    results.push([...current]);
    for (let i = start; i < sorted.length; i++) {
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      current.push(sorted[i]);
      walk(i + 1, current);
      current.pop();
    }
  }
  walk(0, []);
  return results;
}

test('subsets count', subsets([1, 2, 3]).length, 8);
test('empty input still yields one subset', subsets([]), [[]]);
test('combination sum', combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]);
test('permutation count', permutations([1, 2, 3]).length, 6);
test('duplicates deduped', subsetsWithDup([1, 2, 2]).length, 6);
test('i > start keeps [2,2]', JSON.stringify(subsetsWithDup([1, 2, 2])).includes('[2,2]'), true);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Step 1: honest recursion + a cache. Usually enough, and hardest to get wrong.
function memoise(fn) {
  const cache = new Map();
  return function wrapped(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const value = fn(wrapped, ...args);         // pass the wrapper for recursion
    cache.set(key, value);
    return value;
  };
}

const coinsMemo = memoise((self, amount, coins) => {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  let best = Infinity;
  for (const c of coins) best = Math.min(best, 1 + self(amount - c, coins));
  return best;
});

// Step 2: bottom-up table. Same recurrence, no stack limit.
function coinsTable(coins, amount) {
  const best = new Array(amount + 1).fill(Infinity);
  best[0] = 0;                                  // the base case IS the algorithm
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1);
  return best[amount] === Infinity ? -1 : best[amount];
}

// Step 3: collapse the table when only the previous row is needed.
function climbStairs(n) {
  let twoBack = 1, oneBack = 1;
  for (let i = 2; i <= n; i++) {
    const current = oneBack + twoBack;
    twoBack = oneBack;
    oneBack = current;
  }
  return oneBack;                                // O(1) space
}

// Two sequences: a 2D table, one axis each. Row/column 0 = empty prefix.
function editDistance(a, b) {
  const t = Array.from({ length: a.length + 1 }, (_, i) =>
    Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)));

  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      t[i][j] = a[i - 1] === b[j - 1]
        ? t[i - 1][j - 1]                                        // free match
        : 1 + Math.min(t[i - 1][j], t[i][j - 1], t[i - 1][j - 1]); // del, ins, sub

  return t[a.length][b.length];
}

test('memoised coins', coinsMemo(11, [1, 2, 5]), 3);
test('greedy would fail', coinsTable([1, 3, 4], 6), 2);
test('impossible amount', coinsTable([2], 3), -1);
test('zero amount', coinsTable([1], 0), 0);
test('stairs', climbStairs(10), 89);
test('stairs base case', climbStairs(0), 1);
test('edit distance', editDistance('horse', 'ros'), 3);
test('identical strings', editDistance('abc', 'abc'), 0);
test('one empty', editDistance('', 'abc'), 3);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

function TreeNode(val, left = null, right = null) {
  this.val = val; this.left = left; this.right = right;
}

const preorder = (n, out = []) => { if (n) { out.push(n.val); preorder(n.left, out); preorder(n.right, out); } return out; };
const inorder  = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
const postorder = (n, out = []) => { if (n) { postorder(n.left, out); postorder(n.right, out); out.push(n.val); } return out; };

// Iterative in-order: dive left, visit, go right. Needed for early exit.
function inorderIterative(root) {
  const out = [], stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    out.push(node.val);
    node = node.right;
  }
  return out;
}

// Level order. Swapping arrays keeps level boundaries obvious.
function levelOrder(root) {
  if (!root) return [];
  const out = [];
  let level = [root];
  while (level.length) {
    out.push(level.map(n => n.val));
    const next = [];
    for (const n of level) { if (n.left) next.push(n.left); if (n.right) next.push(n.right); }
    level = next;
  }
  return out;
}

// THE shape: return one thing to the parent, accumulate another outside.
function diameter(root) {
  let best = 0;
  function height(node) {
    if (!node) return 0;
    const left = height(node.left), right = height(node.right);
    best = Math.max(best, left + right);       // the path turning here
    return 1 + Math.max(left, right);           // the height, for the parent
  }
  height(root);
  return best;
}

// BST validity: the range comes from every ancestor, not just the parent.
function isValidBST(node, low = -Infinity, high = Infinity) {
  if (!node) return true;
  if (node.val <= low || node.val >= high) return false;
  return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high);
}

//       4
//      / \
//     2   6
//    / \
//   1   3
const t = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));

test('preorder', preorder(t), [4, 2, 1, 3, 6]);
test('inorder is sorted for a BST', inorder(t), [1, 2, 3, 4, 6]);
test('postorder', postorder(t), [1, 3, 2, 6, 4]);
test('iterative matches recursive', inorderIterative(t), inorder(t));
test('level order', levelOrder(t), [[4], [2, 6], [1, 3]]);
test('diameter', diameter(t), 3);
test('valid BST', isValidBST(t), true);
test('empty tree', levelOrder(null), []);

// A node smaller than its parent but violating a grandparent.
const bad = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
test('grandparent violation caught', isValidBST(bad), false);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

function ListNode(val, next = null) { this.val = val; this.next = next; }

const toList = (values) => {
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of values) { tail.next = new ListNode(v); tail = tail.next; }
  return dummy.next;
};
const toArray = (head) => { const out = []; for (let n = head; n; n = n.next) out.push(n.val); return out; };

function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;      // SAVE before overwriting, or lose the tail
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

function middle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;                    // for even lengths, the SECOND middle
}

function mergeSorted(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

function cycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {                        // met, so there is a loop
      let walk = head;
      while (walk !== slow) { walk = walk.next; slow = slow.next; }
      return walk;                              // the entry point
    }
  }
  return null;
}

// Dummy head pattern: removing a node, including possibly the first.
function removeValue(head, value) {
  const dummy = new ListNode(0, head);
  let node = dummy;
  while (node.next) {
    if (node.next.val === value) node.next = node.next.next;
    else node = node.next;
  }
  return dummy.next;
}

test('reverse', toArray(reverse(toList([1, 2, 3]))), [3, 2, 1]);
test('reverse empty', toArray(reverse(toList([]))), []);
test('middle of odd', middle(toList([1, 2, 3])).val, 2);
test('middle of even', middle(toList([1, 2, 3, 4])).val, 3);
test('merge', toArray(mergeSorted(toList([1, 3]), toList([2, 4]))), [1, 2, 3, 4]);
test('remove the head', toArray(removeValue(toList([1, 2, 3]), 1)), [2, 3]);
test('remove several', toArray(removeValue(toList([1, 2, 1, 2]), 2)), [1, 1]);
test('remove everything', toArray(removeValue(toList([7, 7]), 7)), []);
test('no cycle', cycleStart(toList([1, 2, 3])), null);

const looped = toList([1, 2, 3, 4]);
looped.next.next.next.next = looped.next;
test('cycle entry', cycleStart(looped).val, 2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Longest valid: shrink until legal, THEN record.
function longestAtMostKDistinct(s, k) {
  const counts = new Map();
  let best = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    while (counts.size > k) {
      const out = s[left++];
      counts.set(out, counts.get(out) - 1);
      if (counts.get(out) === 0) counts.delete(out);
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

// Shortest valid: record WHILE legal, then keep shrinking.
function shortestSumAtLeast(nums, target) {
  let best = Infinity, sum = 0, left = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

// Fixed size: one in, one out, no inner loop.
function maxSumOfSize(nums, k) {
  if (nums.length < k) return 0;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k];
    best = Math.max(best, sum);
  }
  return best;
}

// Opposite ends. Sortedness tells you which pointer must move.
function twoSumSorted(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++; else hi--;
  }
  return null;
}

// Same direction: a write pointer compacts in place.
function compact(nums, keep) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (keep(nums[read])) nums[write++] = nums[read];
  }
  return write;                                 // the new logical length
}

test('longest with 2 distinct', longestAtMostKDistinct('eceba', 2), 3);
test('shortest at least 7', shortestSumAtLeast([2, 3, 1, 2, 4, 3], 7), 2);
test('impossible target', shortestSumAtLeast([1, 1], 99), 0);
test('fixed window', maxSumOfSize([2, 1, 5, 1, 3, 2], 3), 9);
test('window longer than input', maxSumOfSize([1], 3), 0);
test('two sum sorted', twoSumSorted([2, 7, 11, 15], 9), [0, 1]);
test('no pair', twoSumSorted([1, 2], 99), null);

const arr = [1, 0, 2, 0, 3];
test('compact returns the length', compact(arr, x => x !== 0), 3);
test('compacted prefix', arr.slice(0, 3), [1, 2, 3]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52const same = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const test = (name, got, want) => console.log(
  (same(got, want) ? 'ok   ' : 'FAIL ') + name +
  (same(got, want) ? '' : `  got ${JSON.stringify(got)}, want ${JSON.stringify(want)}`)
);

// Sorting numbers. The default comparator sorts as STRINGS.
const ascending = (a) => [...a].sort((x, y) => x - y);
const byThenBy = (a) => [...a].sort((x, y) => x.age - y.age || x.name.localeCompare(y.name));

// Frequency counting.
const countBy = (items) => {
  const counts = new Map();
  for (const i of items) counts.set(i, (counts.get(i) || 0) + 1);
  return counts;
};

// A 26-letter signature, for anagram grouping.
const letterKey = (word) => {
  const counts = new Array(26).fill(0);
  for (const ch of word) counts[ch.charCodeAt(0) - 97]++;
  return counts.join(',');
};

// A grid, and flattening a cell into one number for a visited Set.
const makeGrid = (rows, cols, fill = 0) =>
  Array.from({ length: rows }, () => new Array(cols).fill(fill));
const cellKey = (r, c, cols) => r * cols + c;

// Modulo that behaves for negative numbers. JavaScript's % keeps the sign.
const mod = (x, n) => ((x % n) + n) % n;

// Integer division that truncates toward zero, matching most languages.
const intDiv = (a, b) => Math.trunc(a / b);

// Swap without a temporary.
const swap = (arr, i, j) => { [arr[i], arr[j]] = [arr[j], arr[i]]; return arr; };

test('numeric sort', ascending([10, 2, 1]), [1, 2, 10]);
test('default sort really is wrong', [10, 2, 1].sort(), [1, 10, 2]);
test('two-key sort', byThenBy([{ age: 2, name: 'b' }, { age: 2, name: 'a' }]).map(p => p.name), ['a', 'b']);
test('counting', [...countBy('aab')], [['a', 2], ['b', 1]]);
test('anagrams share a key', letterKey('eat') === letterKey('tea'), true);
test('non-anagrams do not', letterKey('eat') === letterKey('tan'), false);
test('grid shape', makeGrid(2, 3).length, 2);
test('grid width', makeGrid(2, 3)[0].length, 3);
test('cell key', cellKey(1, 2, 3), 5);
test('negative modulo', mod(-1, 5), 4);
test('plain % is negative', -1 % 5, -1);
test('truncating division', intDiv(-7, 2), -3);
test('floor would differ', Math.floor(-7 / 2), -4);
test('swap', swap([1, 2, 3], 0, 2), [3, 2, 1]);