Smallest Range Covering Elements from K Lists

Intuition

We need a window [a, b] that touches every list at least once, and among all such windows we want the narrowest. If we hold exactly one candidate element from each list, the window covering them is [min, max] of the held elements. The lower bound is the smallest held element, so to possibly shrink the window we must advance the list that owns that minimum to its next larger value. A min-heap gives us the current minimum in O(log k), and we track the running maximum separately so the current range is always [heap-min, currentMax]. We record the best range each step and stop as soon as any list runs out, because that list can no longer be covered.

Algorithm walkthrough

1. 1Push the first element of each list into a min-heap as (value, listIndex, elementIndex), and track the maximum of these first elements as currentMax.
2. 2The current covering range is [heap minimum, currentMax]; if it is narrower than the best seen, record it.
3. 3Pop the minimum element from the heap.
4. 4If its list has a next element, push that element and update currentMax; otherwise stop, since this list can no longer be represented.
5. 5Repeat, always keeping exactly one element per list in the heap until one list is exhausted.
6. 6Return the best range found.

Implementation

import heapq

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        heap = []
        current_max = float('-inf')
        for i, arr in enumerate(nums):
            heap.append((arr[0], i, 0))
            current_max = max(current_max, arr[0])
        heapq.heapify(heap)

        best = [float('-inf'), float('inf')]
        while heap:
            val, i, j = heapq.heappop(heap)
            if current_max - val < best[1] - best[0]:
                best = [val, current_max]
            if j + 1 == len(nums[i]):
                break
            next_val = nums[i][j + 1]
            current_max = max(current_max, next_val)
            heapq.heappush(heap, (next_val, i, j + 1))
        return best