Smallest Range Covering Elements from K Lists: Min-Heap Approach

Imagine you are comparing prices across multiple stores for different items. Each store has its own sorted price list, and you want to find the tightest price range that guarantees you can buy at least one item from every store. That is essentially what LeetCode 632: Smallest Range Covering Elements from K Lists asks you to solve. Given k sorted lists of integers, find the smallest range [a, b] such that at least one number from each list falls within [a, b].

Why this problem matters

This problem sits at the intersection of heaps, multi-pointer techniques, and range tracking. It tests whether you can coordinate movement across multiple sorted sequences simultaneously, which is a pattern that shows up in merge operations, streaming data, and interval problems.

The brute force approach of checking every possible pair of values is O(n^2) at best. The optimal solution uses a min-heap with k pointers, one per list, and runs in O(n log k) time. It is a direct extension of the "merge k sorted lists" pattern, but instead of building a merged output, you are tracking the window that covers all lists.

The approach

The core idea: maintain one pointer per list and always advance the pointer that points to the smallest value. Here is why that works.

At any moment, you have k pointers, one into each list. The range needed to cover all of them is [min_pointer_value, max_pointer_value]. To shrink this range, you have two options: increase the minimum or decrease the maximum. Since each list is sorted in ascending order, you can only move pointers forward (increasing values). So the only way to potentially shrink the range is to advance the pointer at the minimum, hoping the next value is closer to the current maximum.

A min-heap makes this efficient. Push the initial element from each list into the heap, track the running maximum, and repeatedly:

1. Pop the minimum from the heap (this gives you the current range [min, max]).
2. Check if this range is smaller than the best so far.
3. Advance the pointer for whichever list the minimum came from.
4. Push the next element from that list into the heap, updating the max if needed.
5. Stop when any list runs out (you can no longer cover all k lists).

import heapq

def smallestRange(nums):
    heap = []
    max_val = float('-inf')

    for i, row in enumerate(nums):
        heapq.heappush(heap, (row[0], i, 0))
        max_val = max(max_val, row[0])

    best = [float('-inf'), float('inf')]

    while True:
        min_val, list_idx, elem_idx = heapq.heappop(heap)
        if max_val - min_val < best[1] - best[0]:
            best = [min_val, max_val]
        if elem_idx + 1 == len(nums[list_idx]):
            break
        next_val = nums[list_idx][elem_idx + 1]
        heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
        max_val = max(max_val, next_val)

    return best

Step-by-step walkthrough

Let's trace through nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]. The answer is [20, 24].

Complexity analysis

Where n is the total number of elements across all k lists and k is the number of lists.

Each element gets pushed and popped from the heap at most once. Each heap operation costs O(log k) since the heap holds at most k elements (one per list). The maximum tracking is O(1) per step. Total: O(n log k).

Space is O(k) for the heap, which holds exactly one entry per list at any time.

Edge cases to watch for

• Single list. nums = [[1,2,3]]. The range is [1, 1] (or any single element). The heap has size 1, and the first pop gives you the answer immediately.
• All lists have one element. nums = [[1], [5], [3]]. The range must cover 1, 3, and 5, so the answer is [1, 5]. The algorithm pops the minimum (1), tries to advance L0, finds it exhausted, and stops.
• Overlapping values. nums = [[1,2,3], [1,2,3], [1,2,3]]. The answer is [1, 1]. All three lists start at 1, giving an initial range of size 0.
• Negative numbers. The algorithm works with negative values since it only compares magnitudes. No special handling needed.
• Large k, small lists. The heap stays at size k. If each list is short, the algorithm terminates quickly after one of them runs out.

The building blocks

This problem combines two building blocks that appear across many heap and multi-pointer problems.

Min-heap for multi-source tracking

Maintain one heap entry per source (list, stream, or sequence). Pop the minimum, process it, push the next element from the same source. This is the exact same pattern used in Merge K Sorted Lists and Find K Pairs with Smallest Sums. The only difference is what you do with the minimum after popping it.

The template:

import heapq

heap = []
max_val = float('-inf')
for i, source in enumerate(sources):
    heapq.heappush(heap, (source[0], i, 0))
    max_val = max(max_val, source[0])

while heap:
    min_val, src_idx, elem_idx = heapq.heappop(heap)
    process_range(min_val, max_val)
    if no_more_elements(src_idx, elem_idx):
        break
    next_val = get_next(src_idx, elem_idx)
    heapq.heappush(heap, (next_val, src_idx, elem_idx + 1))
    max_val = max(max_val, next_val)

Range tracking with a running max

While the heap gives you the minimum in O(1), you track the maximum separately as a simple variable. Every time you push a new value into the heap, you update the max. The range at any point is [heap_root, max_val]. This asymmetric approach works because you only advance the minimum side, so the max can only grow or stay the same. You never need to decrease it.

This combination of "heap for the min, variable for the max" is a useful trick whenever you need to track both ends of a moving window across sorted sequences.

From understanding to recall

The mental model for this problem is k pointers sliding forward across sorted lists, with a magnifying glass (the range) trying to squeeze tighter around them. You always push the leftmost pointer forward because that is the only move that can shrink the window.

The part that trips people up is the termination condition: you stop as soon as any list is exhausted, not when all lists are. If one list runs out of elements, you can no longer guarantee coverage of all k lists, so the range is invalid.

Spaced repetition helps you internalize both the "always advance the minimum" invariant and the termination logic. After a few reps, the heap setup and the pop-check-push loop become automatic.

Related posts

• Merge K Sorted Lists - same min-heap multi-pointer pattern
• Sliding Window Maximum - range tracking with specialized data structures
• Find K Pairs with Smallest Sums - heap-driven exploration across multiple lists