632. Smallest Range Covering Elements from K Lists

Description

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
• -105 <= nums[i][j] <= 105
• nums[i] is sorted in non-decreasing order.

 

Solutions

Solution: Sliding Window

• Time complexity: O((nk)log(nk))
• Space complexity: O(nk)

 

JavaScript

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
const smallestRange = function (nums) {
  const k = nums.length;
  const coverMap = new Map();
  const elements = nums.reduce((result, list, index) => {
    for (const num of list) {
      result.push({ num, index });
    }
    return result;
  }, []);
  let left = (coverCount = 0);
  let minRange = Number.MAX_SAFE_INTEGER;

  elements.sort((a, b) => a.num - b.num);

  for (let index = 0; index < elements.length; index++) {
    const element = elements[index];
    const count = coverMap.get(element.index) ?? 0;

    if (!count) coverCount += 1;
    coverMap.set(element.index, count + 1);

    while (coverCount === k) {
      const leftElement = elements[left];
      const range = element.num - leftElement.num;
      const leftCount = coverMap.get(leftElement.index);

      if (range < minRange) {
        minRange = range;
        result = [leftElement.num, element.num];
      }
      coverMap.set(leftElement.index, leftCount - 1);
      if (leftCount - 1 === 0) coverCount -= 1;
      left += 1;
    }
  }
  return result;
};