This is a classic interview problem, often referred to as the LeetCode 632 Solution, which tests the ability to manage multiple sorted data streams efficiently.

Brute Force Approach for Smallest Range Covering Elements from K Lists

A naive approach to solving Smallest Range Covering Elements from K Lists involves collecting all numbers from all lists and attempting to verify every possible range.

1. Flatten and Sort: Combine all elements from the $k$ lists into a single list of pairs (value, original_list_index). Sort this combined list by value.
2. Sliding Window Check: Iterate through the sorted combined list using two pointers (left and right).
3. Validation: For every window defined by left and right, check if the window contains at least one element from all $k$ lists (using a frequency map or counter).
4. Minimization: If the window is valid, record the range [combined[left].value, combined[right].value] and try to shrink the window from the left. If invalid, expand to the right.

Pseudo-code:

text
function bruteForce(nums):
    merged_list = []
    for i from 0 to k-1:
        for val in nums[i]:
            merged_list.add({val, i})
    
    sort(merged_list)
    
    min_range = infinite
    for i from 0 to length(merged_list):
        for j from i to length(merged_list):
            sub_array = merged_list[i...j]
            if sub_array contains all k list indices:
                update min_range

Complexity Analysis:

• Time Complexity: If $N$ is the total number of elements across all lists, sorting takes $O(N \log N)$. The sliding window check, if implemented naively by rescanning, could approach $O(N^2)$. Even with an optimized sliding window on the flattened array, the sorting step dominates.
• Why it fails: While an optimized sliding window on a sorted array is $O(N \log N)$ or $O(N)$, the space complexity becomes $O(N)$ to store all elements. Furthermore, this approach discards the valuable structural information that the input lists are sorted, performing redundant work.

Core Insight for Smallest Range Covering Elements from K Lists

The critical insight for the LeetCode 632 Solution is understanding how to manipulate the range boundaries $[min, max]$ efficiently.

To cover every list, our current set of "active" numbers must contain exactly one number from each of the $k$ lists. Initially, the smallest possible candidates are the first elements of each list. Let's call the minimum of these candidates currentMin and the maximum currentMax. The range is $[currentMin, currentMax]$.

To find a smaller range, we must shrink the difference $currentMax - currentMin$. We have two options:

1. Decrease currentMax: We cannot do this. The lists are sorted in ascending order. If we pick a previous element from the list that contributed currentMax, that value would be smaller, but we have already processed it (or it's the start of the list). Backtracking isn't viable in a forward-scan.
2. Increase currentMin: This is possible. If we remove the element contributing currentMin and replace it with the next element from the same list, the new currentMin of the set will be greater than or equal to the old one. This moves the start of the range to the right, potentially shrinking the range size (even if the new element increases currentMax).

Invariant: The Min-Heap always holds exactly $k$ elements—one specific element from each of the $k$ lists. This ensures that the range $[heap.min(), global\_max\_in\_heap]$ is always a valid range covering all lists.

Visual Description: Imagine $k$ horizontal strips of numbers. We place a pointer at the start of each strip. The Min-Heap tells us which pointer is currently pointing to the smallest value. We calculate the range using this minimum and the known maximum of the pointed-to values. To proceed, we advance only the pointer that pointed to the minimum value. This "pulls" the left boundary of our range to the right. We repeat this until one pointer runs off the end of its strip.

Execution Flow

Let's trace the logic with a simple example: nums = [[4, 10], [0, 9], [5, 18]].

1. Setup:

   • Heap: [(0, list1), (4, list0), (5, list2)] (sorted by value).
   • currentMax: 5.
   • bestRange: $[-\infty, \infty]$.

2. Iteration 1:

   • Pop Min: 0 (from list 1).
   • Current Range: $[0, 5]$. Update bestRange to $[0, 5]$.
   • Next in list 1: 9.
   • Update currentMax: $\max(5, 9) = 9$.
   • Push: 9 to Heap. Heap is now [(4, list0), (5, list2), (9, list1)].

3. Iteration 2:

   • Pop Min: 4 (from list 0).
   • Current Range: $[4, 9]$. Length 5 (same as previous, but $4 > 0$, so don't update).
   • Next in list 0: 10.
   • Update currentMax: $\max ($.

4. Iteration 3:

   • Pop Min: 5 (from list 2).
   • Current Range: $[5, 10]$. Length 5.
   • Next in list 2: 18.
   • Update currentMax: $\max(10, 18) = 18$.

5. Iteration 4:

   • Pop Min: 9 (from list 1).
   • Current Range: $[9, 18]$. Length 9. No update.
   • Next in list 1: None (End of list).
   • Terminate.

6. Result: $[0, 5]$ (Wait, re-evaluating Example 1 logic from description: the example output $[20, 24]$ comes from a different input set. For this trace, $[0, 5]$ is valid).

Proof of Correctness

The algorithm is correct because it exhaustively checks every possible "start" of a minimal range. A minimal range covering all lists must start with an element from one of the lists. Let that starting element be $x$. To minimize the range $[x, y]$, $y$ must be the smallest possible value such that the range includes elements from all other lists.

Because our heap invariant maintains one active element from every list, the current currentMax in the algorithm represents exactly that smallest necessary $y$ for the current minimum $x$. By iterating through the sorted elements using the Min-Heap, we efficiently generate and test the optimal range $[x, y]$ for every possible $x$ in increasing order, until one list runs out of candidates.

Reference Implementation

C++ Solution for LeetCode 632

cpp
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        // Min-heap stores {value, list_index, element_index}
        // Using a custom comparator or simply putting value first in vector/pair
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
        
        int currentMax = INT_MIN;
        int k = nums.size();
        
        // Initialize heap with the first element of each list
        for (int i = 0; i < k; ++i) {
            int val = nums[i][0];
            minHeap.push({val, i, 0});
            currentMax = max(currentMax, val);
        }
        
        int rangeStart = 0;
        int rangeEnd = INT_MAX;
        
        while (minHeap.size() == k) {
            vector<int> top = minHeap.top();
            minHeap.pop();
            
            int minVal = top[0];
            int listIdx = top[1];
            int elemIdx = top[2];
            
            // Check if current range is smaller than the best found so far
            if ((long long)currentMax - minVal < (long long)rangeEnd - rangeStart) {
                rangeStart = minVal;
                rangeEnd = currentMax;
            }
            
            // If the list of the extracted element has more elements, push the next one
            if (elemIdx + 1 < nums[listIdx].size()) {
                int nextVal = nums[listIdx][elemIdx + 1];
                minHeap.push({nextVal, listIdx, elemIdx + 1});
                currentMax = max(currentMax, nextVal);
            } else {
                // If any list is exhausted, we cannot form a valid range covering all k lists
                break;
            }
        }
        
        return {rangeStart, rangeEnd};
    }
};

Java Solution for LeetCode 632

java
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // Min-heap stores int[] {value, listIndex, elementIndex}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        int currentMax = Integer.MIN_VALUE;
        
        // Initialize heap
        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 = 0;
        int rangeEnd = Integer.MAX_VALUE;
        
        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            int minVal = curr[0];
            int listIdx = curr[1];
            int elemIdx = curr[2];
            
            // Update range if smaller
            if (currentMax - minVal < rangeEnd - rangeStart) {
                rangeStart = minVal;
                rangeEnd = currentMax;
            }
            
            // Move to next element in the specific list
            if (elemIdx + 1 < nums.get(listIdx).size()) {
                int nextVal = nums.get(listIdx).get(elemIdx + 1);
                minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
                currentMax = Math.max(currentMax, nextVal);
            } else {
                // Cannot cover all lists anymore
                break;
            }
        }
        
        return new int[]{rangeStart, rangeEnd};
    }
}

Python Solution for LeetCode 632

python
import heapq

class Solution:
    def smallestRange(self, nums: list[list[int]]) -> list[int]:
        min_heap = []
        current_max = -float('inf')
        
        # Initialize heap with the first element of each list
        # Store tuple: (value, list_index, element_index)
        for i in range(len(nums)):
            val = nums[i][0]
            heapq.heappush(min_heap, (val, i, 0))
            current_max = max(current_max, val)
            
        best_range_start = -float('inf')
        best_range_end = float('inf')
        
        while min_heap:
            min_val, list_idx, elem_idx = heapq.heappop(min_heap)
            
            # Update best range if the current one is smaller
            if current_max - min_val < best_range_end - best_range_start:
                best_range_start = min_val
                best_range_end = current_max
            
            # If we reach the end of one list, we stop
            if elem_idx + 1 == len(nums[list_idx]):
                break
                
            next_val = nums[list_idx][elem_idx + 1]
            heapq.heappush(min_heap, (next_val, list_idx, elem_idx + 1))
            current_max = max(current_max, next_val)
            
        return [best_range_start, best_range_end]