find intersection of N strictly sorted lists

findIntersection.js

// find intersection of 2 strictly sorted lists
function findIntersection(a: number[], b: number[]): number[] {
  let ai = 0, bi = 0, result = [];
  while (ai < a.length && bi < b.length) {
    if (a[ai] < b[bi]) ai++;
    else if (a[ai] > b[bi]) bi++;
    else { // they are equal
      result.push(a[ai]);
      ai++;
      bi++;
    }
  }
  return result;
}

// find intersection of N strictly sorted lists
function findIntersectionN(...lists: number[][]): number[] {
  if (!lists.length) return [];

  const result = [];
  const Mx = lists.map(() => 0);
  let NList = lists.length;
  let list = lists[0];
  let listI = 0;
  let listL = list.length;
  let M = -1; // current max number
  let Mi = 0; // last max index
  let i = 0;  // current processing index
  while (true) {
    // increase i until list[i] >= M
    while (i < listL && list[i] < M) i++;
    if (i >= listL) break;

    // max found, save and move to next list
    Mx[listI] = i;  // save current list index
    if (list[i] !== M) {
      M = list[i]; // save new max
      Mi = listI;  // save new max list
      // move to next list
      listI = (listI + 1) % NList;
      list = lists[listI];
      listL = list.length;
      i = Mx[listI];
      continue;
    }

    // not all list agree, move to next list
    if (listI !== Mi) {
      listI = (listI + 1) % NList;
      list = lists[listI];
      listL = list.length;
      i = Mx[listI];
      continue;
    }

    // last max found in all lists
    result.push(M);
    for (let j = 0; j < NList; j++) Mx[j]++; // next indices
    i = Mx[listI];
  }
  return result;
}

// test
function testIntersectionN() {
  const tests = [
    [
      [], // input 1
      [], // input 2
      [], // result
    ],
    [
      [],
      [1],
      [2, 3],
      [],
    ],
    [
      [1, 3],
      [2, 5],
      [4, 6],
      [],
    ],
    [
      [2, 4, 6, 7],
      [1, 3, 4, 5, 6],
      [4, 6],
    ],
    [
      [2, 5, 6, 8, 9, 14],
      [1, 3, 4, 5, 8, 9, 15],
      [1, 5, 8, 9, 10, 12],
      [5, 8, 9],
    ],
  ];

  for (let test of tests) {
    const lists = test.slice(0, test.length - 1);
    const expect = test[test.length - 1];
    const actual = findIntersectionN(...lists);
    assert.deepEqual(actual, expect);
  }
}