Given two arrays and an integer k, find k pairs of numbers with the smallest sum so that in each pair, each array contributes one number to the pair.

1-k-smallest-pairs.js

export function kSmallestPairs(list1, list2, k) {
  let result = [];
  const heap = new MinHeap();

  // we initialize our heap by pairing the first element of list2
  // with every element of list1
  // since our arrays are sorted, our heap will contain our first min pair
  for (let i = 0; i < list1.length; ++i) {
    const a = list1[i];
    const b = list2[0];
    heap.offer([a + b, i, 0]);
  }

  while (result.length < k && heap.size() > 0) {
    // pop a min pair from the heap
    const [_, index1, index2] = heap.poll();
    result.push([list1[index1], list2[index2]]);
    // now we are going to push the next pair to the heap
    // the pair we've just popped is a minimum pair where list2[index2] is involved,
    // so now we need to consider list2[index2 + 1], and pair it with the same element from list1
    const nextA = list1[index1];
    const nextB = list2[index2 + 1];
    if (nextA != null && nextB != null) {
      // handle cases when either index is out of the array bounds
      heap.offer([nextA + nextB, index1, index2 + 1]);
    }
  }

  // Your code will replace this placeholder return statement.
  return result;
}

2-README.md