Code Implementation

import heapq

class Solution:
    def smallestRange(self, nums):
        # nums: List[List[int]]
        # Each list is sorted
        heap = []
        current_max = float('-inf')
        # Initialize heap with first element from each list
        for i, row in enumerate(nums):
            val = row[0]
            heapq.heappush(heap, (val, i, 0))  # (value, list_index, element_index)
            current_max = max(current_max, val)

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

        while True:
            min_val, list_idx, ele_idx = heapq.heappop(heap)
            # Update best range if this is smaller
            if current_max - min_val < best_range[1] - best_range[0]:
                best_range = [min_val, current_max]

            # Move to next element in same list, if possible
            if ele_idx + 1 == len(nums[list_idx]):
                break  # One list exhausted, can't cover all
            next_val = nums[list_idx][ele_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, ele_idx + 1))
            current_max = max(current_max, next_val)

        return best_range
      

#include <vector>
#include <queue>
#include <limits>
using namespace std;

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        typedef tuple<int, int, int> Node; // (value, list_idx, ele_idx)
        auto cmp = [](const Node& a, const Node& b) { return get<0>(a) > get<0>(b); };
        priority_queue<Node, vector<Node>, decltype(cmp)> minHeap(cmp);

        int current_max = numeric_limits<int>::min();
        for (int i = 0; i < nums.size(); ++i) {
            minHeap.emplace(nums[i][0], i, 0);
            current_max = max(current_max, nums[i][0]);
        }

        vector<int> best_range = {numeric_limits<int>::min(), numeric_limits<int>::max()};
        while (true) {
            auto [min_val, list_idx, ele_idx] = minHeap.top();
            minHeap.pop();
            if (current_max - min_val < best_range[1] - best_range[0]) {
                best_range = {min_val, current_max};
            }
            if (ele_idx + 1 == nums[list_idx].size())
                break;
            int next_val = nums[list_idx][ele_idx + 1];
            minHeap.emplace(next_val, list_idx, ele_idx + 1);
            current_max = max(current_max, next_val);
        }
        return best_range;
    }
};
      

import java.util.*;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int currentMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            currentMax = Math.max(currentMax, val);
        }
        int rangeStart = -100000, rangeEnd = 100000;
        while (true) {
            int[] min = minHeap.poll();
            int minVal = min[0], listIdx = min[1], eleIdx = min[2];
            if (currentMax - minVal < rangeEnd - rangeStart) {
                rangeStart = minVal;
                rangeEnd = currentMax;
            }
            if (eleIdx + 1 == nums.get(listIdx).size())
                break;
            int nextVal = nums.get(listIdx).get(eleIdx + 1);
            minHeap.offer(new int[]{nextVal, listIdx, eleIdx + 1});
            currentMax = Math.max(currentMax, nextVal);
        }
        return new int[]{rangeStart, rangeEnd};
    }
}
      

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(item) {
        this.heap.push(item);
        this._bubbleUp();
    }
    pop() {
        if (this.heap.length < 2) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._bubbleDown();
        return top;
    }
    _bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    _bubbleDown() {
        let idx = 0, len = this.heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
            if (left < len && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < len && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === idx) break;
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}

var smallestRange = function(nums) {
    let heap = new MinHeap();
    let maxVal = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        heap.push([nums[i][0], i, 0]);
        maxVal = Math.max(maxVal, nums[i][0]);
    }
    let best = [-Infinity, Infinity];
    while (true) {
        let [minVal, listIdx, eleIdx] = heap.pop();
        if (maxVal - minVal < best[1] - best[0]) best = [minVal, maxVal];
        if (eleIdx + 1 === nums[listIdx].length) break;
        let nextVal = nums[listIdx][eleIdx + 1];
        heap.push([nextVal, listIdx, eleIdx + 1]);
        maxVal = Math.max(maxVal, nextVal);
    }
    return best;
};
      

Problem Description

You are given k sorted integer lists, represented as nums, where nums[i] is the i-th list. Your task is to find the smallest range [a, b] (inclusive) such that at least one number from each of the k lists is included in this range.

• The output should be the range [a, b] where a and b are integers, and a <= b.
• If there are multiple such ranges with the same length, return the one with the smallest a.
• You must pick exactly one element from each list to cover all lists in the range. You cannot reuse elements from the same list for the same range.
• There is always at least one valid solution.

For example, given nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]], the answer should be [20,24] because 20 (from the second list), 24 (from the first), and 22 (from the third) are all within [20,24].

Thought Process

At first glance, the problem seems to ask for a range that "touches" every list at least once. The brute-force idea would be to consider all possible combinations by picking one element from each list, then finding the smallest and largest among them, and keeping track of the smallest such range. But this quickly becomes infeasible as the number of lists and their sizes grow, because the number of combinations is the product of the lengths of all lists.

To optimize, we notice that since all lists are sorted, we can try to "merge" the lists in a way similar to the merge step of merge sort, always advancing the smallest current element. This way, we can efficiently check the current range covered by one element from each list, and try to minimize it as we go.

The key insight is to always keep track of the current minimum and maximum among the chosen elements (one from each list), and to try advancing the pointer in the list that currently contributes the minimum. This is because increasing the minimum may help shrink the range, while increasing the maximum would only make the range larger.

Solution Approach

• Step 1: Use a min-heap (priority queue) to track the current smallest element among all lists. Each entry in the heap stores the value, the index of the list it came from, and the index within that list.
• Step 2: Initialize the heap by inserting the first element from each list. Also, keep track of the current maximum value among these elements.
• Step 3: At each step, pop the smallest element from the heap. This gives us the current minimum. The current range is from this minimum to the current maximum.
• Step 4: Update the best (smallest) range found so far if the current range is smaller.
• Step 5: Advance the pointer in the list from which the minimum came: if there are more elements in that list, insert the next element into the heap and update the current maximum if necessary.
• Step 6: If any list is exhausted (no more elements to push from that list), stop: we cannot cover all lists anymore.

This approach is efficient because at every step, we only consider the next smallest possible range that covers all lists, and we never revisit the same combination.

Example Walkthrough

Let's walk through the example nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]:

1. Initialize: Heap contains (4,0,0), (0,1,0), (5,2,0). Current max is 5.
2. Step 1: Pop (0,1,0). Range is [0,5]. Push next from list 1: (9,1,1). Max is now 9.
3. Step 2: Pop (4,0,0). Range is [4,9]. Push (10,0,1). Max is now 10.
4. Step 3: Pop (5,2,0). Range is [5,10]. Push (18,2,1). Max is now 18.
5. Step 4: Pop (9,1,1). Range is [9,18]. Push (12,1,2). Max stays 18.
6. Step 5: Pop (10,0,1). Range is [10,18]. Push (15,0,2). Max stays 18.
7. Step 6: Pop (12,1,2). Range is [12,18]. Push (20,1,3). Max stays 20.
8. Step 7: Pop (15,0,2). Range is [15,20]. Push (24,0,3). Max is now 24.
9. Step 8: Pop (18,2,1). Range is [18,24]. Push (22,2,2). Max stays 24.
10. Step 9: Pop (20,1,3). Range is [20,24]. Push (no more in list 1, so we stop).

The best range found during this process is [20,24], which covers 24 (from list 0), 20 (from list 1), and 22 (from list 2).

Time and Space Complexity

• Brute-force: For k lists of length up to n, brute-force would check all n^k combinations, which is exponential and infeasible for large inputs.
• Optimized Heap Approach:
  • Each element in all lists is pushed and popped from the heap at most once. If there are N total elements, this is O(N \log k) time, since the heap has at most k elements.
  • Space complexity is O(k) for the heap and O(1) for pointers, not counting the input.

This makes the optimized approach efficient and practical even for large datasets.

Summary

The problem of finding the smallest range covering at least one element from each of k sorted lists is elegantly solved using a min-heap to always track the current minimum, and a variable to track the current maximum. By advancing only the list that contributed the minimum, we efficiently explore all possible ranges without redundant work. This approach leverages the sorted property of the lists and the power of heaps to achieve an optimal O(N \log k) solution, making it both elegant and efficient.