Smallest range covering elements from K lists
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]
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;}