Smallest Range Covering Elements from K Lists

Problem

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

Solution

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var smallestRange = function(nums) {
    const minHeap = new MinPriorityQueue({ priority: o => o.val });
    let max = -Infinity; // max value in minHeap;

    // insert the first element of each array in nums into our heap
    for (let i = 0; i < nums.length; i++) {
        // i, j is index of val in nums (ie. nums[i][j])
        minHeap.enqueue({ val: nums[i][0], i: i, j: 0 });
        max = Math.max(max, nums[i][0]);
    }

    const range = [-Infinity, Infinity]; // smallest range
    while (!minHeap.isEmpty()) {
        // use smallest element in heap as potential start range
        const { val, i, j } = minHeap.dequeue().element;
        if (max - val < range[1] - range[0]) {
            range[0] = val;
            range[1] = max;
        }

        // no more elements in nums[i] to go through
        if (j + 1 === nums[i].length) {
            break;
        }

        // enqueue next element in nums[i]
        minHeap.enqueue({ val: nums[i][j + 1], i, j: j + 1 });
        max = Math.max(max, nums[i][j + 1]);
    }
    return range;
};

We will use a min-heap minHeap to store one element from each of the k list in nums starting from left to right (ie. smallest to largest since each list is sorted in non-decreasing order). To minimize the range, we use minHeap to essentially slide across all possible ranges of the k values, one from each list, such that the k values are consecutive in sorted order. We check if the smallest value and largest value in minHeap produces a smaller range than our current smallest range range and update accordingly. Next, we remove the smallest value from minHeap, and push in the next smallest value from the same list that the removed element originated from. When the list of the removed element has no more elements, we can terminate and return range.

Problem​

Solution​

Problem

Solution