Smallest Range Covering Elements from K Lists — Solution

Problem

Given k sorted lists of integers, find the smallest range [a, b] such that at least one number from each list falls within that range. "Smallest" means the shortest interval; if two ranges have the same length, prefer the one with the smaller starting value.

Example:

• Input: lists = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• Output: [20, 24]
• Explanation: 24 is from list 0, 20 is from list 1, and 22 is from list 2 — all fall within [20, 24], which has length 4. No shorter range covers all three lists.

Counter-example: The range [0, 5] also contains one element from each list (0 from list 1, 4 from list 0, 5 from list 2), but its length is 5, making it worse than [20, 24].

Intuition

At any moment, if we pick exactly one element from each list, those elements define a candidate range. To minimize the range, we want those chosen elements to be as close together as possible. The key insight: the range width is always determined by the gap between the smallest and largest of our chosen elements. We can shrink this gap by replacing the current minimum with the next element from that list — no other swap can reduce the lower bound. A min-heap efficiently tracks the minimum, while we separately track the running maximum, giving us each candidate range in O(log k) time.

Solution — Min-Heap with Running Maximum

Seed the heap with the first element from each list, tracking the current maximum. Each iteration: record the range [heap_min, current_max], pop the minimum, and push the next element from that list. Stop when any list runs out of elements, because from that point we can no longer cover every list.

1. Push (value, list_index, element_index) into a min-heap for the first element of each list.
2. Initialize current_max to the maximum of all those first elements.
3. Track best_range starting as [first_heap_min, current_max].
4. Loop: pop the minimum element from the heap.
5. Push the next element from the same list into the heap and update current_max if the new value is larger.
6. If the new range [heap_min, current_max] is smaller than best_range, update it.
7. Stop if the popped list has no more elements.

1import heapq
2
3def smallest_range(nums):
4    # Each heap entry: (value, list_index, element_index)
5    heap = []
6    current_max = float('-inf')
7
8    for list_idx, sorted_list in enumerate(nums):
9        heapq.heappush(heap, (sorted_list[0], list_idx, 0))
10        current_max = max(current_max, sorted_list[0])
11
12    best_range = [heap[0][0], current_max]
13
14    while heap:
15        current_min, list_idx, elem_idx = heapq.heappop(heap)
16
17        next_elem_idx = elem_idx + 1
18        if next_elem_idx == len(nums[list_idx]):
19            # This list is exhausted — we can no longer cover every list
20            break
21
22        next_val = nums[list_idx][next_elem_idx]
23        heapq.heappush(heap, (next_val, list_idx, next_elem_idx))
24        current_max = max(current_max, next_val)
25
26        # Update best if this range is strictly smaller (or equal length, smaller start)
27        if current_max - heap[0][0] < best_range[1] - best_range[0]:
28            best_range = [heap[0][0], current_max]
29
30    return best_range

Time: O(n log k) where n is the total number of elements across all lists and k is the number of lists — each element is pushed and popped from the heap exactly once, and each heap operation costs O(log k).

Space: O(k) — the heap holds exactly one element per list at all times.

Complexity Summary

Common Mistakes

• Forgetting to initialize current_max from the first elements — current_max must start as the maximum of all k initial values, not 0 or negative infinity applied lazily. If you initialize it lazily inside the loop, the very first range check will compare against a stale maximum.
• Stopping when the heap is empty instead of when a list is exhausted — if any list runs out, you can no longer guarantee one element per list, so the correct exit condition is "next element index >= list size", not "heap empty".
• Re-reading heap[0] after the pop without checking it's the new minimum — after popping and pushing, the new heap minimum is heap[0] (or heap.peek()); reading it before the push gives the old minimum, producing an incorrect range.
• Only tracking the minimum via the heap but not current_max separately — finding the current max from all k heap elements each iteration would cost O(k) per step, turning the whole solution O(nk) instead of O(n log k). current_max must be maintained incrementally and can only increase.
• Using a max-heap and trying to mirror the logic — the algorithm is designed around evicting the minimum to narrow the range from below; flipping it produces unnecessary complexity and is harder to get right.

Related Problems

• merge-k-sorted-lists — same min-heap pattern of merging k sorted streams one element at a time
• k-closest-points-to-origin — heap used to efficiently select the k smallest elements across a pool
• kth-largest-element-in-an-array — heap-based selection to extract the k-th ordered element
• top-k-frequent-elements — min-heap of size k to maintain the top-k candidates while scanning
• k-th-smallest-prime-fraction — heap search across multiple implicitly sorted sequences, structurally identical to this problem's multi-list sweep