Smallest Range Covering Elements from K Lists

Difficulty: Hard · Pattern: K-Way Merge · Concept: Algorithms & Data Structures — Core Data Structures

Merge K Sorted Lists used a min-heap to merge everything into one sorted output. This problem reuses the exact same heap mechanism — track the current smallest unconsumed element per list — to answer a genuinely different question: find the smallest range [lo, hi] that contains at least one number from every one of the k lists.

The added difficulty: merging just needs the current minimum. This needs the minimum and a running maximum of everything currently "in play" across all k lists — every time the heap's minimum advances, the range's width might shrink, but only advancing the list that's currently behind can ever produce a better range (advancing anything else only risks losing coverage of some list entirely).

Your task: implement smallest_range(lists), where lists is k non-empty sorted lists. Return [lo, hi].

Implement it yourself

assert smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]) == [20, 24]
assert smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]]) == [1, 1]
assert smallest_range([[1], [1], [1]]) == [1, 1]
assert smallest_range([[1, 3], [2]]) == [1, 2]

Next: Rotting Oranges