Smallest range covering elements from K lists

Hard

Problem

Given k sorted lists, find the smallest range [a, b] that includes at least one number from each list. A range is smaller if it is narrower, or equally wide with a smaller a.

Example 1

Input:  [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20, 24]

Also asked as: Smallest range in “K” Lists

Test cases

Case 1

Input:    [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Expected: [20,24]

Case 2

Input:    [[1,2,3],[1,2,3],[1,2,3]]
Expected: [1,1]

Case 3

Input:    [[1],[2],[3]]
Expected: [1,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Min-heap of one element per list, track the running max

Time O(N log K)Space O(K)

Keep one pointer per list in a min-heap; the range is [heapMin, currentMax]. Pop the min, advance that list, update max. Stop when a list is exhausted.

function smallestRange(lists) {
let heap = lists.map((l, i) => [l[0], i, 0]);
heap.sort((a, b) => a[0] - b[0]);
let curMax = Math.max(...heap.map((x) => x[0]));
let best = [heap[0][0], curMax];
while (true) {
const [val, li, ei] = heap.shift();
if (curMax - val < best[1] - best[0]) best = [val, curMax];
if (ei + 1 === lists[li].length) break;
const nxt = [lists[li][ei + 1], li, ei + 1];
curMax = Math.max(curMax, nxt[0]);
let p = heap.findIndex((x) => x[0] > nxt[0]);
p === -1 ? heap.push(nxt) : heap.splice(p, 0, nxt);
}
return best;
}