Smallest Range Covering K Lists — K-Way Merge Heap Interview

Problem Statement#

You have k non-empty sorted integer lists. Find the smallest range [a, b] that contains at least one number from each list.

Constraints:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i] is sorted in non-decreasing order.

Input:  [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

Input:  [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Why This Problem Matters#

LeetCode 632 is a hard interview problem at Google, Meta, and Amazon. It is the canonical K-way merge plus sliding-range pattern: the same skeleton used in merging K sorted streams, finding K smallest sums, and aggregating logs.

This priority queue interview classic forces you to track the running max while popping the running min — a skill that translates directly to building production aggregators.

The Core Insight#

Push one element from each list into a min-heap with its list index and position. Track the current max across the heap. The current range is [heap.peek(), max]. Pop the min, advance its list pointer, push the next element, and update the max. Stop when any list is exhausted.

Visual Dry Run#

lists = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = []
        cur_max = float('-inf')
        for i, arr in enumerate(nums):
            heapq.heappush(heap, (arr[0], i, 0))
            cur_max = max(cur_max, arr[0])
        best = [float('-inf'), float('inf')]
        while heap:
            val, i, j = heapq.heappop(heap)
            if cur_max - val < best[1] - best[0]:
                best = [val, cur_max]
            if j + 1 == len(nums[i]):
                break
            nxt = nums[i][j + 1]
            cur_max = max(cur_max, nxt)
            heapq.heappush(heap, (nxt, i, j + 1))
        return best

class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i][0] < this.h[p][0]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l][0] < this.h[m][0]) m = l;
            if (r < n && this.h[r][0] < this.h[m][0]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
var smallestRange = function(nums) {
    const heap = new MinHeap();
    let curMax = -Infinity;
    nums.forEach((arr, i) => {
        heap.push([arr[0], i, 0]);
        curMax = Math.max(curMax, arr[0]);
    });
    let best = [-Infinity, Infinity];
    while (heap.size) {
        const [val, i, j] = heap.pop();
        if (curMax - val < best[1] - best[0]) best = [val, curMax];
        if (j + 1 === nums[i].length) break;
        const nxt = nums[i][j + 1];
        curMax = Math.max(curMax, nxt);
        heap.push([nxt, i, j + 1]);
    }
    return best;
};

Time: O(N log K) — N total elements, each heap op is log K. Space: O(K) — heap holds one element per list.

Common Mistakes#

• Forgetting to update cur_max when seeding the heap.
• Updating cur_max after the comparison instead of before pushing.
• Wrong tiebreak: smaller range wins, not lower-left endpoint.
• Stopping too early — you stop only when a list runs out.
• Returning the heap top as the right endpoint; the right endpoint is cur_max.

Interview Tips#

• Frame this as K-way merge with a sliding window across all K lists.
• Discuss why we cannot just merge into a single array — that is O(N log N) which is the same big-O but loses the early termination.
• Mention the dual: this is the inverse of merging K sorted lists where you would output every element.
• Walk through the invariant: at each step, the heap top is the min and cur_max is the max.

Follow-up Questions#

• What if lists can be empty? Hint: filter or return special value.
• What if you must return all minimal ranges? Hint: collect during traversal with equality check.
• What if K is huge but N is small? Hint: this approach is already log K.
• Solve without a heap. Hint: sliding window over a flattened (val, list_id) sorted array.
• What about K infinite streams? Hint: assume non-decreasing, run online with a heap.

Key Takeaways#

• LeetCode 632 Smallest Range Covering K Lists is a K-way merge plus sliding range problem.
• Min-heap tracks the smallest current element; cur_max tracks the largest.
• Time: O(N log K). Space: O(K).
• The heap holds exactly one entry per list at all times.
• Stop when any list is exhausted — you cannot improve afterward.
• This pattern reuses for streaming aggregation and sensor fusion.
• A frequent Google and Meta priority queue interview question.