Smallest Range Covering Elements from K Lists

Smallest Range Covering Elements from K Lists is a classic heap problem. You have several sorted lists, and you must find the shortest interval [a, b] that contains at least one number from every list. The trick is to always know the smallest current value, which is exactly what a min-heap gives you.

The slow way first

We could collect every value with a tag for which list it came from, sort them all together, and then slide a window over that merged sequence until it covers all k lists. That works, but merging and sliding over N total elements with bookkeeping is fiddly, and naively re-scanning the window is wasteful.

The question to ask: to shrink a window, which endpoint should I move? The width is max - min. The max is fixed by whatever the largest current value is, so the only way to make progress is to push the smallest value forward — and to do that I need to always know the current minimum cheaply.

The idea: a min-heap of one value per list

Keep a pointer into each sorted list and put each list's current value into a min-heap. At any moment the heap top is the global min, and we separately track curMax, the largest current value. The window [min, curMax] always covers all k lists, because every list contributes its current value.

Each step we pop the min, compare the current [min, curMax] against the best seen, then advance the list the min came from. We stop the instant any list is exhausted, because from then on we can no longer guarantee coverage of every list.

Walk through it

Step through the animation. Three sorted lists sit in rows with pointers p0, p1, p2. The smallest current value is popped each step; that list advances one cell, and the new value may raise curMax. The very first window [0, 5] turns out to be the tightest, and every later window is wider, so [0, 5] wins.

Pseudocode

put the first element of each list into a min-heap
curMax = the largest of those first elements
best = none
while the heap is not empty:
    (val, list r, index j) = pop the smallest
    if best is none or (curMax - val) < width(best):
        best = [val, curMax]
    if j is the last index of list r:
        stop -> that list is exhausted
    nxt = next value in list r
    curMax = max(curMax, nxt)
    push (nxt, r, j + 1)
return best

The Python solution

def smallest_range(lists):
    heap = [(row[0], r, 0) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    cur_max = max(row[0] for row in lists)
    best = None
    while heap:
        val, r, j = heapq.heappop(heap)
        if best is None or cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(lists[r]):
            return best
        nxt = lists[r][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, r, j + 1))

• We seed the heap with each list head as (value, list index, position), so popping gives the min plus where it came from.
• cur_max starts as the largest head and only ever grows, because pushing the next value can raise it but advancing never lowers it.
• Line 7 pops the current global minimum — the left edge of the window.
• Line 8 compares this window width cur_max - val against the best recorded width and updates best when it is strictly tighter.
• Line 10 is the stop condition: once the popped list has no next element, no future window can cover that list, so we return.

Complexity

The heap never holds more than k items (one per list), so memory is O(k). We touch every element at most once, each with an O(log k) heap operation, for O(N log k) total.

When this pattern shows up

Practice