Patterns

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// Variant A: opposite ends. Find a pair summing to the target.
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++;        // need more: only the left can grow
    else hi--;                     // need less: only the right can shrink
  }
  return null;
}

// Variant B: same direction. Keep only what passes, in place.
function removeValue(nums, value) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== value) nums[write++] = nums[read];
  }
  return write;                    // the new logical length
}

// Variant C: different speeds. Find the middle of a linked list.
function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}

console.log(twoSumSorted([2, 7, 11, 15], 9));      // [0,1]
console.log(twoSumSorted([2, 7, 11, 15], 100));    // null

const arr = [3, 2, 2, 3, 4];
console.log('kept', removeValue(arr, 3), 'of 5 ->', arr.slice(0, removeValue([3, 2, 2, 3, 4], 3)));

const list = { v: 1, next: { v: 2, next: { v: 3, next: { v: 4, next: null } } } };
console.log('middle of 1-2-3-4:', middleNode(list).v);   // 3, the second middle

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// Variable window, longest valid: shrink until legal, then measure.
function longestWithAtMostKDistinct(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) {                 // too many distinct: shrink
      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);   // record AFTER it is legal
  }
  return best;
}

// Variable window, shortest valid: record while legal, 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) {                    // legal: record, then shrink
      best = Math.min(best, right - left + 1);
      sum -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

// Fixed window: no inner loop at all.
function maxSumOfSize(nums, k) {
  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];      // one in, one out
    best = Math.max(best, sum);
  }
  return best;
}

console.log(longestWithAtMostKDistinct('eceba', 2));        // 3, "ece"
console.log(longestWithAtMostKDistinct('aa', 1));           // 2
console.log(shortestSumAtLeast([2, 3, 1, 2, 4, 3], 7));     // 2, [4,3]
console.log(shortestSumAtLeast([1, 1, 1], 99));             // 0, impossible
console.log(maxSumOfSize([2, 1, 5, 1, 3, 2], 3));           // 9

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// 1. Range sums in O(1) after an O(n) build.
function buildPrefix(nums) {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;                            // prefix[0] = 0 removes every edge case
}
const rangeSum = (prefix, lo, hi) => prefix[hi + 1] - prefix[lo];

// 2. Count subarrays summing to k. Works with negatives; a window does not.
function countSubarraysWithSum(nums, k) {
  const seen = new Map([[0, 1]]);           // one empty prefix, sum 0
  let running = 0, count = 0;

  for (const n of nums) {
    running += n;
    count += seen.get(running - k) || 0;    // every earlier prefix that completes k
    seen.set(running, (seen.get(running) || 0) + 1);
  }
  return count;
}

// 3. Difference array: many range updates, then one pass to materialise.
function applyRangeUpdates(length, updates) {
  const delta = new Array(length + 1).fill(0);
  for (const [lo, hi, amount] of updates) {
    delta[lo] += amount;
    delta[hi + 1] -= amount;                // cancel just past the end
  }
  const out = [];
  let running = 0;
  for (let i = 0; i < length; i++) { running += delta[i]; out.push(running); }
  return out;
}

const prefix = buildPrefix([3, 1, 4, 1, 5, 9]);
console.log('sum of 1..3:', rangeSum(prefix, 1, 3));     // 6
console.log('sum of 0..5:', rangeSum(prefix, 0, 5));     // 23
console.log(countSubarraysWithSum([1, 1, 1], 2));        // 2
console.log(countSubarraysWithSum([1, -1, 0], 0));       // 3
console.log(applyRangeUpdates(5, [[1, 3, 2], [0, 1, 1]]));  // [1,3,2,2,0]

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// Shape 1: seen-before, in one pass.
function firstDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return n;
    seen.add(n);
  }
  return null;
}

// Shape 2: frequency counter, then read the answer off it.
function firstUniqueChar(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  for (let i = 0; i < s.length; i++) if (counts.get(s[i]) === 1) return i;
  return -1;
}

// Shape 3: group by a canonical key. The key IS the insight.
function groupAnagrams(words) {
  const groups = new Map();
  for (const word of words) {
    const key = [...word].sort().join('');       // canonical form
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

// Shape 4: map a value to where you saw it, so you can pair them up.
function twoSumUnsorted(nums, target) {
  const indexOf = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (indexOf.has(target - nums[i])) return [indexOf.get(target - nums[i]), i];
    indexOf.set(nums[i], i);                     // set AFTER checking, or n+n=target lies
  }
  return null;
}

console.log(firstDuplicate([2, 1, 3, 1, 4]));                    // 1
console.log(firstUniqueChar('leetcode'));                        // 0
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat']));  // 2 groups
console.log(twoSumUnsorted([3, 2, 4], 6));                       // [1,2]
console.log(twoSumUnsorted([3, 3], 6));                          // [0,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// Form 1: exact match in a sorted array.
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);         // no overflow, and 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 position where a predicate becomes true. The workhorse.
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 not found
}

// Form 3: binary search on the answer.
// "What is the smallest capacity that ships everything within d days?"
function shipWithinDays(weights, days) {
  const feasible = (capacity) => {
    let need = 1, load = 0;
    for (const w of weights) {
      if (load + w > capacity) { need++; load = 0; }
      load += w;
    }
    return need <= days;
  };

  // The answer is somewhere between the biggest single item and the total.
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;               // works: try smaller
    else lo = mid + 1;                         // fails: must go bigger
  }
  return lo;
}

console.log(search([-1, 0, 3, 5, 9, 12], 9));            // 4
console.log(search([-1, 0, 3, 5, 9, 12], 2));            // -1
console.log(lowerBound([1, 2, 2, 2, 3], 2));             // 1, first 2
console.log(lowerBound([1, 3, 5], 4));                   // 2, where 4 would go
console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5));  // 15
console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3));      // 6

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// Greedy after sorting by end time: the maximum non-overlapping set.
function maxNonOverlapping(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);   // by END
  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) { count++; lastEnd = end; }
  }
  return count;
}

// Greedy after sorting by size: two pointers from both ends.
function rescueBoats(people, limit) {
  const sorted = [...people].sort((a, b) => a - b);
  let boats = 0, lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    if (sorted[lo] + sorted[hi] <= limit) lo++;   // lightest rides along
    hi--;                                          // heaviest always boards
    boats++;
  }
  return boats;
}

// The insight is sometimes the comparator itself.
function largestConcatenation(nums) {
  const parts = nums.map(String).sort((a, b) => (b + a).localeCompare(a + b));
  const joined = parts.join('');
  return joined[0] === '0' ? '0' : joined;        // all zeros collapse
}

console.log(maxNonOverlapping([[1, 4], [3, 5], [0, 6], [5, 7], [8, 11]]));  // 3
console.log(rescueBoats([3, 2, 2, 1], 3));            // 3
console.log(rescueBoats([1, 2], 3));                  // 1
console.log(largestConcatenation([3, 30, 34, 5, 9]));  // '9534330'
console.log(largestConcatenation([0, 0]));             // '0'

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
33function merge(intervals) {
  if (intervals.length === 0) return [];
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);   // by START
  const out = [sorted[0].slice()];                             // copy the input

  for (let i = 1; i < sorted.length; i++) {
    const open = out[out.length - 1];
    if (sorted[i][0] <= open[1]) {
      open[1] = Math.max(open[1], sorted[i][1]);   // Math.max is NOT optional
    } else {
      out.push(sorted[i].slice());
    }
  }
  return out;
}

// Sweep line: peak concurrency, without merging anything.
function peakConcurrent(intervals) {
  const events = [];
  for (const [s, e] of intervals) { events.push([s, 1]); events.push([e, -1]); }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // -1 before +1 on ties

  let active = 0, peak = 0;
  for (const [, delta] of events) { active += delta; peak = Math.max(peak, active); }
  return peak;
}

console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));   // [[1,6],[8,10],[15,18]]
console.log(merge([[1, 10], [2, 3]]));                     // [[1,10]] contained
console.log(merge([[1, 4], [4, 5]]));                      // [[1,5]] touching
console.log(peakConcurrent([[0, 30], [5, 10], [15, 20]]));  // 2
console.log(peakConcurrent([[1, 5], [2, 6], [3, 7]]));      // 3
console.log(peakConcurrent([[1, 2], [2, 3]]));              // 1, only touching

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// Next greater element to the right, for every index.
function nextGreater(nums) {
  const answer = new Array(nums.length).fill(-1);
  const stack = [];                          // indices, values decreasing

  for (let i = 0; i < nums.length; i++) {
    // nums[i] is the next greater element for everything smaller on the stack.
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      answer[stack.pop()] = nums[i];         // the pop resolves that index
    }
    stack.push(i);
  }
  return answer;                             // anything left never found one
}

// Same skeleton, different bookkeeping: largest rectangle in a histogram.
function largestRectangle(heights) {
  const stack = [];                          // indices, heights increasing
  let best = 0;
  const bars = [...heights, 0];              // sentinel 0 flushes the stack

  for (let i = 0; i < bars.length; i++) {
    while (stack.length && bars[stack[stack.length - 1]] >= bars[i]) {
      const height = bars[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

// Distances rather than values: days until a warmer temperature.
function daysUntilWarmer(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop();
      answer[j] = i - j;                     // this is why we store indices
    }
    stack.push(i);
  }
  return answer;
}

console.log(nextGreater([2, 1, 2, 4, 3]));                    // [4,2,4,-1,-1]
console.log(largestRectangle([2, 1, 5, 6, 2, 3]));            // 10
console.log(largestRectangle([2, 4]));                        // 4
console.log(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]));  // [1,1,4,2,1,1,0,0]

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// A binary heap, because JavaScript has no built-in priority queue.
class Heap {
  constructor(compare = (a, b) => a - b) { this.a = []; this.compare = compare; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }

  push(v) {
    this.a.push(v);
    let i = this.a.length - 1;
    while (i > 0) {
      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], last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0;
      for (;;) {
        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;
  }
}

// k largest: a MIN-heap capped at k. The weakest survivor is always on top.
function kLargest(nums, k) {
  const heap = new Heap();                        // min-heap
  for (const n of nums) {
    heap.push(n);
    if (heap.size > k) heap.pop();                // evict the smallest
  }
  const out = [];
  while (heap.size) out.push(heap.pop());
  return out.reverse();
}

// k most frequent: count first, then heap on the counts.
function topKFrequent(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);

  const heap = new Heap((a, b) => a[1] - b[1]);   // compare by count
  for (const entry of counts) {
    heap.push(entry);
    if (heap.size > k) heap.pop();
  }
  return heap.a.map(e => e[0]).sort((a, b) => counts.get(b) - counts.get(a));
}

console.log(kLargest([3, 2, 1, 5, 6, 4], 2));                  // [6,5]
console.log(kLargest([7], 1));                                 // [7]
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));              // [1,2]
console.log(topKFrequent([4, 4, 4, 5, 5, 6], 1));              // [4]

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
57function toList(values) {
  const dummy = { v: null, next: null };
  let tail = dummy;
  for (const v of values) { tail.next = { v, next: null }; tail = tail.next; }
  return dummy.next;
}
const toArray = (head) => { const out = []; for (let n = head; n; n = n.next) out.push(n.v); return out; };

// Reverse. Save next BEFORE you overwrite it.
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;      // save it or lose the rest of the list
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;                   // the old tail is the new head
}

// Merge two sorted lists. The dummy head removes every special case.
function mergeSorted(a, b) {
  const dummy = { v: null, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.v <= b.v) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;            // one of them still has nodes
  return dummy.next;
}

// Cycle detection, and where the cycle begins.
function cycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {         // they met, so there is a loop
      let walk = head;
      while (walk !== slow) { walk = walk.next; slow = slow.next; }
      return walk;               // distance from head equals distance from meeting
    }
  }
  return null;
}

console.log(toArray(reverse(toList([1, 2, 3, 4, 5]))));       // [5,4,3,2,1]
console.log(toArray(reverse(toList([1]))));                   // [1]
console.log(toArray(reverse(toList([]))));                    // []
console.log(toArray(mergeSorted(toList([1, 3, 5]), toList([2, 4]))));  // [1,2,3,4,5]

const looped = toList([3, 2, 0, -4]);
looped.next.next.next.next = looped.next;                      // tail -> index 1
console.log('cycle starts at value:', cycleStart(looped).v);   // 2
console.log('no cycle:', cycleStart(toList([1, 2, 3])));       // null

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
53function buildTree(values) {
  // Level-order array, null for a missing child.
  if (!values.length || values[0] === null) return null;
  const root = { v: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  while (i < values.length) {
    const node = queue.shift();
    if (i < values.length && values[i] !== null) { node.left = { v: values[i], left: null, right: null }; queue.push(node.left); }
    i++;
    if (i < values.length && values[i] !== null) { node.right = { v: values[i], left: null, right: null }; queue.push(node.right); }
    i++;
  }
  return root;
}

// In-order: on a BST this comes out sorted.
function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.v);
  inorder(node.right, out);
  return out;
}

// Post-order, the important shape: return one thing, accumulate another.
function diameter(root) {
  let best = 0;

  function height(node) {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    best = Math.max(best, left + right);      // path THROUGH this node
    return 1 + Math.max(left, right);         // height, for the parent
  }

  height(root);
  return best;
}

// Validity needs a range passed downward, not a local check.
function isValidBST(node, low = -Infinity, high = Infinity) {
  if (!node) return true;
  if (node.v <= low || node.v >= high) return false;
  return isValidBST(node.left, low, node.v) && isValidBST(node.right, node.v, high);
}

const tree = buildTree([1, 2, 3, 4, 5]);
console.log('in-order:', inorder(tree));                       // [4,2,5,1,3]
console.log('diameter:', diameter(tree));                      // 3
console.log('valid BST [2,1,3]:', isValidBST(buildTree([2, 1, 3])));      // true
console.log('valid BST [5,1,4,null,null,3,6]:', isValidBST(buildTree([5, 1, 4, null, null, 3, 6])));  // 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// Grid BFS with level counting. The template for "fewest steps".
function shortestPath(grid) {
  const rows = grid.length, cols = grid[0].length;
  if (grid[0][0] === 1) return -1;

  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let queue = [[0, 0]];
  seen[0][0] = true;                          // mark on ENQUEUE
  let steps = 0;

  while (queue.length) {
    const next = [];
    for (const [r, c] of queue) {             // one whole level
      if (r === rows - 1 && c === cols - 1) return steps;
      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 || seen[nr][nc]) continue;
        seen[nr][nc] = true;
        next.push([nr, nc]);
      }
    }
    queue = next;
    steps++;
  }
  return -1;
}

// Multi-source: seed every start before the loop.
function distanceToNearestZero(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [];

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); }

  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  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 (dist[nr][nc] !== -1) continue;      // already reached, so already closer
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return dist;
}

console.log(shortestPath([[0, 0, 0], [0, 1, 0], [0, 0, 0]]));   // 4
console.log(shortestPath([[0, 1], [1, 0]]));                    // -1
console.log(distanceToNearestZero([[0, 0, 0], [0, 1, 0], [1, 1, 1]]));
// [[0,0,0],[0,1,0],[1,2,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
32function topologicalOrder(nodeCount, edges) {
  // edges are [from, to]: from must come before to.
  const adjacency = Array.from({ length: nodeCount }, () => []);
  const inDegree = new Array(nodeCount).fill(0);

  for (const [from, to] of edges) {
    adjacency[from].push(to);
    inDegree[to]++;
  }

  // Everything with no prerequisites is ready immediately.
  const queue = [];
  for (let n = 0; n < nodeCount; n++) if (inDegree[n] === 0) queue.push(n);

  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    order.push(node);
    for (const next of adjacency[node]) {
      if (--inDegree[next] === 0) queue.push(next);   // now unblocked
    }
  }

  // Fewer than every node means a cycle swallowed the rest.
  return order.length === nodeCount ? order : null;
}

console.log(topologicalOrder(4, [[0, 1], [0, 2], [1, 3], [2, 3]]));   // [0,1,2,3]
console.log(topologicalOrder(2, [[1, 0]]));                          // [1,0]
console.log(topologicalOrder(2, [[0, 1], [1, 0]]));                  // null, cycle
console.log(topologicalOrder(3, []));                                // [0,1,2]
console.log('possible?', topologicalOrder(2, [[0, 1], [1, 0]]) !== null);   // 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
45class 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 straight at the root.
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  union(a, b) {
    let rootA = this.find(a), rootB = this.find(b);
    if (rootA === rootB) return false;              // already together

    // Union by size: hang the smaller tree under the bigger one.
    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;                                     // a real merge happened
  }

  connected(a, b) { return this.find(a) === this.find(b); }
}

const uf = new UnionFind(6);
uf.union(0, 1); uf.union(1, 2); uf.union(4, 5);
console.log('0 and 2 connected:', uf.connected(0, 2));    // true
console.log('0 and 4 connected:', uf.connected(0, 4));    // false
console.log('components:', uf.groups);                    // 3: {0,1,2} {3} {4,5}

// The boolean return of union() detects a cycle in one pass.
function hasCycle(n, edges) {
  const find = new UnionFind(n);
  for (const [a, b] of edges) if (!find.union(a, b)) return true;
  return false;
}
console.log('cycle in a triangle:', hasCycle(3, [[0, 1], [1, 2], [2, 0]]));   // true
console.log('cycle in a line:    ', 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// The template. Everything below is this with different details.
function subsets(nums) {
  const results = [];

  function walk(start, current) {
    results.push([...current]);              // COPY, or every result aliases
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);                 // choose
      walk(i + 1, current);                  // explore; i + 1 = no reuse
      current.pop();                         // un-choose
    }
  }

  walk(0, []);
  return results;
}

// Permutations: start from 0 each time, track what is taken.
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++) {
      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;
}

// Reuse allowed, plus a prune that makes it practical.
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, so everything after is too big
      current.push(sorted[i]);
      walk(i, current, remaining - sorted[i]);   // i, not i + 1: reuse allowed
      current.pop();
    }
  }

  walk(0, [], target);
  return results;
}

console.log(subsets([1, 2, 3]).length, 'subsets of 3');       // 8
console.log(permutations([1, 2, 3]).length, 'permutations');   // 6
console.log(combinationSum([2, 3, 6, 7], 7));                  // [[2,2,3],[7]]
console.log(combinationSum([2], 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// Step 1: the honest recursion, memoised. Usually where you should stop.
function coinChangeMemo(coins, amount, memo = new Map()) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  if (memo.has(amount)) return memo.get(amount);

  let best = Infinity;
  for (const coin of coins) {
    best = Math.min(best, 1 + coinChangeMemo(coins, amount - coin, memo));
  }
  memo.set(amount, best);
  return best;
}

// Step 2: the same recurrence bottom-up. No recursion, no stack limit.
function coinChangeTable(coins, amount) {
  const best = new Array(amount + 1).fill(Infinity);
  best[0] = 0;                                  // zero coins make zero
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) best[a] = Math.min(best[a], best[a - coin] + 1);
    }
  }
  return best[amount] === Infinity ? -1 : best[amount];
}

// Step 3: when a row only needs the row before it, keep two variables.
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.
function longestCommonSubsequence(a, b) {
  const table = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      table[i][j] = a[i - 1] === b[j - 1]
        ? table[i - 1][j - 1] + 1                // matched: extend the diagonal
        : Math.max(table[i - 1][j], table[i][j - 1]);   // skip one or the other
    }
  }
  return table[a.length][b.length];
}

console.log(coinChangeTable([1, 3, 4], 6));            // 2, not 3
console.log(coinChangeTable([2], 3));                  // -1
console.log(coinChangeMemo([1, 3, 4], 6));             // 2
console.log(climbStairs(10));                          // 89
console.log(longestCommonSubsequence('abcde', 'ace')); // 3
console.log(longestCommonSubsequence('abc', 'def'));   // 0