Problem set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21const 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 containsDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;      // exit early, no need to see the rest
    seen.add(n);
  }
  return false;
}

test('has a duplicate', containsDuplicate([1, 2, 3, 1]), true);
test('all distinct', containsDuplicate([1, 2, 3, 4]), false);
test('immediate repeat', containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]), true);
test('single element', containsDuplicate([7]), false);
test('empty', containsDuplicate([]), false);
test('negatives', containsDuplicate([-1, -2, -1]), 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
26const 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 isAnagram(a, b) {
  if (a.length !== b.length) return false;

  const counts = new Map();
  for (const ch of a) counts.set(ch, (counts.get(ch) || 0) + 1);

  for (const ch of b) {
    const left = counts.get(ch);
    if (!left) return false;           // absent, or already used up
    counts.set(ch, left - 1);
  }
  return true;                          // lengths matched, so nothing can remain
}

test('anagram', isAnagram('anagram', 'nagaram'), true);
test('not an anagram', isAnagram('rat', 'car'), false);
test('different lengths', isAnagram('a', 'ab'), false);
test('both empty', isAnagram('', ''), true);
test('same letters, wrong counts', isAnagram('aabb', 'abbb'), false);
test('unicode', isAnagram('héllo', 'olléh'), true);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22const 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 twoSum(nums, target) {
  const indexOf = new Map();            // value -> index

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i];
    indexOf.set(nums[i], i);            // AFTER the check, or n pairs with itself
  }
  return [];
}

test('basic', twoSum([2, 7, 11, 15], 9), [0, 1]);
test('later in the array', twoSum([3, 2, 4], 6), [1, 2]);
test('equal values', twoSum([3, 3], 6), [0, 1]);
test('negatives', twoSum([-3, 4, 3, 90], 0), [0, 2]);
test('no pair', twoSum([1, 2], 100), []);

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
30const 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 groupAnagrams(words) {
  const groups = new Map();

  for (const word of words) {
    // Count-based key: 26 slots, so building it is linear in the word length.
    const counts = new Array(26).fill(0);
    for (const ch of word) counts[ch.charCodeAt(0) - 97]++;
    const key = counts.join(',');

    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

// Compare as sorted group contents so the test does not depend on ordering.
const shape = (groups) => groups.map(g => [...g].sort()).sort((a, b) => a[0].localeCompare(b[0]));

test('classic', shape(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])),
  [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]);
test('one empty word', shape(groupAnagrams([''])), [['']]);
test('single letter', shape(groupAnagrams(['a'])), [['a']]);
test('no anagrams', shape(groupAnagrams(['abc', 'def'])), [['abc'], ['def']]);
test('empty input', groupAnagrams([]), []);

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
31const 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 topKFrequent(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);

  // A frequency can be at most nums.length, so bucket by count directly.
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [value, count] of counts) buckets[count].push(value);

  const out = [];
  for (let count = buckets.length - 1; count > 0 && out.length < k; count--) {
    for (const value of buckets[count]) {
      out.push(value);
      if (out.length === k) break;
    }
  }
  return out;
}

const sorted = (a) => [...a].sort((x, y) => x - y);

test('two most frequent', sorted(topKFrequent([1, 1, 1, 2, 2, 3], 2)), [1, 2]);
test('k = 1', topKFrequent([1], 1), [1]);
test('all equal counts', sorted(topKFrequent([1, 2, 3], 3)), [1, 2, 3]);
test('k covers everything', sorted(topKFrequent([4, 4, 5], 2)), [4, 5]);
test('negatives', topKFrequent([-1, -1, 2], 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
30const 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 productExceptSelf(nums) {
  const out = new Array(nums.length).fill(1);

  // Pass 1: out[i] becomes the product of everything to the LEFT of i.
  let running = 1;
  for (let i = 0; i < nums.length; i++) {
    out[i] = running;
    running *= nums[i];
  }

  // Pass 2: multiply in the product of everything to the RIGHT of i.
  running = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    out[i] *= running;
    running *= nums[i];
  }
  return out;
}

test('basic', productExceptSelf([1, 2, 3, 4]), [24, 12, 8, 6]);
test('with a zero', productExceptSelf([-1, 1, 0, -3, 3]), [0, 0, 9, 0, 0]);
test('two zeros', productExceptSelf([0, 0, 2]), [0, 0, 0]);
test('two elements', productExceptSelf([2, 3]), [3, 2]);
test('negatives', productExceptSelf([-1, -2, -3]), [6, 3, 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
26const 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 longestConsecutive(nums) {
  const pool = new Set(nums);
  let best = 0;

  for (const n of pool) {
    if (pool.has(n - 1)) continue;      // not the start of a run, skip it

    let length = 1;
    while (pool.has(n + length)) length++;
    best = Math.max(best, length);
  }
  return best;
}

test('classic', longestConsecutive([100, 4, 200, 1, 3, 2]), 4);
test('with duplicates', longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]), 9);
test('empty', longestConsecutive([]), 0);
test('single', longestConsecutive([5]), 1);
test('no run', longestConsecutive([10, 30, 20]), 1);
test('negatives across zero', longestConsecutive([-1, 0, 1, 2]), 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
51const 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 isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const value = board[r][c];
      if (value === '.') continue;

      const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(value) || cols[c].has(value) || boxes[box].has(value)) return false;

      rows[r].add(value);
      cols[c].add(value);
      boxes[box].add(value);
    }
  }
  return true;
}

const valid = [
  ['5','3','.','.','7','.','.','.','.'],
  ['6','.','.','1','9','5','.','.','.'],
  ['.','9','8','.','.','.','.','6','.'],
  ['8','.','.','.','6','.','.','.','3'],
  ['4','.','.','8','.','3','.','.','1'],
  ['7','.','.','.','2','.','.','.','6'],
  ['.','6','.','.','.','.','2','8','.'],
  ['.','.','.','4','1','9','.','.','5'],
  ['.','.','.','.','8','.','.','7','9'],
];
test('a valid board', isValidSudoku(valid), true);

// Same board, but the leading 5 is moved down so the top-left box has two 5s.
const boxClash = valid.map(row => [...row]);
boxClash[1][0] = '5';
test('duplicate in a box', isValidSudoku(boxClash), false);

const rowClash = valid.map(row => [...row]);
rowClash[0][2] = '3';
test('duplicate in a row', isValidSudoku(rowClash), false);

const empty = Array.from({ length: 9 }, () => new Array(9).fill('.'));
test('all empty is valid', isValidSudoku(empty), 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
35const 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 encode(list) {
  // length + '#' + contents. The length prefix makes the payload unambiguous.
  let out = '';
  for (const s of list) out += s.length + '#' + s;
  return out;
}

function decode(encoded) {
  const out = [];
  let i = 0;
  while (i < encoded.length) {
    let hash = i;
    while (encoded[hash] !== '#') hash++;          // read the digits

    const length = Number(encoded.slice(i, hash));
    out.push(encoded.slice(hash + 1, hash + 1 + length));
    i = hash + 1 + length;                          // jump past this record
  }
  return out;
}

const roundTrip = (list) => decode(encode(list));

test('plain words', roundTrip(['lint', 'code', 'love', 'you']), ['lint', 'code', 'love', 'you']);
test('contains the delimiter', roundTrip(['a#b', '#', '2#x']), ['a#b', '#', '2#x']);
test('empty strings', roundTrip(['', '', 'a']), ['', '', 'a']);
test('empty list', roundTrip([]), []);
test('digits that look like lengths', roundTrip(['12', '3#4']), ['12', '3#4']);
test('encoded form', encode(['ab', 'c']), '2#ab1#c');

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
26const 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 isPalindrome(s) {
  const ok = (ch) => /[a-z0-9]/i.test(ch);
  let lo = 0, hi = s.length - 1;

  while (lo < hi) {
    while (lo < hi && !ok(s[lo])) lo++;        // the lo < hi guard matters
    while (lo < hi && !ok(s[hi])) hi--;
    if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
    lo++; hi--;
  }
  return true;
}

test('with punctuation', isPalindrome('A man, a plan, a canal: Panama'), true);
test('not a palindrome', isPalindrome('race a car'), false);
test('only punctuation', isPalindrome(' '), true);
test('empty', isPalindrome(''), true);
test('single letter', isPalindrome('a'), true);
test('digits', isPalindrome('0P'), false);
test('mixed case', isPalindrome('Aa'), 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
25const 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 removeDuplicates(nums) {
  if (nums.length === 0) return 0;

  let write = 1;                              // nums[0] is always kept
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read];
  }
  return write;
}

// Helper so the tests can look at the meaningful prefix.
const front = (nums) => { const k = removeDuplicates(nums); return nums.slice(0, k); };

test('with duplicates', front([1, 1, 2]), [1, 2]);
test('longer run', front([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]), [0, 1, 2, 3, 4]);
test('all identical', front([5, 5, 5]), [5]);
test('already unique', front([1, 2, 3]), [1, 2, 3]);
test('empty', front([]), []);
test('returns the count', removeDuplicates([1, 1, 2]), 2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23const 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 twoSumSorted(nums, target) {
  let lo = 0, hi = nums.length - 1;

  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo + 1, hi + 1];    // 1-based, as asked
    if (sum < target) lo++;                          // need bigger
    else hi--;                                       // need smaller
  }
  return [];
}

test('basic', twoSumSorted([2, 7, 11, 15], 9), [1, 2]);
test('middle pair', twoSumSorted([2, 3, 4], 6), [1, 3]);
test('negatives', twoSumSorted([-1, 0], -1), [1, 2]);
test('two elements', twoSumSorted([1, 2], 3), [1, 2]);
test('no pair', twoSumSorted([1, 2, 3], 100), []);

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
37const 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 threeSum(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const out = [];

  for (let i = 0; i < sorted.length - 2; i++) {
    if (sorted[i] > 0) break;                            // sorted: no way back to 0
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;  // skip a repeated anchor

    let lo = i + 1, hi = sorted.length - 1;
    while (lo < hi) {
      const sum = sorted[i] + sorted[lo] + sorted[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        out.push([sorted[i], sorted[lo], sorted[hi]]);
        lo++; hi--;
        // Step past duplicates so the same triple is not emitted twice.
        while (lo < hi && sorted[lo] === sorted[lo - 1]) lo++;
        while (lo < hi && sorted[hi] === sorted[hi + 1]) hi--;
      }
    }
  }
  return out;
}

test('classic', threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]]);
test('no triple', threeSum([0, 1, 1]), []);
test('all zeros', threeSum([0, 0, 0]), [[0, 0, 0]]);
test('four zeros, still one triple', threeSum([0, 0, 0, 0]), [[0, 0, 0]]);
test('too short', threeSum([1, 2]), []);
test('many duplicates', threeSum([-2, 0, 0, 2, 2]), [[-2, 0, 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
25const 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 maxArea(heights) {
  let best = 0, lo = 0, hi = heights.length - 1;

  while (lo < hi) {
    const height = Math.min(heights[lo], heights[hi]);
    best = Math.max(best, height * (hi - lo));

    // Move the shorter wall: it is the binding constraint.
    if (heights[lo] < heights[hi]) lo++;
    else hi--;
  }
  return best;
}

test('classic', maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
test('two walls', maxArea([1, 1]), 1);
test('increasing', maxArea([1, 2, 3, 4, 5]), 6);
test('tall ends', maxArea([9, 1, 1, 9]), 27);
test('single wall holds nothing', maxArea([5]), 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
29const 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 sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;

  while (mid <= hi) {
    if (nums[mid] === 0) {
      [nums[lo], nums[mid]] = [nums[mid], nums[lo]];
      lo++; mid++;                        // what came from lo is a settled 1 or 0
    } else if (nums[mid] === 2) {
      [nums[mid], nums[hi]] = [nums[hi], nums[mid]];
      hi--;                                // do NOT advance mid: new value unseen
    } else {
      mid++;                               // a 1 is already in the right region
    }
  }
  return nums;
}

test('classic', sortColors([2, 0, 2, 1, 1, 0]), [0, 0, 1, 1, 2, 2]);
test('short', sortColors([2, 0, 1]), [0, 1, 2]);
test('single', sortColors([0]), [0]);
test('already sorted', sortColors([0, 1, 2]), [0, 1, 2]);
test('reversed', sortColors([2, 2, 1, 1, 0, 0]), [0, 0, 1, 1, 2, 2]);
test('one value only', sortColors([1, 1, 1]), [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
35const 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 trap(heights) {
  if (heights.length === 0) return 0;

  let lo = 0, hi = heights.length - 1;
  let leftMax = heights[lo], rightMax = heights[hi];
  let water = 0;

  while (lo < hi) {
    // The smaller running max bounds the water level, so that side is settled.
    if (leftMax <= rightMax) {
      lo++;
      leftMax = Math.max(leftMax, heights[lo]);
      water += leftMax - heights[lo];
    } else {
      hi--;
      rightMax = Math.max(rightMax, heights[hi]);
      water += rightMax - heights[hi];
    }
  }
  return water;
}

test('classic', trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6);
test('simple basin', trap([4, 2, 0, 3, 2, 5]), 9);
test('monotonic holds nothing', trap([1, 2, 3, 4]), 0);
test('descending holds nothing', trap([4, 3, 2, 1]), 0);
test('empty', trap([]), 0);
test('flat', trap([2, 2, 2]), 0);
test('single dip', trap([3, 0, 3]), 3);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22const 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 maxProfit(prices) {
  let cheapest = Infinity, best = 0;

  for (const price of prices) {
    cheapest = Math.min(cheapest, price);      // best day to have bought
    best = Math.max(best, price - cheapest);   // best sale if we sell today
  }
  return best;
}

test('classic', maxProfit([7, 1, 5, 3, 6, 4]), 5);
test('only falls', maxProfit([7, 6, 4, 3, 1]), 0);
test('single day', maxProfit([5]), 0);
test('empty', maxProfit([]), 0);
test('rises throughout', maxProfit([1, 2, 3, 4]), 3);
test('best pair at the end', maxProfit([3, 2, 6, 5, 0, 3]), 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
28const 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 lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let best = 0, left = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // Only jump if the previous sighting is inside the current window.
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) left = lastSeen.get(ch) + 1;

    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

test('classic', lengthOfLongestSubstring('abcabcbb'), 3);
test('all identical', lengthOfLongestSubstring('bbbbb'), 1);
test('window must slide', lengthOfLongestSubstring('pwwkew'), 3);
test('empty', lengthOfLongestSubstring(''), 0);
test('stale index trap', lengthOfLongestSubstring('dvdf'), 3);
test('single char', lengthOfLongestSubstring('a'), 1);
test('all distinct', lengthOfLongestSubstring('abcdef'), 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
30const 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 characterReplacement(s, k) {
  const counts = new Map();
  let best = 0, left = 0, mostCommon = 0;

  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    mostCommon = Math.max(mostCommon, counts.get(s[right]));

    // Too many characters would need replacing: shrink from the left.
    while (right - left + 1 - mostCommon > k) {
      counts.set(s[left], counts.get(s[left]) - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

test('one replacement', characterReplacement('ABAB', 2), 4);
test('classic', characterReplacement('AABABBA', 1), 4);
test('no replacements allowed', characterReplacement('ABCD', 0), 1);
test('all identical', characterReplacement('AAAA', 2), 4);
test('single char', characterReplacement('A', 1), 1);
test('empty', characterReplacement('', 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
45
46const 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 checkInclusion(pattern, text) {
  if (pattern.length > text.length) return false;

  const need = new Array(26).fill(0);
  const have = new Array(26).fill(0);
  const at = (ch) => ch.charCodeAt(0) - 97;

  for (const ch of pattern) need[at(ch)]++;
  for (let i = 0; i < pattern.length; i++) have[at(text[i])]++;

  let matching = 0;
  for (let i = 0; i < 26; i++) if (need[i] === have[i]) matching++;

  if (matching === 26) return true;

  for (let right = pattern.length; right < text.length; right++) {
    const entering = at(text[right]);
    const leaving = at(text[right - pattern.length]);

    // Adjust only the two letters whose counts changed.
    have[entering]++;
    if (have[entering] === need[entering]) matching++;
    else if (have[entering] === need[entering] + 1) matching--;

    have[leaving]--;
    if (have[leaving] === need[leaving]) matching++;
    else if (have[leaving] === need[leaving] - 1) matching--;

    if (matching === 26) return true;
  }
  return false;
}

test('present', checkInclusion('ab', 'eidbaooo'), true);
test('absent', checkInclusion('ab', 'eidboaoo'), false);
test('exact match', checkInclusion('abc', 'cba'), true);
test('pattern too long', checkInclusion('abcd', 'abc'), false);
test('single char present', checkInclusion('a', 'a'), true);
test('a rearrangement counts', checkInclusion('aab', 'aba'), true);
test('wrong repeat counts', checkInclusion('aab', 'abb'), 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
27const 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 minSubArrayLen(target, nums) {
  let best = Infinity, sum = 0, left = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    // While it is still valid, record and shrink. Shortest-valid shape.
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

test('classic', minSubArrayLen(7, [2, 3, 1, 2, 4, 3]), 2);
test('single element suffices', minSubArrayLen(4, [1, 4, 4]), 1);
test('impossible', minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]), 0);
test('whole array needed', minSubArrayLen(6, [1, 2, 3]), 3);
test('empty', minSubArrayLen(5, []), 0);
test('exact single', minSubArrayLen(5, [5]), 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
42const 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 minWindow(text, pattern) {
  if (pattern.length === 0 || text.length < pattern.length) return '';

  const need = new Map();
  for (const ch of pattern) need.set(ch, (need.get(ch) || 0) + 1);

  let missing = pattern.length;          // total characters still owed
  let bestStart = 0, bestLength = Infinity;
  let left = 0;

  for (let right = 0; right < text.length; right++) {
    const ch = text[right];
    // Only a still-owed character reduces the debt.
    if (need.get(ch) > 0) missing--;
    need.set(ch, (need.get(ch) || 0) - 1);   // can go negative: a surplus

    while (missing === 0) {                   // valid: record, then shrink
      if (right - left + 1 < bestLength) {
        bestLength = right - left + 1;
        bestStart = left;
      }
      const out = text[left++];
      need.set(out, need.get(out) + 1);
      if (need.get(out) > 0) missing++;       // we just gave one back
    }
  }
  return bestLength === Infinity ? '' : text.slice(bestStart, bestStart + bestLength);
}

test('classic', minWindow('ADOBECODEBANC', 'ABC'), 'BANC');
test('whole string', minWindow('a', 'a'), 'a');
test('impossible', minWindow('a', 'aa'), '');
test('empty pattern', minWindow('abc', ''), '');
test('repeats needed', minWindow('aabbb', 'aabb'), 'aabb');
test('must span a gap', minWindow('aaflslflsldkabbb', 'aabb'), 'aflslflsldkabb');
test('pattern longer than text', minWindow('ab', 'abc'), '');

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
27const 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 NumArray {
  constructor(nums) {
    // One longer than the input, so prefix[0] = 0 and there is no edge case.
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) this.prefix[i + 1] = this.prefix[i] + nums[i];
  }

  sumRange(lo, hi) {
    return this.prefix[hi + 1] - this.prefix[lo];
  }
}

const arr = new NumArray([-2, 0, 3, -5, 2, -1]);
test('middle range', arr.sumRange(0, 2), 1);
test('from index 2', arr.sumRange(2, 5), -1);
test('whole array', arr.sumRange(0, 5), -3);
test('single element', arr.sumRange(3, 3), -5);
test('first element only', arr.sumRange(0, 0), -2);

const one = new NumArray([7]);
test('one-element array', one.sumRange(0, 0), 7);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25const 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 subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);     // one empty prefix with total 0
  let running = 0, count = 0;

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

test('classic', subarraySum([1, 1, 1], 2), 2);
test('sums to k once', subarraySum([1, 2, 3], 3), 2);
test('with negatives', subarraySum([1, -1, 0], 0), 3);
test('single match', subarraySum([1], 1), 1);
test('no match', subarraySum([1, 2], 7), 0);
test('all zeros, k = 0', subarraySum([0, 0, 0], 0), 6);
test('needs the seeded zero', subarraySum([3, 4, 7], 7), 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
29const 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 findMaxLength(nums) {
  // Map from running total to the FIRST index that produced it.
  const firstAt = new Map([[0, -1]]);   // total 0 exists before the array starts
  let running = 0, best = 0;

  for (let i = 0; i < nums.length; i++) {
    running += nums[i] === 1 ? 1 : -1;             // 0 counts as -1

    if (firstAt.has(running)) {
      best = Math.max(best, i - firstAt.get(running));   // the gap sums to zero
    } else {
      firstAt.set(running, i);                      // only the first sighting
    }
  }
  return best;
}

test('simple pair', findMaxLength([0, 1]), 2);
test('extra one', findMaxLength([0, 1, 0]), 2);
test('longer', findMaxLength([0, 1, 1, 0, 1, 1, 1, 0]), 4);
test('no balance', findMaxLength([1, 1, 1]), 0);
test('whole array', findMaxLength([0, 0, 1, 1]), 4);
test('empty', findMaxLength([]), 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
27const 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 subarraysDivByK(nums, k) {
  const counts = new Map([[0, 1]]);
  let running = 0, total = 0;

  for (const n of nums) {
    running += n;
    // JavaScript % keeps the sign of the dividend, so normalise into 0..k-1.
    const remainder = ((running % k) + k) % k;

    total += counts.get(remainder) || 0;
    counts.set(remainder, (counts.get(remainder) || 0) + 1);
  }
  return total;
}

test('classic', subarraysDivByK([4, 5, 0, -2, -3, 1], 5), 7);
test('none divisible', subarraysDivByK([5], 9), 0);
test('single divisible', subarraysDivByK([5], 5), 1);
test('negatives', subarraysDivByK([-1, 2, 9], 2), 2);
test('all zeros', subarraysDivByK([0, 0], 3), 3);
test('k of 1 takes everything', subarraysDivByK([1, 2, 3], 1), 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
30const 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 carPooling(trips, capacity) {
  // Stops are bounded (0..1000), so bucket the deltas rather than sorting.
  const delta = new Array(1002).fill(0);

  for (const [passengers, from, to] of trips) {
    delta[from] += passengers;      // they board here
    delta[to] -= passengers;        // and leave here, freeing the seats
  }

  let onboard = 0;
  for (let stop = 0; stop < delta.length; stop++) {
    onboard += delta[stop];                    // the running sum is the real count
    if (onboard > capacity) return false;
  }
  return true;
}

test('too full', carPooling([[2, 1, 5], [3, 3, 7]], 4), false);
test('just fits', carPooling([[2, 1, 5], [3, 3, 7]], 5), true);
test('no overlap', carPooling([[2, 1, 5], [3, 5, 7]], 3), true);
test('single trip', carPooling([[4, 0, 1]], 4), true);
test('one seat short', carPooling([[5, 0, 1]], 4), false);
test('no trips', carPooling([], 1), true);
test('drop-off frees a seat', carPooling([[3, 2, 7], [3, 7, 9]], 3), 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
25const 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 search(nums, target) {
  let lo = 0, hi = nums.length - 1;      // both inclusive

  while (lo <= hi) {                      // <= or a 1-element range is skipped
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1; // both branches exclude mid
    else hi = mid - 1;
  }
  return -1;
}

test('found in the middle', search([-1, 0, 3, 5, 9, 12], 9), 4);
test('absent', search([-1, 0, 3, 5, 9, 12], 2), -1);
test('first element', search([1, 2, 3], 1), 0);
test('last element', search([1, 2, 3], 3), 2);
test('single hit', search([5], 5), 0);
test('single miss', search([5], 3), -1);
test('empty', 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
24const 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 findMin(nums) {
  let lo = 0, hi = nums.length - 1;

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    // Comparing against the RIGHT end handles the unrotated case for free.
    if (nums[mid] > nums[hi]) lo = mid + 1;    // pivot is strictly right of mid
    else hi = mid;                              // mid could be the minimum
  }
  return nums[lo];
}

test('rotated', findMin([3, 4, 5, 1, 2]), 1);
test('rotated further', findMin([4, 5, 6, 7, 0, 1, 2]), 0);
test('not rotated', findMin([1, 2, 3]), 1);
test('single', findMin([5]), 5);
test('two, rotated', findMin([2, 1]), 1);
test('two, in order', findMin([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
32
33const 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 search(nums, target) {
  let lo = 0, hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {
      // Left half is sorted: is the target inside it?
      if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // Right half is sorted.
      if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

test('in the right half', search([4, 5, 6, 7, 0, 1, 2], 0), 4);
test('absent', search([4, 5, 6, 7, 0, 1, 2], 3), -1);
test('in the left half', search([4, 5, 6, 7, 0, 1, 2], 5), 1);
test('single miss', search([1], 0), -1);
test('single hit', search([1], 1), 0);
test('unrotated', search([1, 2, 3, 4], 3), 2);
test('pivot itself', search([5, 1, 3], 5), 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
28const 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 minEatingSpeed(piles, h) {
  const hoursAt = (speed) => {
    let hours = 0;
    for (const pile of piles) hours += Math.ceil(pile / speed);
    return hours;
  };

  let lo = 1, hi = Math.max(...piles);     // the answer is in this range
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (hoursAt(mid) <= h) hi = mid;        // fast enough: try slower
    else lo = mid + 1;                      // too slow: must speed up
  }
  return lo;
}

test('classic', minEatingSpeed([3, 6, 7, 11], 8), 4);
test('tight schedule', minEatingSpeed([30, 11, 23, 4, 20], 5), 30);
test('more time', minEatingSpeed([30, 11, 23, 4, 20], 6), 23);
test('single pile, one hour', minEatingSpeed([12], 1), 12);
test('plenty of time', minEatingSpeed([1, 1, 1], 3), 1);
test('two piles', minEatingSpeed([2, 2], 2), 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
32const 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 shipWithinDays(weights, days) {
  const daysNeeded = (capacity) => {
    let used = 1, load = 0;
    for (const w of weights) {
      if (load + w > capacity) { used++; load = 0; }   // start a new day
      load += w;
    }
    return used;
  };

  let lo = Math.max(...weights);                    // must fit the heaviest
  let hi = weights.reduce((a, b) => a + b, 0);      // everything in one day
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (daysNeeded(mid) <= days) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

test('classic', shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5), 15);
test('three days', shipWithinDays([3, 2, 2, 4, 1, 4], 3), 6);
test('one per day', shipWithinDays([1, 2, 3, 1, 1], 4), 3);
test('single package', shipWithinDays([7], 1), 7);
test('one day for everything', shipWithinDays([1, 2, 3], 1), 6);
test('a day each', shipWithinDays([5, 5, 5], 3), 5);

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
41const 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 findMedianSortedArrays(a, b) {
  // Always binary search the SHORTER array, so the split count stays valid.
  if (a.length > b.length) [a, b] = [b, a];

  const total = a.length + b.length;
  const half = Math.floor((total + 1) / 2);      // size of the left partition
  let lo = 0, hi = a.length;

  while (lo <= hi) {
    const takeA = lo + ((hi - lo) >> 1);          // from a
    const takeB = half - takeA;                   // the rest from b

    // Sentinels remove every boundary special case.
    const aLeft = takeA > 0 ? a[takeA - 1] : -Infinity;
    const aRight = takeA < a.length ? a[takeA] : Infinity;
    const bLeft = takeB > 0 ? b[takeB - 1] : -Infinity;
    const bRight = takeB < b.length ? b[takeB] : Infinity;

    if (aLeft <= bRight && bLeft <= aRight) {     // a correct split
      if (total % 2 === 1) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = takeA - 1;           // took too many from a
    else lo = takeA + 1;                          // took too few
  }
  return 0;
}

test('even total', findMedianSortedArrays([1, 3], [2]), 2);
test('odd total', findMedianSortedArrays([1, 2], [3, 4]), 2.5);
test('one empty', findMedianSortedArrays([], [1]), 1);
test('other empty', findMedianSortedArrays([2], []), 2);
test('no overlap', findMedianSortedArrays([1, 2], [7, 8]), 4.5);
test('identical', findMedianSortedArrays([1, 1], [1, 1]), 1);
test('uneven lengths', findMedianSortedArrays([1, 3, 5, 7], [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
29const 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 isValid(s) {
  const closes = { ')': '(', ']': '[', '}': '{' };
  const stack = [];

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      // Pops empty when a closer arrives with nothing open.
      if (stack.pop() !== closes[ch]) return false;
    }
  }
  return stack.length === 0;             // anything left open is invalid
}

test('simple pair', isValid('()'), true);
test('nested and sequential', isValid('()[]{}'), true);
test('mismatched types', isValid('(]'), false);
test('interleaved', isValid('([)]'), false);
test('correctly nested', isValid('{[]}'), true);
test('unclosed', isValid('('), false);
test('closer first', isValid(')'), false);
test('empty', isValid(''), 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
46const 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 MinStack {
  constructor() {
    this.items = [];
    this.mins = [];                       // running minimum at each depth
  }

  push(value) {
    this.items.push(value);
    const currentMin = this.mins.length ? this.mins[this.mins.length - 1] : Infinity;
    this.mins.push(Math.min(value, currentMin));
  }

  pop() {
    this.mins.pop();                      // always in lockstep
    return this.items.pop();
  }

  top() { return this.items[this.items.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

const st = new MinStack();
st.push(-2); st.push(0); st.push(-3);
test('min with -3 on top', st.getMin(), -3);
st.pop();
test('top after pop', st.top(), 0);
test('min recovered', st.getMin(), -2);

const st2 = new MinStack();
st2.push(5);
test('single element min', st2.getMin(), 5);
st2.push(5);
st2.pop();
test('duplicate min survives a pop', st2.getMin(), 5);

const st3 = new MinStack();
st3.push(2); st3.push(1); st3.push(3);
test('min is not the top', st3.getMin(), 1);
st3.pop();
test('min unchanged after popping a larger value', st3.getMin(), 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
26const 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 dailyTemperatures(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];                        // indices, temperatures decreasing

  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const day = stack.pop();
      answer[day] = i - day;               // indices, so the distance is free
    }
    stack.push(i);
  }
  return answer;                            // anything unpopped keeps its 0
}

test('classic', dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]);
test('rising', dailyTemperatures([30, 40, 50, 60]), [1, 1, 1, 0]);
test('with a plateau', dailyTemperatures([30, 60, 90]), [1, 1, 0]);
test('falling', dailyTemperatures([90, 80, 70]), [0, 0, 0]);
test('all equal', dailyTemperatures([50, 50, 50]), [0, 0, 0]);
test('single day', dailyTemperatures([40]), [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
33const 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 evalRPN(tokens) {
  const stack = [];
  const apply = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),      // trunc, not floor: -7/2 is -3
  };

  for (const token of tokens) {
    if (token in apply) {
      const right = stack.pop();            // popped FIRST, so it is the right side
      const left = stack.pop();
      stack.push(apply[token](left, right));
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

test('addition then multiply', evalRPN(['2', '1', '+', '3', '*']), 9);
test('division', evalRPN(['4', '13', '5', '/', '+']), 6);
test('subtraction order', evalRPN(['5', '3', '-']), 2);
test('negative truncation', evalRPN(['-7', '2', '/']), -3);
test('single number', evalRPN(['42']), 42);
test('longer', evalRPN(['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+']), 22);

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
35const 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 calculate(s) {
  const stack = [];
  let number = 0, operator = '+';

  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch >= '0' && ch <= '9') number = number * 10 + Number(ch);   // multi-digit

    // Act on an operator, or at the very end of the string.
    if ((ch < '0' && ch !== ' ') || i === s.length - 1) {
      if (operator === '+') stack.push(number);
      else if (operator === '-') stack.push(-number);
      else if (operator === '*') stack.push(stack.pop() * number);
      else stack.push(Math.trunc(stack.pop() / number));

      operator = ch;                        // remember it for the next term
      number = 0;
    }
  }
  return stack.reduce((a, b) => a + b, 0);   // the deferred additions
}

test('precedence', calculate('3+2*2'), 7);
test('integer division', calculate(' 3/2 '), 1);
test('mixed', calculate(' 3+5 / 2 '), 5);
test('multi-digit', calculate('12+34'), 46);
test('single number', calculate('42'), 42);
test('subtraction chain', calculate('10-2-3'), 5);
test('multiply chain', calculate('2*3*4'), 24);

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
30const 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 largestRectangleArea(heights) {
  const bars = [...heights, 0];            // sentinel 0 flushes the stack
  const stack = [];                         // indices, heights increasing
  let best = 0;

  for (let i = 0; i < bars.length; i++) {
    while (stack.length && bars[stack[stack.length - 1]] >= bars[i]) {
      const height = bars[stack.pop()];
      // Left boundary is whatever remains beneath, or the very start.
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

test('classic', largestRectangleArea([2, 1, 5, 6, 2, 3]), 10);
test('two bars', largestRectangleArea([2, 4]), 4);
test('single bar', largestRectangleArea([5]), 5);
test('flat', largestRectangleArea([3, 3, 3]), 9);
test('increasing', largestRectangleArea([1, 2, 3, 4]), 6);
test('decreasing', largestRectangleArea([4, 3, 2, 1]), 6);
test('a zero splits it', largestRectangleArea([2, 0, 2]), 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
33const 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)}`)
);

// Helpers, so each panel stands alone.
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 reverseList(head) {
  let prev = null, curr = head;

  while (curr) {
    const next = curr.next;      // save it FIRST, or lose the rest of the list
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;                    // the old tail
}

test('five nodes', toArray(reverseList(toList([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]);
test('two nodes', toArray(reverseList(toList([1, 2]))), [2, 1]);
test('single node', toArray(reverseList(toList([1]))), [1]);
test('empty', toArray(reverseList(toList([]))), []);
test('duplicates', toArray(reverseList(toList([1, 1, 2]))), [2, 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
34const 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)}`)
);

// Helpers, so each panel stands alone.
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 mergeTwoLists(a, b) {
  const dummy = new ListNode(0);       // removes the "which list starts it" case
  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;                   // attach whatever remains, in one step
  return dummy.next;
}

test('interleaved', toArray(mergeTwoLists(toList([1, 2, 4]), toList([1, 3, 4]))), [1, 1, 2, 3, 4, 4]);
test('both empty', toArray(mergeTwoLists(toList([]), toList([]))), []);
test('one empty', toArray(mergeTwoLists(toList([]), toList([0]))), [0]);
test('no overlap', toArray(mergeTwoLists(toList([1, 2]), toList([8, 9]))), [1, 2, 8, 9]);
test('one much longer', toArray(mergeTwoLists(toList([5]), toList([1, 2, 3]))), [1, 2, 3, 5]);

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
42const 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)}`)
);

// Helpers, so each panel stands alone.
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 hasCycle(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {          // both guards needed before a double step
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;     // fast gains 1 per step, so it must land
  }
  return false;                          // fast reached the end: no loop
}

const looped = toList([3, 2, 0, -4]);
looped.next.next.next.next = looped.next;      // tail points back to index 1
test('has a cycle', hasCycle(looped), true);

const twoLoop = toList([1, 2]);
twoLoop.next.next = twoLoop;
test('two-node cycle', hasCycle(twoLoop), true);

const selfLoop = toList([1]);
selfLoop.next = selfLoop;
test('self loop', hasCycle(selfLoop), true);

test('no cycle', hasCycle(toList([1, 2, 3])), false);
test('single node', hasCycle(toList([1])), false);
test('empty', hasCycle(toList([])), 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
48const 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)}`)
);

// Helpers, so each panel stands alone.
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 isPalindrome(head) {
  if (!head || !head.next) return true;

  // Find the middle.
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }

  // Reverse the second half.
  let prev = null, curr = slow.next;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Compare. The shorter half ends first, so an odd middle is ignored.
  let front = head, back = prev;
  while (back) {
    if (front.val !== back.val) return false;
    front = front.next;
    back = back.next;
  }
  return true;
}

test('even palindrome', isPalindrome(toList([1, 2, 2, 1])), true);
test('not a palindrome', isPalindrome(toList([1, 2])), false);
test('odd palindrome', isPalindrome(toList([1, 2, 1])), true);
test('single node', isPalindrome(toList([1])), true);
test('all equal', isPalindrome(toList([7, 7, 7, 7])), true);
test('near miss', isPalindrome(toList([1, 2, 3, 2, 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
33const 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)}`)
);

// Helpers, so each panel stands alone.
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 removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);   // so the head has a predecessor too
  let lead = dummy, trail = dummy;

  for (let i = 0; i < n; i++) lead = lead.next;   // open a gap of n

  while (lead.next) { lead = lead.next; trail = trail.next; }

  trail.next = trail.next.next;           // trail sits just before the target
  return dummy.next;
}

test('remove the second from last', toArray(removeNthFromEnd(toList([1, 2, 3, 4, 5]), 2)), [1, 2, 3, 5]);
test('remove the only node', toArray(removeNthFromEnd(toList([1]), 1)), []);
test('remove the head', toArray(removeNthFromEnd(toList([1, 2]), 2)), [2]);
test('remove the tail', toArray(removeNthFromEnd(toList([1, 2]), 1)), [1]);
test('longer list', toArray(removeNthFromEnd(toList([1, 2, 3, 4, 5]), 5)), [2, 3, 4, 5]);

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
51const 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)}`)
);

// Helpers, so each panel stands alone.
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 reorderList(head) {
  if (!head || !head.next) return head;

  // 1. Find the middle. For even lengths this leaves slow at the end of half one.
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }

  // 2. Cut, then reverse the second half.
  let second = slow.next;
  slow.next = null;                       // the cut: without it you build a cycle
  let prev = null;
  while (second) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }

  // 3. Weave the two halves.
  let first = head, back = prev;
  while (back) {
    const nextFirst = first.next, nextBack = back.next;
    first.next = back;
    back.next = nextFirst;
    first = nextFirst;
    back = nextBack;
  }
  return head;
}

test('even length', toArray(reorderList(toList([1, 2, 3, 4]))), [1, 4, 2, 3]);
test('odd length', toArray(reorderList(toList([1, 2, 3, 4, 5]))), [1, 5, 2, 4, 3]);
test('two nodes', toArray(reorderList(toList([1, 2]))), [1, 2]);
test('single node', toArray(reorderList(toList([1]))), [1]);
test('three nodes', toArray(reorderList(toList([1, 2, 3]))), [1, 3, 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
37const 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)}`)
);

// Helpers, so each panel stands alone.
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 addTwoNumbers(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy, carry = 0;

  // The carry belongs in the condition, or 9 + 1 loses its leading digit.
  while (a || b || carry) {
    const sum = (a ? a.val : 0) + (b ? b.val : 0) + carry;
    carry = Math.floor(sum / 10);
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
    if (a) a = a.next;
    if (b) b = b.next;
  }
  return dummy.next;
}

test('342 + 465', toArray(addTwoNumbers(toList([2, 4, 3]), toList([5, 6, 4]))), [7, 0, 8]);
test('zero plus zero', toArray(addTwoNumbers(toList([0]), toList([0]))), [0]);
test('carry cascades', toArray(addTwoNumbers(toList([9, 9, 9]), toList([1]))), [0, 0, 0, 1]);
test('final carry', toArray(addTwoNumbers(toList([9]), toList([1]))), [0, 1]);
test('different lengths', toArray(addTwoNumbers(toList([1]), toList([9, 9]))), [0, 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
50const 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)}`)
);

// Helpers, so each panel stands alone.
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 mergeTwo(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 mergeKLists(lists) {
  if (lists.length === 0) return null;

  // Merge in pairs, halving the count each round: log k rounds.
  let current = lists;
  while (current.length > 1) {
    const next = [];
    for (let i = 0; i < current.length; i += 2) {
      next.push(mergeTwo(current[i], current[i + 1] ?? null));
    }
    current = next;
  }
  return current[0];
}

test('three lists', toArray(mergeKLists([toList([1, 4, 5]), toList([1, 3, 4]), toList([2, 6])])),
  [1, 1, 2, 3, 4, 4, 5, 6]);
test('no lists', toArray(mergeKLists([])), []);
test('one empty list', toArray(mergeKLists([toList([])])), []);
test('odd count', toArray(mergeKLists([toList([1]), toList([2]), toList([3])])), [1, 2, 3]);
test('some empty', toArray(mergeKLists([toList([]), toList([1]), toList([])])), [1]);
test('single list', toArray(mergeKLists([toList([2, 4])])), [2, 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
32const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function maxDepth(root) {
  if (!root) return 0;                                   // empty tree
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

test('balanced-ish', maxDepth(buildTree([3, 9, 20, null, null, 15, 7])), 3);
test('leaning', maxDepth(buildTree([1, null, 2])), 2);
test('single node', maxDepth(buildTree([1])), 1);
test('empty', maxDepth(buildTree([])), 0);
test('full three levels', maxDepth(buildTree([1, 2, 3, 4, 5, 6, 7])), 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
49const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function invertTree(root) {
  if (!root) return null;

  [root.left, root.right] = [root.right, root.left];     // swap here
  invertTree(root.left);                                  // then recurse
  invertTree(root.right);
  return root;
}

// Read back as a level-order array so the test is readable.
const levels = (root) => {
  if (!root) return [];
  const out = [], queue = [root];
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i];
    out.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return out;
};

test('classic', levels(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9]))), [4, 7, 2, 9, 6, 3, 1]);
test('three nodes', levels(invertTree(buildTree([2, 1, 3]))), [2, 3, 1]);
test('empty', levels(invertTree(buildTree([]))), []);
test('single', levels(invertTree(buildTree([1]))), [1]);
test('one-sided', levels(invertTree(buildTree([1, 2]))), [1, 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
35const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function isSameTree(a, b) {
  if (!a && !b) return true;               // both ended together
  if (!a || !b) return false;              // one ended early
  if (a.val !== b.val) return false;       // safe now: both exist

  return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}

test('identical', isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])), true);
test('mirrored, not equal', isSameTree(buildTree([1, 2]), buildTree([1, null, 2])), false);
test('different values', isSameTree(buildTree([1, 2, 1]), buildTree([1, 1, 2])), false);
test('both empty', isSameTree(buildTree([]), buildTree([])), true);
test('one empty', isSameTree(buildTree([1]), buildTree([])), 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
45const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function isBalanced(root) {
  // Returns the height, or -1 meaning "unbalanced somewhere below".
  function height(node) {
    if (!node) return 0;

    const left = height(node.left);
    if (left === -1) return -1;             // propagate the failure upward
    const right = height(node.right);
    if (right === -1) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
  }

  return height(root) !== -1;
}

test('balanced', isBalanced(buildTree([3, 9, 20, null, null, 15, 7])), true);
test('unbalanced', isBalanced(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])), false);
test('empty is balanced', isBalanced(buildTree([])), true);
test('single node', isBalanced(buildTree([1])), true);
test('a chain of three', isBalanced(buildTree([1, 2, null, 3])), false);
test('two levels', isBalanced(buildTree([1, 2, 3])), 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
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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function diameterOfBinaryTree(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);      // the path THROUGH this node
    return 1 + Math.max(left, right);          // the height, for the parent
  }

  height(root);
  return best;
}

test('classic', diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])), 3);
test('two nodes', diameterOfBinaryTree(buildTree([1, 2])), 1);
test('single node', diameterOfBinaryTree(buildTree([1])), 0);
test('empty', diameterOfBinaryTree(buildTree([])), 0);
test('deep on one side', diameterOfBinaryTree(buildTree([1, 2, null, 3, 4, 5, 6])), 3);

// Built by hand: the longest path is 7-5-3-2-4-6-8, six edges, and it never
// touches the root. Through the root would only be five.
const offCentre = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(3, new TreeNode(5, new TreeNode(7), null), null),
    new TreeNode(4, null, new TreeNode(6, null, new TreeNode(8)))),
  new TreeNode(9));
test('longest path skips the root', diameterOfBinaryTree(offCentre), 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
35
36
37
38
39
40
41
42
43
44
45
46const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function levelOrder(root) {
  if (!root) return [];

  const out = [];
  let level = [root];

  while (level.length) {
    out.push(level.map(node => node.val));

    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;                             // swapping arrays keeps levels clean
  }
  return out;
}

test('three levels', levelOrder(buildTree([3, 9, 20, null, null, 15, 7])), [[3], [9, 20], [15, 7]]);
test('single node', levelOrder(buildTree([1])), [[1]]);
test('empty', levelOrder(buildTree([])), []);
test('left chain', levelOrder(buildTree([1, 2, null, 3])), [[1], [2], [3]]);
test('full tree', levelOrder(buildTree([1, 2, 3, 4, 5, 6, 7])), [[1], [2, 3], [4, 5, 6, 7]]);

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
39const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function isValidBST(root, low = -Infinity, high = Infinity) {
  if (!root) return true;

  // The range comes from every ancestor, not just the parent.
  if (root.val <= low || root.val >= high) return false;

  return isValidBST(root.left, low, root.val) &&
         isValidBST(root.right, root.val, high);
}

test('valid', isValidBST(buildTree([2, 1, 3])), true);
test('grandparent violated', isValidBST(buildTree([5, 1, 4, null, null, 3, 6])), false);
test('single node', isValidBST(buildTree([1])), true);
test('empty', isValidBST(buildTree([])), true);
test('duplicate is invalid', isValidBST(buildTree([2, 2])), false);
test('deep valid tree', isValidBST(buildTree([8, 4, 12, 2, 6, 10, 14])), true);
test('subtly wrong', isValidBST(buildTree([10, 5, 15, null, null, 6, 20])), 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
42const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function lowestCommonAncestor(root, p, q) {
  let node = root;

  while (node) {
    if (p < node.val && q < node.val) node = node.left;        // both smaller
    else if (p > node.val && q > node.val) node = node.right;  // both larger
    else return node.val;                                       // they split here
  }
  return null;
}

const bst = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
test('split at the root', lowestCommonAncestor(bst, 2, 8), 6);
test('one is the ancestor', lowestCommonAncestor(bst, 2, 4), 2);
test('deep pair', lowestCommonAncestor(bst, 3, 5), 4);
test('both on the right', lowestCommonAncestor(bst, 7, 9), 8);
test('same node twice', lowestCommonAncestor(bst, 4, 4), 4);

const small = buildTree([2, 1]);
test('two-node tree', lowestCommonAncestor(small, 1, 2), 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
43const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function kthSmallest(root, k) {
  const stack = [];
  let node = root;

  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }   // dive left

    node = stack.pop();                                     // visit
    if (--k === 0) return node.val;                         // stop as soon as found

    node = node.right;                                      // then go right
  }
  return -1;
}

test('first smallest', kthSmallest(buildTree([3, 1, 4, null, 2]), 1), 1);
test('third smallest', kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 3), 3);
test('single node', kthSmallest(buildTree([1]), 1), 1);
test('largest', kthSmallest(buildTree([2, 1, 3]), 3), 3);
test('middle', kthSmallest(buildTree([2, 1, 3]), 2), 2);
test('k beyond the tree', kthSmallest(buildTree([1]), 5), -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
47const 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)}`)
);

// Helpers, so each panel stands alone.
function TreeNode(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
// Build from a level-order array, using null for a missing child.
const buildTree = (values) => {
  if (!values.length || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1, head = 0;
  while (i < values.length) {
    const node = queue[head++];
    if (i < values.length) { if (values[i] !== null) { node.left = new TreeNode(values[i]); queue.push(node.left); } i++; }
    if (i < values.length) { if (values[i] !== null) { node.right = new TreeNode(values[i]); queue.push(node.right); } i++; }
  }
  return root;
};

function maxPathSum(root) {
  let best = -Infinity;

  // Returns the best downward path starting at this node.
  function contribution(node) {
    if (!node) return 0;

    // Clamp at 0: a negative branch is worse than not going that way.
    const left = Math.max(0, contribution(node.left));
    const right = Math.max(0, contribution(node.right));

    best = Math.max(best, node.val + left + right);   // the path turning here
    return node.val + Math.max(left, right);           // straight path, for the parent
  }

  contribution(root);
  return best;
}

test('simple', maxPathSum(buildTree([1, 2, 3])), 6);
test('negative root', maxPathSum(buildTree([-10, 9, 20, null, null, 15, 7])), 42);
test('single node', maxPathSum(buildTree([5])), 5);
test('all negative', maxPathSum(buildTree([-3])), -3);
test('negative children', maxPathSum(buildTree([2, -1, -2])), 2);
test('two nodes', maxPathSum(buildTree([-2, 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
58const 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)}`)
);

// A binary min-heap. 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 p = (i - 1) >> 1;
      if (this.compare(this.a[p], this.a[i]) <= 0) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  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;
  }
}

function lastStoneWeight(stones) {
  const heap = new Heap((a, b) => b - a);        // inverted: a max-heap
  for (const s of stones) heap.push(s);

  while (heap.size > 1) {
    const heaviest = heap.pop();
    const second = heap.pop();
    if (heaviest !== second) heap.push(heaviest - second);
  }
  return heap.size ? heap.peek() : 0;
}

test('classic', lastStoneWeight([2, 7, 4, 1, 8, 1]), 1);
test('single stone', lastStoneWeight([1]), 1);
test('pair destroyed', lastStoneWeight([2, 2]), 0);
test('unequal pair', lastStoneWeight([5, 3]), 2);
test('all identical, even count', lastStoneWeight([3, 3, 3, 3]), 0);
test('all identical, odd count', lastStoneWeight([3, 3, 3]), 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
56const 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)}`)
);

// A binary min-heap. 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 p = (i - 1) >> 1;
      if (this.compare(this.a[p], this.a[i]) <= 0) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  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;
  }
}

function findKthLargest(nums, k) {
  const heap = new Heap();                    // min-heap of the best k so far

  for (const n of nums) {
    heap.push(n);
    if (heap.size > k) heap.pop();            // evict the weakest survivor
  }
  return heap.peek();                          // smallest of the top k
}

test('classic', findKthLargest([3, 2, 1, 5, 6, 4], 2), 5);
test('with duplicates', findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4);
test('largest', findKthLargest([1, 2, 3], 1), 3);
test('smallest', findKthLargest([1, 2, 3], 3), 1);
test('single element', findKthLargest([7], 1), 7);
test('all identical', findKthLargest([2, 2, 2], 2), 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
61const 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)}`)
);

// A binary min-heap. 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 p = (i - 1) >> 1;
      if (this.compare(this.a[p], this.a[i]) <= 0) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  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;
  }
}

function kClosest(points, k) {
  // No sqrt: comparing squares gives the same order.
  const distance = ([x, y]) => x * x + y * y;

  // Max-heap on distance, so the FARTHEST of the current best is on top.
  const heap = new Heap((a, b) => distance(b) - distance(a));

  for (const point of points) {
    heap.push(point);
    if (heap.size > k) heap.pop();            // drop the farthest
  }
  return heap.a;
}

const shape = (points) => [...points].sort((a, b) => a[0] - b[0] || a[1] - b[1]);

test('one point', shape(kClosest([[1, 3], [-2, 2]], 1)), [[-2, 2]]);
test('two points', shape(kClosest([[3, 3], [5, -1], [-2, 4]], 2)), [[-2, 4], [3, 3]]);
test('k equals the count', shape(kClosest([[1, 1], [2, 2]], 2)), [[1, 1], [2, 2]]);
test('origin included', shape(kClosest([[0, 0], [9, 9]], 1)), [[0, 0]]);
test('single point', shape(kClosest([[4, 5]], 1)), [[4, 5]]);

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
28const 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 leastInterval(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);

  const most = Math.max(...counts.values());
  // How many tasks are tied at that maximum frequency?
  let tied = 0;
  for (const c of counts.values()) if (c === most) tied++;

  // The frame the most frequent task forces, plus its tied partners.
  const framed = (most - 1) * (n + 1) + tied;

  // If there are enough distinct tasks to fill every gap, nothing idles.
  return Math.max(framed, tasks.length);
}

test('cooldown 2', leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2), 8);
test('no cooldown', leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 0), 6);
test('long cooldown', leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 3), 10);
test('single task', leastInterval(['A'], 5), 1);
test('all distinct', leastInterval(['A', 'B', 'C'], 2), 3);
test('enough filler, no idling', leastInterval(['A', 'A', 'B', 'C', 'D', 'E'], 1), 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
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
81const 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)}`)
);

// A binary min-heap. 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 p = (i - 1) >> 1;
      if (this.compare(this.a[p], this.a[i]) <= 0) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  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;
  }
}

class MedianFinder {
  constructor() {
    this.low = new Heap((a, b) => b - a);     // max-heap: the smaller half
    this.high = new Heap();                    // min-heap: the larger half
  }

  addNum(value) {
    // Push into low, then hand its largest to high. The unconditional move
    // guarantees every element in low is <= every element in high.
    this.low.push(value);
    this.high.push(this.low.pop());

    // Rebalance so low is never smaller than high.
    if (this.high.size > this.low.size) this.low.push(this.high.pop());
  }

  findMedian() {
    if (this.low.size > this.high.size) return this.low.peek();
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

const m = new MedianFinder();
m.addNum(1);
test('one value', m.findMedian(), 1);
m.addNum(2);
test('two values', m.findMedian(), 1.5);
m.addNum(3);
test('three values', m.findMedian(), 2);

const m2 = new MedianFinder();
for (const v of [5, 15, 1, 3]) m2.addNum(v);
test('unsorted arrivals', m2.findMedian(), 4);

const m3 = new MedianFinder();
for (const v of [-1, -2, -3]) m3.addNum(v);
test('negatives', m3.findMedian(), -2);

const m4 = new MedianFinder();
for (const v of [2, 2, 2, 2]) m4.addNum(v);
test('all identical', m4.findMedian(), 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
38const 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 numIslands(grid) {
  if (!grid.length) return 0;
  // Copy so the caller's grid is untouched.
  const g = grid.map(row => [...row]);
  const rows = g.length, cols = g[0].length;
  let islands = 0;

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (g[r][c] !== '1') return;             // water, or already sunk
    g[r][c] = '0';                            // mark BEFORE recursing
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (g[r][c] === '1') { islands++; sink(r, c); }

  return islands;
}

test('three islands', numIslands([
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
]), 3);
test('one big island', numIslands([['1', '1'], ['1', '1']]), 1);
test('all water', numIslands([['0', '0'], ['0', '0']]), 0);
test('single land cell', numIslands([['1']]), 1);
test('diagonal does not connect', numIslands([['1', '0'], ['0', '1']]), 2);
test('empty grid', numIslands([]), 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
36const 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 maxAreaOfIsland(grid) {
  if (!grid.length) return 0;
  const g = grid.map(row => [...row]);
  const rows = g.length, cols = g[0].length;

  // Returns the size of the blob consumed from here.
  function measure(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== 1) return 0;
    g[r][c] = 0;
    return 1 + measure(r + 1, c) + measure(r - 1, c)
             + measure(r, c + 1) + measure(r, c - 1);
  }

  let best = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (g[r][c] === 1) best = Math.max(best, measure(r, c));

  return best;
}

// Two islands: three cells top-left, and five in the bottom-right block
// (the lone 1 at row 1 joins them via the cell directly below it).
test('largest of several', maxAreaOfIsland([
  [1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1],
]), 5);
test('one cell', maxAreaOfIsland([[1]]), 1);
test('no land', maxAreaOfIsland([[0, 0], [0, 0]]), 0);
test('whole grid', maxAreaOfIsland([[1, 1], [1, 1]]), 4);
test('a long snake', maxAreaOfIsland([[1, 1, 1], [0, 0, 1], [1, 1, 1]]), 7);

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
45const 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 orangesRotting(grid) {
  const g = grid.map(row => [...row]);
  const rows = g.length, cols = g[0].length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  const queue = [];
  let fresh = 0;
  // Seed with EVERY rotten orange: multi-source BFS.
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (g[r][c] === 2) queue.push([r, c]);
      else if (g[r][c] === 1) fresh++;
    }

  let minutes = 0, head = 0;
  while (head < queue.length && fresh > 0) {
    const levelSize = queue.length - head;    // one minute's worth
    minutes++;
    for (let i = 0; i < levelSize; i++) {
      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 (g[nr][nc] !== 1) continue;
        g[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}

test('four minutes', orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]), 4);
test('one unreachable', orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]), -1);
test('nothing fresh', orangesRotting([[0, 2]]), 0);
test('no rotten source', orangesRotting([[1]]), -1);
test('empty cells only', orangesRotting([[0, 0]]), 0);
test('already all rotten', orangesRotting([[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
36const 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 Node(val, neighbors = []) { this.val = val; this.neighbors = neighbors; }

function cloneGraph(node, copies = new Map()) {
  if (!node) return null;
  if (copies.has(node)) return copies.get(node);      // already cloned

  const copy = new Node(node.val);
  copies.set(node, copy);                              // record BEFORE recursing

  for (const neighbor of node.neighbors) {
    copy.neighbors.push(cloneGraph(neighbor, copies));
  }
  return copy;
}

// Build a square: 1-2-3-4-1
const a = new Node(1), b = new Node(2), c = new Node(3), d = new Node(4);
a.neighbors = [b, d]; b.neighbors = [a, c]; c.neighbors = [b, d]; d.neighbors = [a, c];

const cloned = cloneGraph(a);
test('root value', cloned.val, 1);
test('neighbour values', cloned.neighbors.map(n => n.val), [2, 4]);
test('it is a copy, not the original', cloned === a, false);
test('neighbours are copies too', cloned.neighbors[0] === b, false);
test('the cycle is preserved', cloned.neighbors[0].neighbors[0] === cloned, true);
test('walks all the way round', cloned.neighbors[0].neighbors[1].neighbors[1].val, 4);
test('null input', cloneGraph(null), null);

const lone = new Node(7);
test('single node', cloneGraph(lone).val, 7);

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
36const 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 canFinish(numCourses, prerequisites) {
  const dependents = Array.from({ length: numCourses }, () => []);
  const remaining = new Array(numCourses).fill(0);

  // [a, b] means b must come before a, so the edge runs b -> a.
  for (const [a, b] of prerequisites) {
    dependents[b].push(a);
    remaining[a]++;
  }

  const queue = [];
  for (let c = 0; c < numCourses; c++) if (remaining[c] === 0) queue.push(c);

  let taken = 0;
  for (let head = 0; head < queue.length; head++) {
    taken++;
    for (const next of dependents[queue[head]]) {
      if (--remaining[next] === 0) queue.push(next);   // now unblocked
    }
  }
  return taken === numCourses;      // short of the total means a cycle
}

test('possible', canFinish(2, [[1, 0]]), true);
test('circular', canFinish(2, [[1, 0], [0, 1]]), false);
test('no prerequisites', canFinish(3, []), true);
test('chain', canFinish(4, [[1, 0], [2, 1], [3, 2]]), true);
test('diamond', canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]), true);
test('three-cycle', canFinish(3, [[0, 1], [1, 2], [2, 0]]), false);
test('single course', canFinish(1, []), 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
32const 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 findOrder(numCourses, prerequisites) {
  const dependents = Array.from({ length: numCourses }, () => []);
  const remaining = new Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    dependents[b].push(a);
    remaining[a]++;
  }

  const order = [];
  for (let c = 0; c < numCourses; c++) if (remaining[c] === 0) order.push(c);

  for (let head = 0; head < order.length; head++) {
    for (const next of dependents[order[head]]) {
      if (--remaining[next] === 0) order.push(next);
    }
  }
  return order.length === numCourses ? order : [];
}

test('single edge', findOrder(2, [[1, 0]]), [0, 1]);
test('no constraints', findOrder(2, []), [0, 1]);
test('chain', findOrder(4, [[1, 0], [2, 1], [3, 2]]), [0, 1, 2, 3]);
test('impossible', findOrder(2, [[0, 1], [1, 0]]), []);
test('one course', findOrder(1, []), [0]);
test('branching', findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]), [0, 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
42const 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) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];   // path compression
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;                       // already joined
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.groups--;
    return true;
  }
}

function countComponents(n, edges) {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.groups;
}

test('two components', countComponents(5, [[0, 1], [1, 2], [3, 4]]), 2);
test('one component', countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]]), 1);
test('no edges', countComponents(4, []), 4);
test('single node', countComponents(1, []), 1);
test('redundant edges', countComponents(3, [[0, 1], [1, 2], [0, 2]]), 1);
test('self loop', countComponents(2, [[0, 0]]), 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
62const 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 pacificAtlantic(heights) {
  if (!heights.length) return [];
  const rows = heights.length, cols = heights[0].length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  const flood = (starts) => {
    const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
    const queue = [...starts];
    for (const [r, c] of starts) seen[r][c] = true;

    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 (seen[nr][nc]) continue;
        // Walking UPHILL: water would have flowed the other way.
        if (heights[nr][nc] < heights[r][c]) continue;
        seen[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }
    return seen;
  };

  const pacificEdge = [], atlanticEdge = [];
  for (let r = 0; r < rows; r++) {
    pacificEdge.push([r, 0]);
    atlanticEdge.push([r, cols - 1]);
  }
  for (let c = 0; c < cols; c++) {
    pacificEdge.push([0, c]);
    atlanticEdge.push([rows - 1, c]);
  }

  const pacific = flood(pacificEdge), atlantic = flood(atlanticEdge);
  const out = [];
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (pacific[r][c] && atlantic[r][c]) out.push([r, c]);

  return out;
}

const grid = [
  [1, 2, 2, 3, 5],
  [3, 2, 3, 4, 4],
  [2, 4, 5, 3, 1],
  [6, 7, 1, 4, 5],
  [5, 1, 1, 2, 4],
];
test('classic count', pacificAtlantic(grid).length, 7);
test('single cell reaches both', pacificAtlantic([[1]]), [[0, 0]]);
test('flat grid: every cell', pacificAtlantic([[1, 1], [1, 1]]).length, 4);
test('empty', pacificAtlantic([]), []);
test('one row', pacificAtlantic([[1, 2, 3]]).length, 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
73const 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 {
  constructor(compare = (a, b) => a - b) { this.a = []; this.compare = compare; }
  get size() { return this.a.length; }
  push(v) {
    this.a.push(v);
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.compare(this.a[p], this.a[i]) <= 0) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  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;
  }
}

function networkDelayTime(times, n, start) {
  const adjacency = new Map();
  for (const [from, to, weight] of times) {
    if (!adjacency.has(from)) adjacency.set(from, []);
    adjacency.get(from).push([to, weight]);
  }

  const best = new Map([[start, 0]]);
  const heap = new Heap((a, b) => a[0] - b[0]);       // [distance, node]
  heap.push([0, start]);

  while (heap.size) {
    const [distance, node] = heap.pop();
    // A better route to this node was already settled: this entry is stale.
    if (distance > (best.get(node) ?? Infinity)) continue;

    for (const [next, weight] of adjacency.get(node) || []) {
      const candidate = distance + weight;
      if (candidate < (best.get(next) ?? Infinity)) {
        best.set(next, candidate);
        heap.push([candidate, next]);
      }
    }
  }

  if (best.size !== n) return -1;                      // something unreachable
  return Math.max(...best.values());
}

test('classic', networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2), 2);
test('two nodes', networkDelayTime([[1, 2, 1]], 2, 1), 1);
test('unreachable', networkDelayTime([[1, 2, 1]], 2, 2), -1);
test('single node', networkDelayTime([], 1, 1), 0);
test('prefers the cheaper route', networkDelayTime([[1, 2, 9], [1, 3, 1], [3, 2, 1]], 3, 1), 2);
test('parallel edges', networkDelayTime([[1, 2, 5], [1, 2, 2]], 2, 1), 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
28const 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 subsets(nums) {
  const results = [];

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

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

test('three elements', subsets([1, 2, 3]).length, 8);
test('contents', subsets([1, 2]), [[], [1], [1, 2], [2]]);
test('single', subsets([0]), [[], [0]]);
test('empty input', subsets([]), [[]]);
test('four elements', subsets([1, 2, 3, 4]).length, 16);
test('the empty subset is included', subsets([9])[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
32const 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 permute(nums) {
  const results = [];
  const 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: any unused element is next
      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;
}

test('three elements', permute([1, 2, 3]).length, 6);
test('contents', permute([0, 1]), [[0, 1], [1, 0]]);
test('single', permute([1]), [[1]]);
test('four elements', permute([1, 2, 3, 4]).length, 24);
test('all are distinct', new Set(permute([1, 2, 3]).map(p => p.join(''))).size, 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
31const 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 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 the rest 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;
}

test('classic', combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]);
test('multiple ways', combinationSum([2, 3, 5], 8), [[2, 2, 2, 2], [2, 3, 3], [3, 5]]);
test('impossible', combinationSum([2], 1), []);
test('exact single', combinationSum([7], 7), [[7]]);
test('repeat one candidate', combinationSum([3], 9), [[3, 3, 3]]);
test('target of zero', combinationSum([1, 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
31const 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 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++) {
      // i > start, NOT i > 0: block repeats as siblings, allow them deeper.
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      current.push(sorted[i]);
      walk(i + 1, current);
      current.pop();
    }
  }

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

test('one duplicate', subsetsWithDup([1, 2, 2]), [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]);
test('count is six', subsetsWithDup([1, 2, 2]).length, 6);
test('all identical', subsetsWithDup([2, 2, 2]), [[], [2], [2, 2], [2, 2, 2]]);
test('no duplicates behaves normally', subsetsWithDup([1, 2]).length, 4);
test('single', subsetsWithDup([0]), [[], [0]]);
test('two pairs', subsetsWithDup([1, 1, 2, 2]).length, 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
26const 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 generateParenthesis(n) {
  const results = [];

  function walk(current, open, close) {
    if (current.length === 2 * n) { results.push(current); return; }

    if (open < n) walk(current + '(', open + 1, close);
    if (close < open) walk(current + ')', open, close + 1);   // never over-close
  }

  walk('', 0, 0);
  return results;
}

test('n = 1', generateParenthesis(1), ['()']);
test('n = 2', generateParenthesis(2), ['(())', '()()']);
test('n = 3 count', generateParenthesis(3).length, 5);
test('n = 4 count', generateParenthesis(4).length, 14);
test('n = 0', generateParenthesis(0), ['']);
test('every result is the right length', generateParenthesis(3).every(s => s.length === 6), 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
40const 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 exist(board, word) {
  const rows = board.length, cols = board[0].length;
  const grid = board.map(row => [...row]);        // do not disturb the caller's

  function search(r, c, index) {
    if (index === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (grid[r][c] !== word[index]) return false;

    const saved = grid[r][c];
    grid[r][c] = '#';                              // mark as used on THIS path

    const found = search(r + 1, c, index + 1) || search(r - 1, c, index + 1) ||
                  search(r, c + 1, index + 1) || search(r, c - 1, index + 1);

    grid[r][c] = saved;                            // restore for other paths
    return found;
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (search(r, c, 0)) return true;

  return false;
}

const board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']];
test('winding path', exist(board, 'ABCCED'), true);
test('short word', exist(board, 'SEE'), true);
test('cannot reuse a cell', exist(board, 'ABCB'), false);
test('single letter', exist([['A']], 'A'), true);
test('absent letter', exist([['A']], 'B'), false);
test('whole row', exist([['A', 'B']], 'AB'), true);
test('backwards', exist([['A', 'B']], 'BA'), 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
25const 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 climbStairs(n) {
  // Only the previous two values are ever needed, so no table.
  let twoBack = 1, oneBack = 1;

  for (let i = 2; i <= n; i++) {
    const current = oneBack + twoBack;
    twoBack = oneBack;
    oneBack = current;
  }
  return oneBack;
}

test('two steps', climbStairs(2), 2);
test('three steps', climbStairs(3), 3);
test('one step', climbStairs(1), 1);
test('zero steps', climbStairs(0), 1);
test('five steps', climbStairs(5), 8);
test('tenth', climbStairs(10), 89);
test('no overflow at 40', climbStairs(40), 165580141);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const 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 rob(nums) {
  let skip = 0, take = 0;      // best excluding / including the previous house

  for (const money of nums) {
    // Robbing this house means we could not have robbed the previous one.
    const robThis = skip + money;
    skip = Math.max(skip, take);
    take = robThis;
  }
  return Math.max(skip, take);
}

test('alternating', rob([1, 2, 3, 1]), 4);
test('skip two', rob([2, 7, 9, 3, 1]), 12);
test('single house', rob([5]), 5);
test('empty street', rob([]), 0);
test('two houses', rob([2, 1]), 2);
test('all equal', rob([4, 4, 4, 4]), 8);

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
29const 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 rob(nums) {
  if (nums.length === 1) return nums[0];      // both slices would be empty

  const linear = (houses) => {
    let skip = 0, take = 0;
    for (const money of houses) {
      const robThis = skip + money;
      skip = Math.max(skip, take);
      take = robThis;
    }
    return Math.max(skip, take);
  };

  // Either the first house is out, or the last one is. Never both in.
  return Math.max(linear(nums.slice(0, -1)), linear(nums.slice(1)));
}

test('circle forces a choice', rob([2, 3, 2]), 3);
test('classic', rob([1, 2, 3, 1]), 4);
test('single house', rob([5]), 5);
test('two houses', rob([1, 2]), 2);
test('four equal', rob([4, 4, 4, 4]), 8);
test('longer', rob([1, 2, 3, 4, 5, 1]), 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
25const 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 coinChange(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];
}

test('classic', coinChange([1, 2, 5], 11), 3);
test('impossible', coinChange([2], 3), -1);
test('zero amount', coinChange([1], 0), 0);
test('greedy would fail here', coinChange([1, 3, 4], 6), 2);
test('exact single coin', coinChange([7], 7), 1);
test('many of one coin', coinChange([2], 8), 4);
test('no coins', coinChange([], 5), -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
26const 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 change(amount, coins) {
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;                                 // one way to make nothing

  // Coins OUTSIDE: each combination is built in one fixed coin order,
  // so 1+2 and 2+1 are never counted separately.
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      ways[a] += ways[a - coin];
    }
  }
  return ways[amount];
}

test('classic', change(5, [1, 2, 5]), 4);
test('impossible', change(3, [2]), 0);
test('exact', change(10, [10]), 1);
test('zero amount', change(0, [1, 2]), 1);
test('only ones', change(4, [1]), 1);
test('order does not matter', change(4, [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
30const 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 lengthOfLIS(nums) {
  // tails[k] = the smallest value that can end an increasing run of length k+1.
  const tails = [];

  for (const n of nums) {
    // Binary search for the first tail >= n.
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (tails[mid] < n) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = n;                     // extend, or improve an existing tail
  }
  return tails.length;
}

test('classic', lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]), 4);
test('with duplicates', lengthOfLIS([0, 1, 0, 3, 2, 3]), 4);
test('all identical', lengthOfLIS([7, 7, 7, 7]), 1);
test('single', lengthOfLIS([1]), 1);
test('empty', lengthOfLIS([]), 0);
test('strictly decreasing', lengthOfLIS([5, 4, 3, 2]), 1);
test('strictly increasing', lengthOfLIS([1, 2, 3, 4]), 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
26const 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 longestCommonSubsequence(a, b) {
  // Row and column 0 mean "empty prefix", so they stay 0 and remove edge cases.
  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
        : Math.max(table[i - 1][j], table[i][j - 1]);     // drop one or the other
    }
  }
  return table[a.length][b.length];
}

test('classic', longestCommonSubsequence('abcde', 'ace'), 3);
test('identical', longestCommonSubsequence('abc', 'abc'), 3);
test('nothing in common', longestCommonSubsequence('abc', 'def'), 0);
test('one empty', longestCommonSubsequence('', 'abc'), 0);
test('single match', longestCommonSubsequence('a', 'a'), 1);
test('interleaved', longestCommonSubsequence('bsbininm', 'jmjkbkjkv'), 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
28const 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 wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const reachable = new Array(s.length + 1).fill(false);
  reachable[0] = true;                          // the empty prefix

  for (let end = 1; end <= s.length; end++) {
    for (let start = 0; start < end; start++) {
      if (reachable[start] && words.has(s.slice(start, end))) {
        reachable[end] = true;
        break;                                   // one way is enough
      }
    }
  }
  return reachable[s.length];
}

test('two words', wordBreak('leetcode', ['leet', 'code']), true);
test('reuses a word', wordBreak('applepenapple', ['apple', 'pen']), true);
test('impossible', wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']), false);
test('single letter', wordBreak('a', ['a']), true);
test('not in the dictionary', wordBreak('b', ['a']), false);
test('greedy would fail', wordBreak('aaaaaaa', ['aaaa', 'aaa']), 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
29const 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 canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;             // cannot halve an odd total

  const target = total / 2;
  const reachable = new Array(target + 1).fill(false);
  reachable[0] = true;                            // a sum of zero always is

  for (const n of nums) {
    // Downward, so this number is not used twice in one pass.
    for (let sum = target; sum >= n; sum--) {
      if (reachable[sum - n]) reachable[sum] = true;
    }
  }
  return reachable[target];
}

test('splittable', canPartition([1, 5, 11, 5]), true);
test('not splittable', canPartition([1, 2, 3, 5]), false);
test('odd total', canPartition([1, 2]), false);
test('equal pair', canPartition([2, 2]), true);
test('single element', canPartition([1]), false);
test('four equal', canPartition([3, 3, 3, 3]), true);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const 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 uniquePaths(m, n) {
  // One row, reused. row[c] means "ways to reach column c on the current row".
  const row = new Array(n).fill(1);              // the top row: one path each

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      row[c] += row[c - 1];                       // from above + from the left
    }
  }
  return row[n - 1];
}

test('3 by 7', uniquePaths(3, 7), 28);
test('3 by 2', uniquePaths(3, 2), 3);
test('single row', uniquePaths(1, 5), 1);
test('single column', uniquePaths(5, 1), 1);
test('one cell', uniquePaths(1, 1), 1);
test('square', uniquePaths(3, 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
31const 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 longestPalindrome(s) {
  if (s.length < 2) return s;
  let bestStart = 0, bestLength = 1;

  const grow = (left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; }
    // The loop overshoots by one on each side.
    const length = right - left - 1;
    if (length > bestLength) { bestLength = length; bestStart = left + 1; }
  };

  for (let i = 0; i < s.length; i++) {
    grow(i, i);          // odd length, centred on a character
    grow(i, i + 1);      // even length, centred on a gap
  }
  return s.slice(bestStart, bestStart + bestLength);
}

test('odd centre', longestPalindrome('babad'), 'bab');
test('even centre', longestPalindrome('cbbd'), 'bb');
test('single char', longestPalindrome('a'), 'a');
test('whole string', longestPalindrome('racecar'), 'racecar');
test('no repeat', longestPalindrome('abcd'), 'a');
test('empty', longestPalindrome(''), '');
test('all identical', longestPalindrome('aaaa'), 'aaaa');

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
26const 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 maxSubArray(nums) {
  if (nums.length === 0) return 0;

  // Start from nums[0], not 0, or an all-negative array answers 0.
  let running = nums[0], best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Extend, or start fresh here — whichever is larger.
    running = Math.max(nums[i], running + nums[i]);
    best = Math.max(best, running);
  }
  return best;
}

test('classic', maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
test('single element', maxSubArray([1]), 1);
test('all positive', maxSubArray([5, 4, -1, 7, 8]), 23);
test('all negative', maxSubArray([-3, -1, -2]), -1);
test('single negative', maxSubArray([-1]), -1);
test('empty', maxSubArray([]), 0);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22const 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 canJump(nums) {
  let furthest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > furthest) return false;             // unreachable, and so is the end
    furthest = Math.max(furthest, i + nums[i]);
  }
  return true;
}

test('reachable', canJump([2, 3, 1, 1, 4]), true);
test('blocked by a zero', canJump([3, 2, 1, 0, 4]), false);
test('single element', canJump([0]), true);
test('one step needed', canJump([1, 0]), true);
test('cannot start', canJump([0, 1]), false);
test('big first jump', canJump([5, 0, 0, 0, 0]), 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
27const 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 jump(nums) {
  let jumps = 0, currentEnd = 0, furthest = 0;

  // Stop before the last index: arriving there needs no further jump.
  for (let i = 0; i < nums.length - 1; i++) {
    furthest = Math.max(furthest, i + nums[i]);

    if (i === currentEnd) {          // exhausted this range: must jump now
      jumps++;
      currentEnd = furthest;
    }
  }
  return jumps;
}

test('classic', jump([2, 3, 1, 1, 4]), 2);
test('alternative', jump([2, 3, 0, 1, 4]), 2);
test('already there', jump([0]), 0);
test('one jump', jump([1, 1]), 1);
test('two jumps', jump([1, 1, 1]), 2);
test('single big jump', jump([5, 1, 1, 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
27const 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 partitionLabels(s) {
  const lastIndex = new Map();
  for (let i = 0; i < s.length; i++) lastIndex.set(s[i], i);

  const sizes = [];
  let start = 0, end = 0;

  for (let i = 0; i < s.length; i++) {
    // This piece must stretch at least to this character's final appearance.
    end = Math.max(end, lastIndex.get(s[i]));
    if (i === end) { sizes.push(end - start + 1); start = i + 1; }
  }
  return sizes;
}

test('classic', partitionLabels('ababcbacadefegdehijhklij'), [9, 7, 8]);
test('one piece', partitionLabels('eccbbbbdec'), [10]);
test('single character', partitionLabels('a'), [1]);
test('all distinct', partitionLabels('abc'), [1, 1, 1]);
test('repeated pair', partitionLabels('abab'), [4]);
test('empty', partitionLabels(''), []);

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
30const 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 merge(intervals) {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [sorted[0].slice()];               // copy: never mutate 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;
}

test('classic', merge([[1, 3], [2, 6], [8, 10], [15, 18]]), [[1, 6], [8, 10], [15, 18]]);
test('touching merges', merge([[1, 4], [4, 5]]), [[1, 5]]);
test('fully contained', merge([[1, 10], [2, 3]]), [[1, 10]]);
test('unsorted input', merge([[5, 6], [1, 2]]), [[1, 2], [5, 6]]);
test('single interval', merge([[1, 4]]), [[1, 4]]);
test('empty', merge([]), []);
test('all identical', merge([[1, 2], [1, 2]]), [[1, 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
35const 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 insert(intervals, newInterval) {
  const out = [];
  let [start, end] = newInterval;
  let i = 0;

  // Phase 1: everything that finishes before the new interval begins.
  while (i < intervals.length && intervals[i][1] < start) out.push(intervals[i++]);

  // Phase 2: absorb everything that overlaps.
  while (i < intervals.length && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  out.push([start, end]);

  // Phase 3: the rest, untouched.
  while (i < intervals.length) out.push(intervals[i++]);

  return out;
}

test('simple overlap', insert([[1, 3], [6, 9]], [2, 5]), [[1, 5], [6, 9]]);
test('absorbs several', insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]),
  [[1, 2], [3, 10], [12, 16]]);
test('into an empty list', insert([], [5, 7]), [[5, 7]]);
test('swallowed whole', insert([[1, 5]], [2, 3]), [[1, 5]]);
test('goes after', insert([[1, 5]], [6, 8]), [[1, 5], [6, 8]]);
test('goes before', insert([[3, 5]], [1, 2]), [[1, 2], [3, 5]]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25const 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 eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  // Sort by END. This is the whole insight.
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 1, lastEnd = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= lastEnd) { kept++; lastEnd = sorted[i][1]; }
  }
  return intervals.length - kept;
}

test('remove one', eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]), 1);
test('all identical', eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]), 2);
test('already disjoint', eraseOverlapIntervals([[1, 2], [2, 3]]), 0);
test('empty', eraseOverlapIntervals([]), 0);
test('single', eraseOverlapIntervals([[1, 2]]), 0);
test('nested intervals', eraseOverlapIntervals([[1, 100], [11, 22], [1, 11], [2, 12]]), 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
30const 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 minMeetingRooms(intervals) {
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);       // a room is taken
    events.push([end, -1]);        // a room is freed
  }

  // On a tie, -1 sorts before +1, so a room frees up before the next start.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

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

test('two rooms', minMeetingRooms([[0, 30], [5, 10], [15, 20]]), 2);
test('one room', minMeetingRooms([[7, 10], [2, 4]]), 1);
test('three overlapping', minMeetingRooms([[1, 5], [2, 6], [3, 7]]), 3);
test('back to back needs one', minMeetingRooms([[1, 2], [2, 3], [3, 4]]), 1);
test('single meeting', minMeetingRooms([[1, 2]]), 1);
test('no meetings', minMeetingRooms([]), 0);