Smallest Range Covering Elements from K Lists

You have k sorted lists. Find the smallest [a, b] range such that every list contributes at least one value inside it. With [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], the answer is [20,24]: 24 from list 0, 20 from list 1, 22 from list 2.

The key insight: any valid range is anchored by the current minimum and maximum of the selected elements. Start with the first element of each list — that is the narrowest possible window at the left edge. Then repeatedly: shrink the range by advancing the list that holds the current minimum (its next element replaces it), track the best range seen, and stop when some list runs out. The min-heap gives the current minimum in O(log k); a simple variable tracks the maximum.

Approach in steps:

1. Seed a min-heap with the first element of each list; track the max.
2. Pop the min; if the range (max - min) beats the best, record it.
3. Advance that element's list; push its successor; if a list empties, stop.

import heapq
 
def smallestRange(nums):
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    hi = max(v for v, _, _ in heap)
    best = [heap[0][0], hi]
    while True:
        lo, i, j = heapq.heappop(heap)
        if hi - lo < best[1] - best[0]:
            best = [lo, hi]
        if j + 1 == len(nums[i]):
            return best
        nxt = nums[i][j + 1]
        hi = max(hi, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))

Time is O(n log k) for n total elements; space O(k).

Trickiest edge case: a list of length 1. Advancing it empties the list, which terminates the scan — the machine must return immediately, because no larger minimum can ever maintain coverage.